.
Erdos-Szekeres lemma: A sequence of $n^2+1$ real numbers contains a monotonic subsequence of length $n+1$.
First Proof. (direct argument)
Let the sequence be $\langle x_1,x_2,\dots,x_{n^2+1}\rangle$. We associate an ordered pair $(a_i,b_i)$ for each $1\le i\le n^2+1$ such that $a_i$ is the length of the longest monotonically increasing sequence ending at $x_i$ and $b_i$ is the length of the longest monotonically decreasing sequence ending at $x_i$. We might note that if $i<j$ then $(a_i,b_i)\ne (a_j,b_j)$. If $x_i<x_j$, then $a_j$ is at least one more than $a_i$. Else if, $x_i>x_j$, then $b_j$ is at least one more than $b_i$. By pigeon hole principle, there is at least one ordered pair other than $\{(a,b) \, | \, 1\le a\le n,1\le b\le n\}$.
Second Proof. (based structure theorem of finite posets)
Let $X=\{1,2,3,\dots ,n^2+1\}$. Lets define an order $i\preceq j$ if $i\le j$ and $x_i\le x_j$ where $1\le i,j\le n^2+1$ to get the poset $(X,\preceq)$. A chain $i_1\preceq i_2\preceq \dots \preceq i_m$ in $(X,\preceq)$ corresponds to a monotonically increasing subsequence $x_{i_1}\le x_{i_2}\le \dots \le x_{i_m}$ (as $i_1<i_2<\dots <i_m$). Similarly, an antichain in $(X,\preceq)$ corresponds to a monotonically decreasing sequence. By structure theorem, $\alpha(X,\preceq)\cdot \omega (X,\preceq)\ge n^2+1$ where $\alpha(X,\preceq)$ is the length of the longest chain and $\omega (X,\preceq)$ is the length of the longest antichain. Hence, $\alpha(X,\preceq)>n$ or $\omega(X,\preceq)>n$.
Third Proof. (based on Dilworth's theorem)
Suppose define the order as in the second proof. If the length of every chain does not exceed $n$, then, there must be more than $n$ chains. By dilworth's theorem, we have an antichain of length greater than $n$.
PDF copy of the post
— 07 Apr 2014 19:10
Comments: 0