Erdős–Szekeres theorem

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.

If ai is out of range then ni is part of an increasing sequence of length at least r, and if bi is out of range then ni is part of a decreasing sequence of length at least 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.

A path of four upward-sloping edges in a set of 17 points. By the Erdős–Szekeres theorem, every set of 17 points has a path of this length that slopes either upward or downward. The 16-point subset with the central point removed has no such path.