info prev up next book cdrom email home

Erdös-Szekeres Theorem

Suppose $a$, $b \in \Bbb{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

© 1996-9 Eric W. Weisstein