Erdős–Szekeres theorem  From Wikipedia, the free encyclopedia
Jump to: navigation, search 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 that makes precise one of the corollaries of
Ramsey's theorem. While Ramsey's theorem makes it easy to prove
that every 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 length at least (r − 1)(s − 1) + 1 contains
a monotonically increasing subsequence of length r or a
monotonically decreasing subsequence