happy ending problem

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

Figure 1: Examples showing that $g(4)\\leq 5$ .

It is obvious that for $n=3$ , just three points in general positionare sufficient to create a triangle. For $n=4$ , Paul Erdős andEsther Klein (later Szekeres) determined that at least five points arenecessary, and Kalbfleisch later determined $g(5)=9$ . Much later,George Szekeres (posthumously) and Lindsay Peters published a computerproof [6] that $g(6)=17$ .

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

g(n)\\leq\\binom{2n-4}{n-2}+1.

Later, in 1961 they gave the lower bound $g(n)\\geq 1+2^{n-2}$ .

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

g(n)\\leq\\binom{2n-4}{n-2},

while Kleitman and Pachter showed that then

g(n)\\leq\\binom{2n-4}{n-2}+7-2n.

And Géza Tóth and Pavel Valtr in 1998 gave the upper bound

g(n)\\leq{2n-5\\choose n-3}+2,

which in 2005 they refined to

g(n)\\leq\\binom{2n-5}{n-3}+1.

References

1 F. R. K. Chung and R. L. Graham, Forced convex $n$ -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.