Erdős–Szekeres theorem

Statement

Let $r$ and $s$ be positive integers. Let $a_1, a_2, \dots, a_N$ be a sequence of $N = (r - 1)(s - 1) + 1$ distinct real numbers. Then the sequence has an increasing subsequence of length $r$ or a decreasing subsequence of length $s$.

Remarks

The bound is sharp: some sequence of $(r - 1)(s - 1)$ distinct numbers has neither type of subsequence. For $r = s = 3$: each sequence of $5$ distinct numbers has a monotone subsequence of length $3$. A short proof labels each term with the lengths of the longest increasing and decreasing subsequences that end at it. The labels are distinct, and the pigeonhole principle finishes the proof.

History

Paul Erdős and George Szekeres proved the theorem in 1935.

Explanations

L1 human

A long enough list of different numbers always contains a long subsequence that goes up or one that goes down. The terms need not be adjacent. For example, $3, 1, 4, 5, 2$ has the increasing subsequence $3, 4, 5$.