Erdős-Szekeres Theorem

Suppose a,b in N, n=ab+1, and x_1, ..., x_n is a sequence of n real numbers. Then this sequence contains a monotonic increasing (decreasing) subsequence of a+1 terms or a monotonic decreasing (increasing) subsequence of b+1 terms. Dilworth's lemma is a generalization of this theorem.

See also

Combinatorics, Dilworth's Lemma

Explore with Wolfram|Alpha


Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth. New York: Hyperion, pp. 54-55, 1998.

Referenced on Wolfram|Alpha

Erdős-Szekeres Theorem

Cite this as:

Weisstein, Eric W. "Erdős-Szekeres Theorem." From MathWorld--A Wolfram Web Resource.

Subject classifications