Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-23T13:55:39.786Z Has data issue: false hasContentIssue false
  • English
  • Français

Minimum Number of Monotone Subsequences of Length 4 in Permutations

Part of: Combinatorics Graph theory Extremal combinatorics

Published online by Cambridge University Press:  19 December 2014

JÓZSEF BALOGH ,
PING HU ,
BERNARD LIDICKÝ ,
OLEG PIKHURKO ,
BALÁZS UDVARI  and
JAN VOLEC
JÓZSEF BALOGH
Affiliation:
Department of Mathematics, University of Illinois, Urbana, IL 61801, USA (e-mail: [email protected], [email protected], [email protected]) Bolyai Institute, University of Szeged, Szeged, Hungary (e-mail: [email protected])
PING HU
Affiliation:
Department of Mathematics, University of Illinois, Urbana, IL 61801, USA (e-mail: [email protected], [email protected], [email protected])
BERNARD LIDICKÝ
Affiliation:
Department of Mathematics, University of Illinois, Urbana, IL 61801, USA (e-mail: [email protected], [email protected], [email protected]) Charles University, Prague, Czech Republic
OLEG PIKHURKO
Affiliation:
Mathematics Institute and DIMAP, University of Warwick, Coventry CV4 7AL, UK (e-mail: [email protected], [email protected])
BALÁZS UDVARI
Affiliation:
Bolyai Institute, University of Szeged, Szeged, Hungary (e-mail: [email protected])
JAN VOLEC
Affiliation:
Mathematics Institute and DIMAP, University of Warwick, Coventry CV4 7AL, UK (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We show that for every sufficiently large n, the number of monotone subsequences of length four in a permutation on n points is at least

\begin{equation*} \binom{\lfloor{n/3}\rfloor}{4} + \binom{\lfloor{(n+1)/3}\rfloor}{4} + \binom{\lfloor{(n+2)/3}\rfloor}{4}. \end{equation*}
Furthermore, we characterize all permutations on [n] that attain this lower bound. The proof uses the flag algebra framework together with some additional stability arguments. This problem is equivalent to some specific type of edge colourings of complete graphs with two colours, where the number of monochromatic K4 is minimized. We show that all the extremal colourings must contain monochromatic K4 only in one of the two colours. This translates back to permutations, where all the monotone subsequences of length four are all either increasing, or decreasing only.

MSC classification

Primary: 05C35: Extremal problems
Secondary: 05D99: None of the above, but in this section 05A05: Permutations, words, matrices
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 24 , Special Issue 4: Oberwolfach Special Issue Part 1 , July 2015 , pp. 658 - 679
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Albert, M. H., Atkinson, M. D., Handley, C. C., Holton, D. A. and Stromquist, W. (2002) On packing densities of permutations. Electron. J. Combin. 9 R5.CrossRefGoogle Scholar
[2]Alon, N. and Shapira, A. (2008) A characterization of the (natural) graph properties testable with one-sided error. SIAM J. Comput. 37 1703–1727.CrossRefGoogle Scholar
[3]Baber, R. Turán densities of hypercubes. Submitted.Google Scholar
[4]Baber, R. (2011) Some results in extremal combinatorics. Dissertation.Google Scholar
[5]Baber, R. and Talbot, J. (2011) Hypergraphs do jump. Combin. Probab. Comput. 20 161–171.CrossRefGoogle Scholar
[6]Baber, R. and Talbot, J. (2014) A solution to the 2/3 conjecture. SIAM J. Discrete Math. 28 756–766.CrossRefGoogle Scholar
[7]Balogh, J., Hu, P., Lidický, B. and Liu, H. (2014) Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube. European J. Combin. 35 75–85.CrossRefGoogle Scholar
[8]Borchers, B. (1999) CSDP: A C library for semidefinite programming. Optimization Methods and Software 11 613–623.CrossRefGoogle Scholar
[9]Cummings, J., Kráľ, D., Pfender, F., Sperfeld, K., Treglown, A. and Young, M. (2013) Monochromatic triangles in three-coloured graphs. J. Combin. Theory Ser. B 103 489–503.CrossRefGoogle Scholar
[10]Das, S., Huang, H., Ma, J., Naves, H. and Sudakov, B. (2013) A problem of Erdős on the minimum number of k-cliques. J. Combin. Theory Ser. B 103 344–373.CrossRefGoogle Scholar
[11]Erdős, P. and Szekeres, G. (1935) A combinatorial problem in geometry. Compositio Math. 2 463–470.Google Scholar
[12]Falgas-Ravry, V. and Vaughan, E. R. (2013) Applications of the semi-definite method to the Turán density problem for 3-graphs. Combin. Probab. Comput. 22 21–54.CrossRefGoogle Scholar
[13]Giraud, G. (1979) Sur le problème de Goodman pour les quadrangles et la majoration des nombres de Ramsey. J. Combin. Theory Ser. B 27 237–253.CrossRefGoogle Scholar
[14]Glebov, R., Kráľ, D. and Volec, J. (2013) A problem of Erdős and Sós on 3-graphs. In The Seventh European Conference on Combinatorics, Graph Theory and Applications, Vol. 16 of CRM Series, Ed. Norm., Pisa. pp. 3–8.CrossRefGoogle Scholar
[15]Goodman, A. W. (1959) On sets of acquaintances and strangers at any party. Amer. Math. Monthly 66 778–783.CrossRefGoogle Scholar
[16]Grzesik, A. (2012) On the maximum number of five-cycles in a triangle-free graph. J. Combin. Theory Ser. B 102 1061–1066.CrossRefGoogle Scholar
[17]Hatami, H., Hladký, J., Kráľ, D., Norine, S. and Razborov, A. (2012) Non-three-colourable common graphs exist. Combin. Probab. Comput. 21 734–742.CrossRefGoogle Scholar
[18]Hatami, H., Hladký, J., Kráľ, D., Norine, S. and Razborov, A. (2013) On the number of pentagons in triangle-free graphs. J. Combin. Theory Ser. A 120 722–732.CrossRefGoogle Scholar
[19]Hladký, J., Kráľ, D. and Norine, S. (2009) Counting flags in triangle-free digraphs. In European Conference on Combinatorics, Graph Theory and Applications: EuroComb 2009, Vol. 34 of Electron. Notes Discrete Math., Elsevier, pp. 621–625.Google Scholar
[20]Kráľ, D., Liu, C.-H., Sereni, J.-S., Whalen, P. and Yilma, Z. B. (2013) A new bound for the 2/3 conjecture. Combin. Probab. Comput. 22 384–393.CrossRefGoogle Scholar
[21]Kráľ, D., Mach, L. and Sereni, J.-S. (2012) A new lower bound based on Gromov's method of selecting heavily covered points. Discrete Comput. Geom. 48 487–498.CrossRefGoogle Scholar
[22]Myers, J. S. (2002/03) The minimum number of monotone subsequences. Electron. J. Combin. 9 R4.CrossRefGoogle Scholar
[23]Nieß, S. Counting monochromatic copies of K 4: A new lower bound for the Ramsey multiplicity problem. Submitted.Google Scholar
[24]Pikhurko, O. (2011) The minimum size of 3-graphs without a 4-set spanning no or exactly three edges. European J. Combin. 32 1142–1155.CrossRefGoogle Scholar
[25]Pikhurko, O. and Razborov, A. Asymptotic structure of graphs with the minimum number of triangles. arXiv:1204.2846. Submitted.Google Scholar
[26]Pikhurko, O. and Vaughan, E. R. (2013) Minimum number of k-cliques in graphs with bounded independence number. Combin. Probab. Comput. 22 910–934.CrossRefGoogle Scholar
[27]Presutti, C. B. (2008) Determining lower bounds for packing densities of non-layered patterns using weighted templates. Electron. J. Combin. 15 R50.CrossRefGoogle Scholar
[28]Presutti, C. B. and Stromquist, W. (2010) Packing rates of measures and a conjecture for the packing density of 2413. In Permutation Patterns, Vol. 376 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 287–316.CrossRefGoogle Scholar
[29]Razborov, A. A. (2007) Flag algebras. J. Symbolic Logic 72 1239–1282.CrossRefGoogle Scholar
[30]Razborov, A. A. (2013) Flag algebras: An interim report. In The Mathematics of Paul Erdős II, Springer, pp. 207–232.CrossRefGoogle Scholar
[31]Razborov, A. A. (2013) On the Caccetta–Häggkvist conjecture with forbidden subgraphs. J. Graph Theory 74 236–248.CrossRefGoogle Scholar
[32]Samotij, W. and Sudakov, B. On the number of monotone sequences. Submitted.Google Scholar
[33]Sperfeld, K. The inducibility of small oriented graphs. Submitted.Google Scholar
[34]Sperfeld, K. (2011) On the minimal monochromatic K 4-density.Google Scholar
[35]Stein, W.et al. (2013) Sage Mathematics Software: Version 5.6. The SAGE Development Team. http://www.sagemath.orgGoogle Scholar
[36]Thomason, A. (1989) A disproof of a conjecture of Erdős in Ramsey theory. J. London Math. Soc. (2) 39 246–255.CrossRefGoogle Scholar
[37]Vaughan, E. R. (2013) Flagmatic: Version 2.0. http://www.flagmatic.orgGoogle Scholar
[38]Yamashita, M., Fujisawa, K., Nakata, K., Nakata, M., Fukuda, M., Kobayashi, K. and Goto, K. (2010) A high-performance software package for semidefinite programs: SDPA 7. Research Report B-460 Dept. of Mathematical and Computing Science, Tokyo Institute of Technology, Tokyo, Japan, September, 2010.Google Scholar