Erdős–Szekeres theorem

Example

For r = 3 and s = 2, the formula tells us that any permutation of three numbers has an increasing subsequence of length three or a decreasing subsequence of length two. Among the six permutations of the numbers 1,2,3:

Geometric interpretation

One can interpret the positions of the numbers in a sequence as x-coordinates of points in the Euclidean plane, and the numbers themselves as y-coordinates; conversely, for any point set in the plane, the y-coordinates of the points, ordered by their x-coordinates, forms a sequence of numbers (unless two of the points have equal x-coordinates). With this translation between sequences and point sets, the Erdős–Szekeres theorem can be interpreted as stating that in any set of at least rs − r − s + 2 points we can find a polygonal path of either r − 1 positive-slope edges or s − 1 negative-slope edges. In particular (taking r = s), in any set of at least n points we can find a polygonal path of at least ⌊√(n-1)⌋ edges with same-sign slopes. For instance, taking r = s = 5, any set of at least 17 points has a four-edge path in which all slopes have the same sign.

An example of rs − r − s + 1 points without such a path, showing that this bound is tight, can be formed by applying a small rotation to an (r − 1) by (s − 1) grid.

Permutation pattern interpretation

The Erdős–Szekeres theorem may also be interpreted in the language of permutation patterns as stating that every permutation of length at least rs + 1 must contain either the pattern 1, 2, 3, ..., r + 1 or the pattern s + 1, s, ..., 2, 1.

Proofs

The Erdős–Szekeres theorem can be proved in several different ways; Steele (1995) surveys six different proofs of the Erdős–Szekeres theorem, including the following two. Other proofs surveyed by Steele include the original proof by Erdős and Szekeres as well as those of Blackwell (1971), Hammersley (1972), and Lovász (1979).

Pigeonhole principle

Given a sequence of length (r − 1)(s − 1) + 1, label each number n_i in the sequence with the pair (a_i,b_i), where a_i is the length of the longest monotonically increasing subsequence ending with n_i and b_i is the length of the longest monotonically decreasing subsequence ending with n_i. Each two numbers in the sequence are labeled with a different pair: if i < j and n_i ≤ n_j then a_i < a_j, and on the other hand if n_i ≥ n_j then b_i < b_j. But there are only (r − 1)(s − 1) possible labels if a_i is at most r − 1 and b_i is at most s − 1, so by the pigeonhole principle there must exist a value of i for which a_i or b_i is outside this range. If a_i is out of range then n_i is part of an increasing sequence of length at least r, and if b_i is out of range then n_i is part of a decreasing sequence of length at least s.

Steele (1995) credits this proof to the one-page paper of Seidenberg (1959) and calls it "the slickest and most systematic" of the proofs he surveys.

Dilworth's theorem

Another of the proofs uses Dilworth's theorem on chain decompositions in partial orders, or its simpler dual (Mirsky's theorem).

To prove the theorem, define a partial ordering on the members of the sequence, in which x is less than or equal to y in the partial order if x ≤ y as numbers and x is not later than y in the sequence. A chain in this partial order is a monotonically increasing subsequence, and an antichain is a monotonically decreasing subsequence. By Mirsky's theorem, either there is a chain of length r, or the sequence can be partitioned into at most r − 1 antichains; but in that case the largest of the antichains must form a decreasing subsequence with length at least

Alternatively, by Dilworth's theorem itself, either there is an antichain of length s, or the sequence can be partitioned into at most s − 1 chains, the longest of which must have length at least r.