Forced Convex Subsets

[The Erdös-Szekeres "Happy End" Problem]

In 1933, Esther Klein asked whether there was a function f(n) such that every set of f(n) points in general position in the plane must contain the vertices of a convex n-gon. Paul Erdös and György Szekeres answered this question affirmatively by deriving the following bounds:

2n-2 + 1 < f(n) < (
 2n-4 n-2
) + 1 = O(4n/sqrt{n})

(Esther Klein and György Szekeres were married soon after the upper bound was proved; hence, Erdös referred to it as the "happy end theorem".) The lower bound is sharp for all n<6, and Erdös and Szekeres conjectured that it is sharp for all n.

These were the best bounds known for over 60 years. Finally, in 1996, Fan Chung and Ron Graham improved the upper bound by 1:

f(n) < (
 2n-4 n-2
)

This modest result apparently opened the floodgates to further improvement. Daniel Kleitman and Lior Pachter soon improved the bound by 2n-7:

f(n) < (
 2n-4 n-2
) - 2n + 7

Inspired by these results, Géza Toth and Pavel Valtr improved the upper bound by roughly a factor of two:

f(n) < (
 2n-5 n-2
) + 2

This is the current record. To quote Kleitman and Pachter:

[Chung and Graham's] modest improvement is like a drop of water that appears downstream from a dam. This drop can be a harbinger of a trickle, then perhaps a stream, and finally the dam may collapse with a rush of water. It is the purpose of [our] paper to replace the Chung-Graham drop with a trickle. Géza Toth and Pavel Valtr have recently replaced out trickle with a stream by further improving the upper bound.
Chung and Graham again conjectured that the lower bound 2n-2+1 is the correct value of f(n). They offered a \$100 reward for the first proof that f(n) = O((4-c)n) for some positive constant c.

A similar question, raised by Erdös, is whether there is a function g(n) such that any set of g(n) points in general position contains the vertices of an empty convex n-gon, that is, a convex n-gon with none of the points in its interior. It is easy to show that g(3) = 2 and g(4) = 4; Harborth proved that g(5) = 9. Horton proved the surprising result that g(7) is infinite -- there are arbitrarily large sets of points in general position with no empty convex 7-gons! The status of g(6) is still open. The current best lower bound, due to Overmars, Scholten, and Vincent, is g(6) > 28, but no finite upper bound is known.

Open Problems - Jeff Erickson (jeffe@cs.uiuc.edu) 23 Jul 1998