Lesson 4

Theorem (Erd\H{o}s–Szekeres Theorem, 1935). Any sequence of \(rs+1\) distinct real numbers has an increasing subsequence of length at least \(r+1\) or a decreasing subsequence of length at least \(s+1\).

Proof. Let the sequence be \(x_{1}, x_{2}, \dotsc, x_{rs+1}\). We define a poset on the set of indices \(P = \{1, 2, \dotsc, rs+1\}\). For two indices \(i, j \in P\), we say \(i \prec j\) if both \(i < j\) and \(x_{i} < x_{j}\). Hence, a chain in this poset forms increasing subsequence. And, if we take an antichain and order the indices in it, we would obtain a decreasing subsequence.

Let \(h\) be the length of the longest chain (longest increasing subsequence) and \(w\) be the size of the largest antichain (longest decreasing subsequence). By Dilworth's theorem, the set \(P\) can be partitioned into \(w\) chains. We have \(rs+1\) elements in \(P\) distributed among \(w\) chains. By the Pigeonhole Principle, at least one of these chains must contain at least \(\lceil \frac{rs+1}{w}\rceil\) elements. The length of the longest chain, \(h\), must be at least this large: \[h \ge \left\lceil \frac{rs+1}{w}\right\rceil.\] This inequality implies \(h \cdot w \ge rs+1\). Therefore, either there is an increasing subsequence of length at least \(r+1\), or a decreasing subsequence of length at least \(s+1\).◼