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.
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)\le \left(\genfrac{}{}{0pt}{}{2n-4}{n-2}\right)+1.$$ |
Later, in 1961 they gave the lower bound $g(n)\ge 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\ge 4$, then
$$g(n)\le \left(\genfrac{}{}{0pt}{}{2n-4}{n-2}\right),$$ |
while Kleitman and Pachter showed that then
$$g(n)\le \left(\genfrac{}{}{0pt}{}{2n-4}{n-2}\right)+7-2n.$$ |
And Géza Tóth and Pavel Valtr in 1998 gave the upper bound
$$g(n)\le \left(\genfrac{}{}{0pt}{}{2n-5}{n-3}\right)+2,$$ |
which in 2005 they refined to
$$g(n)\le \left(\genfrac{}{}{0pt}{}{2n-5}{n-3}\right)+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 |