Erdős–Szekeres theorem on monotone subsequences

proof via partial orders

Let

$$x_1,x_2,\ldots,x_{ab+1}$$

be $ab+1$ distinct real numbers.

Define a partial order on the indices

$$\{1,2,\ldots,ab+1\}$$

by

$$i\prec j \quad\Longleftrightarrow\quad i<j \text{ and } x_i<x_j.$$

A chain

$$i_1\prec i_2\prec\cdots\prec i_r$$

is exactly an increasing subsequence

$$x_{i_1}<x_{i_2}<\cdots<x_{i_r}.$$

Assume that there is no increasing subsequence of length $a+1$. Thus every chain has length at most $a$.

For each index $i$, let

$$r(i)$$

be the length of the longest chain ending at $i$.

Then

$$1\le r(i)\le a.$$

For $k=1,\ldots,a$, define

$$A_k=\{i:r(i)=k\}.$$

These sets partition the $ab+1$ indices:

$$\{1,\ldots,ab+1\} = A_1\sqcup A_2\sqcup\cdots\sqcup A_a.$$

Since there are $ab+1$ elements distributed among only $a$ sets, the pigeonhole principle gives some $k$ such that

$$|A_k|\ge b+1.$$

We claim that the terms corresponding to $A_k$, when read in their original order, form a decreasing subsequence.

Indeed, let

$$i<j,\qquad i,j\in A_k.$$

If we had

$$x_i<x_j,$$

then $i\prec j$. Any longest chain ending at $i$ could then be extended by $j$, giving

$$r(j)\ge r(i)+1=k+1,$$

contradicting

$$r(j)=k.$$

Therefore

$$x_i>x_j.$$

Hence, if

$$i_1<i_2<\cdots<i_m$$

are the elements of $A_k$, then

$$x_{i_1}>x_{i_2}>\cdots>x_{i_m},$$

where

$$m=|A_k|\ge b+1.$$

Thus there is a decreasing subsequence of length at least $b+1$.

Consequently, every sequence of $ab+1$ distinct numbers contains either an increasing subsequence of length at least $a+1$, or a decreasing subsequence of length at least $b+1$.

$$\boxed{\text{Erdős--Szekeres}}$$