Proof of the Erdos-Szekeres Bound

We prove the classical Erdos-Szekeres upper bound $R(s, t) \leq \binom{s + t - 2}{s - 1}$ using an elegant combinatorial argument that combines induction with Pascal's identity.

Statement

Theorem5.5Erdos-Szekeres Bound

For all integers $s, t \geq 1$ , $R(s, t) \leq \binom{s + t - 2}{s - 1}.$ In particular, $R(n, n) \leq \binom{2n - 2}{n - 1} < 4^n / \sqrt{\pi n}$ .

Proof

We proceed by induction on $s + t$ . The base cases are $R(s, 1) = R(1, t) = 1$ for all $s, t \geq 1$ , and $\binom{s - 1}{s - 1} = \binom{t - 1}{0} = 1$ .

For the inductive step, assume $s, t \geq 2$ and that $R(s - 1, t) \leq \binom{s + t - 3}{s - 2}$ and $R(s, t - 1) \leq \binom{s + t - 3}{s - 1}$ .

We first establish the recursive inequality: $R(s, t) \leq R(s - 1, t) + R(s, t - 1).$

Let $N = R(s - 1, t) + R(s, t - 1)$ and consider any 2-coloring of the edges of $K_N$ with colors red and blue. Fix a vertex $v$ and partition the remaining $N - 1$ vertices into:

$R = \{u : vu \text{ is red}\}$
$B = \{u : vu \text{ is blue}\}$

Since $|R| + |B| = N - 1 = R(s-1, t) + R(s, t-1) - 1$ , either $|R| \geq R(s-1, t)$ or $|B| \geq R(s, t-1)$ .

If $|R| \geq R(s-1, t)$ , then the coloring restricted to $R$ contains either a red $K_{s-1}$ (which with $v$ gives a red $K_s$ ) or a blue $K_t$ . If $|B| \geq R(s, t-1)$ , then the coloring restricted to $B$ contains either a red $K_s$ or a blue $K_{t-1}$ (which with $v$ gives a blue $K_t$ ).

Now apply the inductive hypothesis: $R(s, t) \leq R(s-1, t) + R(s, t-1) \leq \binom{s+t-3}{s-2} + \binom{s+t-3}{s-1} = \binom{s+t-2}{s-1},$ where the last step is Pascal's identity. $\square$

■

Asymptotic Analysis

ExampleDiagonal Case Asymptotics

Setting $s = t = n$ gives $R(n, n) \leq \binom{2n - 2}{n - 1} = \frac{(2n-2)!}{((n-1)!)^2}.$ By Stirling's approximation, $\binom{2n-2}{n-1} \sim \frac{4^{n-1}}{\sqrt{\pi(n-1)}}$ , so $R(n, n) = O(4^n / \sqrt{n})$ .

RemarkLower Bounds and the Gap

Erdos proved $R(n,n) \geq (1 + o(1)) \frac{n}{e\sqrt{2}} 2^{n/2}$ using the probabilistic method (1947). The gap between $c \cdot 2^{n/2}$ and $C \cdot 4^n/\sqrt{n}$ has been one of the most famous open problems in combinatorics. In 2023, Campos, Griffiths, Morris, and Sahasrabudhe achieved the first exponential improvement to the upper bound, showing $R(n,n) \leq (4 - \varepsilon)^n$ for some explicit $\varepsilon > 0$ .

RemarkAsymmetric Improvements

For $R(3, t)$ , much tighter bounds are known: $R(3, t) = \Theta(t^2 / \log t)$ . The upper bound follows from Shearer's entropy method and the lower bound from the triangle-free process (Bohman-Keevash, Fiz Pontiveros-Griffiths-Morris).