Erdős–Szekeres Theorem

The Erdős–Szekeres Theorem is a classic result in combinatorics that guarantees the existence of a long monotonic subsequence in any sufficiently long sequence of distinct real numbers.

Statement

Let $m, n$ be positive integers. Then, any sequence of $mn + 1$ distinct real numbers contains either:

an increasing subsequence of length $m + 1$ , or
a decreasing subsequence of length $n + 1$ .

This result was first proved by Paul Erdős and George Szekeres in 1935.

Special Case

When $m = n$ , the theorem says that any sequence of $n^2 + 1$ distinct real numbers contains a monotonic subsequence of length $n + 1$ . This is the most common form in mathematical competitions and is especially useful in problems involving ordering and sequences.

Example

Any sequence of 5 distinct real numbers contains either:

an increasing subsequence of length 3, or
a decreasing subsequence of length 3.

This follows by setting $m = n = 2$ , so $mn + 1 = 5$ .

Proof

Consider a sequence of length $mn + 1$ of distinct real numbers: $a_1, a_2, \dots, a_{mn+1}.$

$[asy] // Asymptote image by aoum size(160); // Draw simple axes (thin gray lines) pen axisPen = gray(0.5); draw((0,0)--(6,0), axisPen); draw((0,0)--(0,6), axisPen); // Plot sequence points in blue pen pointPen = blue + 1.2; dot((1,3), pointPen); label("$a_1$", (0.8,3.2), NE); dot((2,1), pointPen); label("$a_2$", (2,1), NE); dot((3,4), pointPen); label("$a_3$", (2.8,4.2), NE); dot((4,2), pointPen); label("$a_4$", (4,2), NE); dot((5,5), pointPen); label("$a_5$", (5,5), NE); // Increasing subsequence in red pen incrPen = red + 1.3; draw((1,3)--(3,4)--(5,5), incrPen); dot((1,3), red + 3); dot((3,4), red + 3); dot((5,5), red + 3); label("Increasing subsequence", (3,5.7), red); // Decreasing subsequence in dark green pen decrPen = darkgreen + 1.3; draw((1,3)--(2,1), decrPen); dot((1,3), darkgreen + 3); dot((2,1), darkgreen + 3); label("Decreasing subsequence", (2,1), SW, darkgreen); // Axis labels label("$i$", (6,0), S); label("$a_i$", (0,6), W); [/asy]$

Visualization of a sequence of 5 distinct numbers illustrating an increasing subsequence of length 3 (in red) and a decreasing subsequence of length 2 (in green).

For each term $a_i$ , define two numbers: