# Erdos-Szekeres Theorem

• Nov 6th 2010, 03:18 PM
Also sprach Zarathustra
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 $a=b=n$ using the following theorem:

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

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

Proof of the main theorem:

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

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

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

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

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

$f$ is injective function.

Proof:

We need to show that if $k_1, then $\neq $.

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

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

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

Therfor $f$ is injective.

From the theorem above:

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

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