TAOCP 5.1.4 Exercise 3

Section 5.1.4: Tableaux and Involutions

Exercise 3. [**] [M18] (P. Erdős, G. Szekeres.) Prove that any permutation containing more than $n^2$ elements has a monotonic subsequence of length greater than $n$; but there are permutations of $n^2$ elements with no monotonic subsequences of length greater than $n$.

[Hint: See the previous exercise.]

Verified: yes
Solve time: 1m26s

Let $P$ be the tableau corresponding to a permutation $a_1 a_2 \dots a_m$. By Exercise 2, the number of columns of $P$ equals the length of the longest increasing subsequence of $a_1,\dots,a_m$, and the number of rows equals the length of the longest decreasing subsequence.

If $m>n^2$, assume that $a_1,\dots,a_m$ has no increasing subsequence of length $>n$ and no decreasing subsequence of length $>n$. Then every increasing subsequence has length $\le n$, hence $P$ has at most $n$ columns; every decreasing subsequence has length $\le n$, hence $P$ has at most $n$ rows. The shape of $P$ is therefore contained in an $n\times n$ rectangle, so $P$ contains at most $n^2$ cells, hence at most $n^2$ entries. This contradicts $m>n^2$. Therefore any permutation of more than $n^2$ elements contains an increasing subsequence of length $>n$ or a decreasing subsequence of length $>n$.

For the second statement, define a permutation of $n^2$ elements by concatenating $n$ blocks

$B_i = (in, in-1, \dots, (i-1)n+1), \quad 1\le i \le n.$

Within each block the sequence is strictly decreasing, and every element of $B_i$ is less than every element of $B_{i+1}$. Any increasing subsequence can contain at most one element from each block, since each block is decreasing, so its length is at most $n$. Any decreasing subsequence is contained in a single block, since elements from different blocks appear in increasing order of value, so its length is at most $n$. Hence this permutation of $n^2$ elements has no monotonic subsequence of length greater than $n$. ∎