In mathematics, the **Erdős–Szekeres theorem** is a finitary result that makes precise one of the corollaries of Ramsey's theorem. While Ramsey's theorem makes it easy to prove that every infinite sequence of distinct real numbers contains 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 distinct real numbers with length at least (*r* − 1)(*s* − 1) + 1 contains 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.^{[1]}

## 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.

## Alternative interpretations

### 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.^{[2]}
Other proofs surveyed by Steele include the original proof by Erdős and Szekeres as well as those of Blackwell (1971),^{[3]} Hammersley (1972),^{[4]} and Lovász (1979).^{[5]}

### 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*), where

_{i}*a*is the length of the longest monotonically increasing subsequence ending with

_{i}*n*and

_{i}*b*is the length of the longest monotonically decreasing subsequence ending with

_{i}*n*. Each two numbers in the sequence are labeled with a different pair: if

_{i}*i*<

*j*and

*n*≤

_{i}*n*then

_{j}*a*<

_{i}*a*, and on the other hand if

_{j}*n*≥

_{i}*n*then

_{j}*b*<

_{i}*b*. But there are only (

_{j}*r*− 1)(

*s*− 1) possible labels if

*a*is at most

_{i}*r*− 1 and

*b*is at most

_{i}*s*− 1, so by the pigeonhole principle there must exist a value of

*i*for which

*a*or

_{i}*b*is outside this range. If

_{i}*a*is out of range then

_{i}*n*is part of an increasing sequence of length at least

_{i}*r*, and if

*b*is out of range then

_{i}*n*is part of a decreasing sequence of length at least

_{i}*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.^{[2]}^{[6]}

### 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*.

### Application of the Robinson–Schensted correspondence

The result can also be obtained as a corollary of the Robinson–Schensted correspondence.

Recall that the Robinson–Schensted correspondence associate to each sequence a Young tableau *P* whose entries are the values of the sequence. The tableau *P* has the following properties:

- The length of the longest increasing subsequence is equal to the length of the first row of
*P*. - The length of the longest decreasing subsequence is equal to the length of the first column of
*P*.

Now, it is not possible to fit (*r* − 1)(*s* − 1) + 1 entries in a square box of size (*r* − 1)(*s* − 1), so that either the first row is of length at least *r* or the last row is of length at least *s*.

## See also

## References

**^**Erdős, Paul; Szekeres, George (1935), "A combinatorial problem in geometry",*Compositio Mathematica*,**2**: 463–470, doi:10.1007/978-0-8176-4842-8_3, Zbl 0012.27010.- ^
^{a}^{b}Steele, J. Michael (1995), "Variations on the monotone subsequence theme of Erdős and Szekeres", in Aldous, David; Diaconis, Persi; Spencer, Joel; Steele, J. Michael (eds.),*Discrete Probability and Algorithms*(PDF), IMA Volumes in Mathematics and its Applications,**72**, Springer-Verlag, pp. 111–131, ISBN 0-387-94532-6. **^**Blackwell, Paul (1971), "An alternative proof of a theorem of Erdős and Szekeres",*American Mathematical Monthly*,**78**(3): 273–273, doi:10.2307/2317525, JSTOR 2317525.**^**Hammersley, J. M. (1972), "A few seedlings of research",*Proc. 6th Berkeley Symp. Math. Stat. Prob.*, University of California Press, pp. 345–394. As cited by Steele (1995).**^**Lovász, László (1979), "Solution to Exercise 14.25",*Combinatorial Problems and Exercises*, North-Holland. As cited by Steele (1995).**^**Seidenberg, A. (1959), "A simple proof of a theorem of Erdős and Szekeres" (PDF),*Journal of the London Mathematical Society*,**34**: 352, doi:10.1112/jlms/s1-34.3.352^{[dead link]}.