happy ending problem
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  that .
For higher , Erdős and George Szekeres in 1935 gave the upper bound
Later, in 1961 they gave the lower bound .
New ideas for the upper bound were in the air in the late 1990s, with Chung and Graham showing that if , then
while Kleitman and Pachter showed that then
And Géza Tóth and Pavel Valtr in 1998 gave the upper bound
which in 2005 they refined to
- 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.
|Title||happy ending problem|
|Date of creation||2013-03-22 16:16:21|
|Last modified on||2013-03-22 16:16:21|
|Last modified by||PrimeFan (13766)|
|Synonym||happy end problem|