Minimum Number of Monotone Subsequences of Length 4 in Permutations
- 19 December 2014
- journal article
- conference paper
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 24 (4) , 658-679
Abstract
We show that for every sufficiently largen, the number of monotone subsequences of length four in a permutation onnpoints 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 monochromaticK4is minimized. We show that all the extremal colourings must contain monochromaticK4only 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.
Keywords
All Related Versions
This publication has 29 references indexed in Scilit:
- On the maximum number of five-cycles in a triangle-free graphJournal of Combinatorial Theory, Series B, 2012
- A New Lower Bound Based on Gromov’s Method of Selecting Heavily Covered PointsDiscrete & Computational Geometry, 2012
- The minimum size of 3-graphs without a 4-set spanning no or exactly three edgesEuropean Journal of Combinatorics, 2011
- Packing rates of measures and a conjecture for the packing density of 24132010
- Counting flags in triangle-free digraphsElectronic Notes in Discrete Mathematics, 2009
- A Characterization of the (Natural) Graph Properties Testable with One-Sided ErrorSIAM Journal on Computing, 2008
- CSDP, A C library for semidefinite programmingOptimization Methods and Software, 1999
- A Disproof of a Conjecture of Erdős in Ramsey TheoryJournal of the London Mathematical Society, 1989
- Sur le problème de Goodman pour les quadrangles et la majoration des nombres de RamseyJournal of Combinatorial Theory, Series B, 1979
- On Sets of Acquaintances and Strangers at any PartyThe American Mathematical Monthly, 1959