Erdős–Szekeres theorem

From Wikipedia, the free encyclopedia

A path of four positively sloped edges in a set of 17 points. If one forms a sequence of the y-coordinates of the points, in order by their x-coordinates, the Erdős–Szekeres theorem ensures that there exists either a path of this type or one the same length in which all slopes are ≤ 0. However, if the central point is omitted, no such path would exist.

In mathematics, the Erdős–Szekeres theorem is a finitary result, which makes precise one of the corollaries of Ramsey's theorem. While Ramsey's theorem makes it easy to prove that any sequence of distinct real numbers contains either a monotonically increasing infinite subsequence, or a monotonically decreasing infinite subsequence, the result proved by Paul Erdős and George Szekeres goes further. For given r, s they showed that any sequence of length at least

rs − r − s + 2

contains either a monotonically increasing subsequence of length r, or a monotonically decreasing subsequence of length s. The proof appeared in the same 1935 paper that mentions the Happy Ending problem. Steele (1995) contains "six or more" proofs of the theorem.

1 Example
2 Geometric interpretation
3 Proof by the Pigeonhole principle
4 Proof via Dilworth's theorem
5 See also
6 References
7 External links

[edit] 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:

1,2,3 has an increasing subsequence consisting of all three numbers
1,3,2 has a decreasing subsequence 3,2
2,1,3 has a decreasing subsequence 2,1
2,3,1 has two decreasing subsequences, 2,1 and 3,1
3,1,2 has two decreasing subsequences, 3,1 and 3,2
3,2,1 has three decreasing length-2 subsequences, 3,2, 3,1, and 2,1.

[edit] 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. 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. 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.

[edit] Proof by the Pigeonhole principle

We prove the theorem by contradiction. We label each number, $n i$ , in the sequence with a 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$ . If we don't have a monotonically increasing or decreasing subsequence of the desired length, then each $a i$ is between 1 and $r - 1$ and each $b i$ is between 1 and $s - 1$ . So, there are $(r - 1)(s - 1) = r s - r - s + 1$ possible $(a i, b i)$ pairs. Since there are $r s - r - s + 2$ numbers in the sequence, the Pigeonhole principle guarantees that two numbers in the sequence, say $n j$ and $n k$ , have the same $(a i, b i)$ pairs. However, this is impossible for the following reason. Assume $j < k$ . If $n_j \leq n_k$ , then we can append $n k$ to the monotonically increasing subsequence ending at $n j$ to get a longer monotonic subsequence. If $n_j \geq n_k$ , then we can append $n k$ to the monotonically decreasing subsequence ending at $n j$ to get a longer monotonic subsequence. In each case, we reach a contradiction. So the assumption that we didn't have a monotonic subsequence of the desired length was false. This proves the theorem.

[edit] Proof via Dilworth's theorem

The Erdős–Szekeres theorem can be proved in several different ways; one of the proofs uses Dilworth's theorem on chain decompositions in partial orders, or its simpler dual.

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 the dual of Dilworth'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

$\left\lceil\frac{rs-r-s+2}{r-1}\right\rceil=s.$

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.

[edit] See also

Longest increasing subsequence problem

[edit] References

Erdős, Paul; Szekeres, George (1935). "A combinatorial problem in geometry". Compositio Mathematica 2: 463–470.

Steele, J. Michael (1995). "Variations on the monotone subsequence problem of Erdős and Szekeres". Aldous, Diaconis, and Steele, eds. Discrete Probability and Algorithms: 111–132, New York: Springer-Verlag.