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)=<i_k,j_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<k_2, then <i_{k_1},j_{k_1}>\neq <i_{k_2},j_{k_2}>.

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

If a_{k_1}<a_{k_2}, 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 <i_{k_1},j_{k_1}>\neq <i_{k_2},j_{k_2}>.

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.