The minimum number of monotone subsequences (Q1856066): Difference between revisions

\textit{P. Erdős} and \textit{G. Szekeres} [Compositio Math. 2, 463-470 (1935; Zbl 0012.27010)] showed that any permutation of length \(n \geq k^2 + 1\) contains a monotone subsequence of length \(k+1\). As a variation of this problem the following question is raised: If \(n \geq k^2 + 1\), then there is at least one monotone subsequence of length \(k+1\); how many such sequences must there be? An upper bound on the minimum number of \((k+1)\)-subsequences is obtained by a simple example. It is conjectured that this bound is tight which is proven for \(k=2\), with a complete characterisation of the extremal permutations. Different from the case \(k=2\), computational experiments indicate that for \(k>2\) the extremal permutations have all \((k+1)\)-subsequences in the same direction (i.e., all ascending or all descending, respectively) if \(n \geq k(2k-1)\), except for the case \(k=3\) and \(n=16\). Under this condition it can be shown that the above bound is still tight, and the extremal permutations containing the minimum number of monotone \((k+1)\)-subsequences are characterised. It is conjectured that extremal permutations indeed have all \((k+1)\)-subsequences in the same direction if \(n \geq k(2k-1)\), except for \(k=3\) and \(n=16\).