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

2 ^{n-2}+ 1<f(n)<(

2 n-4n-2) + 1 = O(4 ^{n}/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 alln.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)<(

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

n-7:

f(n)<(

2 n-4n-2) - 2 n+ 7Inspired by these results, Géza Toth and Pavel Valtr improved the upper bound by roughly a factor of two:

f(n)<(

2 n-5n-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 2^{n-2}+1 is the correct value off(n). They offered a $100 reward for the first proof thatf(n) = O((4-c)^{n}) for some positive constantc.A similar question, raised by Erdös, is whether there is a function

g(n) such that any set ofg(n) points in general position contains the vertices of anemptyconvexn-gon, that is, a convexn-gon with none of the points in its interior. It is easy to show thatand g(3) = 2; Harborth proved that g(4) = 4. Horton proved the surprising result that g(5) = 9g(7) isinfinite-- there arearbitrarily largesets of points in general position with no empty convex 7-gons! The status ofg(6) is still open. The current best lower bound, due to Overmars, Scholten, and Vincent, is, but no finite upper bound is known. g(6)>28

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