Erdős-Szekeres Theorem

Combinatorics · Axiom Academy

A beautiful result about monotone subsequences in sequences of distinct numbers The Erdős-Szekeres theorem states: Any sequence of more than (r-1)(s-1) distinct numbers contains either an increasing subsequence of length r or a decreasing subsequence of length s. Let's visualize this with a concrete example. Consider a sequence of 9 numbers (more than (3-1)(3-1) = 4). We'll show it must contain either an increasing subsequence of length 3 or a decreasing subsequence of length 3. 2. The Pigeonhole Principle Setup For each position i in our sequence, we assign an ordered pair (L i , D i ) where: L i = length of the longest increasing subsequence ending at position i D i = length of the longest decreasing subsequence ending at position i The key insight: If neither an increasing subsequence of length r nor a decreasing subsequence of length s exists, then all these pairs (L i , D i ) must come from a restricted set. 3. Applying the Pigeonhole Principle Suppose neither subsequence exists. Then for all i: L i ≤ r-1 and D i ≥ s-1. This means each pair (L i , D i ) belongs to the set 1, 2, ..., r-1 × 1, 2, ..., s-1 , which has exactly (r-1)(s-1) possible pairs. The crucial observation: All pairs must be distinct! If position i comes before position j, then either a i < a j (making L j > L i ) or a i > a j (making D j > D i ). We have more than (r-1)(s-1) positions in our sequence, each needing a distinct pair from a set of exactly (r-1)(s-1) possible pairs.

This is the written version of the interactive lesson above. See the full Combinatorics course.