## Erdos-Szekeres Theorem

Hello to all MHF members...

I want to share with you a nice proof of the theorem:

Erdős-Szekeres Theorem -- from Wolfram MathWorld
I will prove this theorem for $\displaystyle a=b=n$ using the following theorem:

(*) If $\displaystyle A,B$ are finite sets, then:

$\displaystyle |A|\leq|B|\Longleftrightarrow$ exist an injective function from $\displaystyle A$ to $\displaystyle B$.

Proof of the main theorem:

Let $\displaystyle a_1,a_2,...,a_{n^2+1}$ be elements of the sequence.

Suppose that this sequence not contains a monotonic increasing subsequence of $\displaystyle n+1$ terms or a monotonic decreasing subsequence of $\displaystyle n+1$ terms.

By assumption, every monotonic increasing subsequence and every monotonic decreasing subsequence are at length of $\displaystyle n$, at most.

Let be $\displaystyle A=\{a_1,a_2,...,a_{n^2+1}\}$, now we look at the function:

$\displaystyle f:A\longrightarrow \{1,2,...,n\}^2$, which is given by: $\displaystyle f(a_k)=<i_k,j_k>$, when $\displaystyle i_k$ is the length of the longest monotonic increasing subsequence which starts with $\displaystyle a_k$ and $\displaystyle j_k$ is the length of the longest monotonic decreasing subsequence which starts with $\displaystyle a_k$.

$\displaystyle f$ is injective function.

Proof:

We need to show that if $\displaystyle k_1<k_2$, then $\displaystyle <i_{k_1},j_{k_1}>\neq <i_{k_2},j_{k_2}>$.

Every elements are diffident, therefor if $\displaystyle k_1<k_2$, then $\displaystyle a_{k_1}\neq a_{k_2}$, hence $\displaystyle a_{k_1}<a_{k_2}$ or $\displaystyle a_{k_1}>a_{k_2}$.

If $\displaystyle a_{k_1}<a_{k_2}$, we look at monotonic increasing subsequence which starts with $\displaystyle a_{k_2}$ her length is $\displaystyle i_{k_2}$. Now we add $\displaystyle a_{k_1}$ to the beginning of this subsequence and we get monotonic increasing subsequence which starts with $\displaystyle a_{k_1}$ her length is $\displaystyle i_{k_2}+1$, it is clear that $\displaystyle i_{k_1}>i_{k_2}$. If $\displaystyle a_{k_1}>a_{k_2}$ we look at monotonic decreasing subsequence which starts with $\displaystyle a_{k_2}$ her length is $\displaystyle j_{k_2}$, we add $\displaystyle a_{k_1}$ to the beginning of this subsequence, and we will get $\displaystyle j_{k_1}>j_{k_2}$.

Anyway, $\displaystyle i_{k_1}\neq i_{k_2}$ or $\displaystyle j_{k_1}>j_{k_2}$, hence $\displaystyle <i_{k_1},j_{k_1}>\neq <i_{k_2},j_{k_2}>$.

Therfor $\displaystyle f$ is injective.

From the theorem above:

$\displaystyle |A|\leq \ |\{1,2...,n\}^2|$ or $\displaystyle n^2+1\leq n^2$, a contradiction, which is prove the theorem.

(*) Actually it is the "pigeonhole" principle.