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 position are sufficient to create a triangle. For $n=4$ , Paul Erdős and Esther Klein (later Szekeres) determined that at least five points are necessary, and Kalbfleisch later determined $g(5)=9$ . Much later, George Szekeres (posthumously) and Lindsay Peters published a computer proof [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.

Title	happy ending problem
Canonical name	HappyEndingProblem
Date of creation	2013-03-22 16:16:21
Last modified on	2013-03-22 16:16:21
Owner	PrimeFan (13766)
Last modified by	PrimeFan (13766)
Numerical id	13
Author	PrimeFan (13766)
Entry type	Definition
Classification	msc 51D20
Synonym	happy end problem