The minimum number of monotone subsequences

Joseph Samuel Myers

The electronic journal of combinatorics, Permutation Patterns, Tome 9 (2002) no. 2

Résumé

Erdős and Szekeres showed that any permutation of length $n \geq k^2+1$ contains a monotone subsequence of length $k+1$. A simple example shows that there need be no more than $(n \bmod k){{\lceil n/k \rceil}\choose {k+1}} + (k - (n \bmod k)){{\lfloor n/k \rfloor}\choose {k+1}}$ such subsequences; we conjecture that this is the minimum number of such subsequences. We prove this for $k=2$, with a complete characterisation of the extremal permutations. For $k > 2$ and $n \geq k(2k-1)$, we characterise the permutations containing the minimum number of monotone subsequences of length $k+1$ subject to the additional constraint that all such subsequences go in the same direction (all ascending or all descending); we show that there are $2 {{k}\choose {n \bmod k}} C_k^{2k-2}$ such extremal permutations, where $C_k = {{1}\over {k+1}}{{2k}\choose {k}}$ is the $k^{{\rm th}}$ Catalan number. We conjecture, with some supporting computational evidence, that permutations with a minimum number of monotone $(k+1)$-subsequences must have all such subsequences in the same direction if $n \geq k(2k-1)$, except for the case of $k = 3$ and $n = 16$.

Détail

DOI : 10.37236/1676

Classification : 05A05, 05D10, 05C35
Mots-clés : monotone subsequence, permutation