The happy ending problem asks, for a given integer , to find the smallest number of points laid on a plane in general position such that a subset of points can be made the vertices of a convex -agon.

Figure 1: Examples showing that .

It is obvious that for , just three points in general position are sufficient to create a triangle. For , Paul Erdős and Esther Klein (later Szekeres) determined that at least five points are necessary, and Kalbfleisch later determined . Much later, George Szekeres (posthumously) and Lindsay Peters published a computer proof [6] that .

For higher , Erdős and George Szekeres in 1935 gave the upper bound

New ideas for the upper bound were in the air in the late 1990s, with Chung and Graham showing that if , then

Bibliography

1

F. R. K. Chung and R. L. Graham, Forced convex -gons in the plane, Discrete Comput. Geom. 19 (1996), 229-233.

2

P. Erdős and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463-470.

3

P. Erdős and G. Szekeres, On some extremum problems in elementary geometry, Ann. Univ. Sci. Budapest Eötvös Sect. Math. 3-4 (1961), 53-62.

4

D. Kleitman and L. Pachter, Finding convex sets among points in the plane, Discrete Comput. Geom. 19 (1998), 405-410.

5

W. Morris and V. Soltan, The Erdős-Szekeres problem on points in convex position - a survey, Bull. Amer. Math. Soc. 37 (2000), 437-458.

6

L. Peters and G. Szekeres, Computer solution to the 17-point Erdős-Szekeres problem, ANZIAM J. 48 (2006), 151-164.

7

G. Tóth and P. Valtr, Note on the Erdős-Szekeres theorem, Discrete Comput. Geom. 19 (1998), 457-459.

8

G. Tóth and P. Valtr, The Erdős-Szekeres theorem: upper bounds and related results. Appearing in J. E. Goodman, J. Pach, and E. Welzl, eds., Combinatorial and computational geometry, Mathematical Sciences Research Institute Publications 52 (2005) 557-568.