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 using the following theorem:

(*) If are finite sets, then:

exist an injective function from to .

Proof of the main theorem:

Let be elements of the sequence.

Suppose that this sequence not contains a monotonic increasing subsequence of terms or a monotonic decreasing subsequence of terms.

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

Let be , now we look at the function:

, which is given by: , when is the length of the longest monotonic increasing subsequence which starts with and is the length of the longest monotonic decreasing subsequence which starts with .

is injective function.

Proof:

We need to show that if , then .

Every elements are diffident, therefor if , then , hence or .

If , we look at monotonic increasing subsequence which starts with her length is . Now we add to the beginning of this subsequence and we get monotonic increasing subsequence which starts with her length is , it is clear that . If we look at monotonic decreasing subsequence which starts with her length is , we add to the beginning of this subsequence, and we will get .

Anyway, or , hence .

Therfor is injective.

From the theorem above:

or , a contradiction, which is prove the theorem.

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