Suppose ,
,
and
,
...,
is a sequence of
real numbers. Then this sequence contains a monotonic
increasing (decreasing) subsequence of
terms or a monotonic
decreasing (increasing) subsequence of
terms. Dilworth's lemma
is a generalization of this theorem.
Erdős-Szekeres Theorem
See also
Combinatorics, Dilworth's LemmaExplore with Wolfram|Alpha
References
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 TheoremCite this as:
Weisstein, Eric W. "Erdős-Szekeres Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Erdos-SzekeresTheorem.html