Happy Ending problem

The Happy Ending problem (so named by Paul Erdős since it led to the marriage of George Szekeres and Esther Klein) is the following statement:

:Theorem. Any set of five points in the plane in general position [In this context, general position means that no two points coincide and no three points are collinear.] has a subset of four points that form the vertices of a convex quadrilateral.

This was one of the original results that led to the development of Ramsey theory.

The Happy Ending theorem can be proven by a simple case analysis: If four or more points are vertices of the convex hull, any four such points can be chosen. If on the other hand the point set has the form of a triangle with two points inside it, the two inner points and one of the triangle sides can be chosen. See Peterson (2000) for an illustrated explanation of this proof, and Morris and Soltan (2000) for a more detailed survey of the problem than we provide here.

The Erdős-Szekeres conjecture states precisely a more general relationship between the number of points in a general-position point set and its largest convex polygon. It remains unproven, but less precise bounds are known.

Larger polygons

Erdős and Szekeres (1935) proved the following generalisation:

:Theorem. For any positive integer "N", any sufficiently large finite set of points in the plane in general position has a subset of "N" points that form the vertices of a convex polygon.

The proof appeared in the same paper that proves the Erdős–Szekeres theorem on monotonic subsequences in sequences of numbers.

Denoting by "f"("N") the minimal possible "M" for a set of "M" points in general position must contain a convex "N"-gon, it is known that
* "f"(3) = 3, trivially.
* "f"(4) = 5. [This was the original problem, proved by Esther Klein.]
* "f"(5) = 9. [According to Erdős and Szekeres (1935), this was first proved by E. Makai; the first published proof appeared in Kalbfleisch et al (1970).] A set of eight points with no convex pentagon is shown in the illustration, demonstrating that "f"(5) > 8; the more difficult part of the proof is to show that every set of nine points in general position contains the vertices of a convex pentagon.
* "f"(6) = 17. [This has been proved by Szekeres and Lindsay Peters (2006). They carried out a computer search which eliminated all possible configurations of 17 points without convex hexagons while examining only a tiny fraction of all configurations.]
* The value of "f"("N") is unknown for all "N" > 6; by the result of Erdős and Szekeres (1935) it is known to be finite.

On the basis of the known values of "f"("N") for "N" = 3, 4 and 5, Erdős and Szekeres conjectured in their original paper that:$f(N)\; =\; 1\; +\; 2^\{N-2\}\; quad\; mbox\{for\; all\; \}\; N\; geq\; 3.$They proved later, by constructing explicit examples, that:$f(N)\; geq\; 1\; +\; 2^\{N-2\},$ [Erdős and Szekeres (1961)] but the best known upper bound when "N" ≥ 7 is:$f(N)\; leq\; \{2N-5\; choose\; N-3\}\; +\; 1\; =\; Oleft(frac\{4^N\}\{sqrt\; N\}\; ight).$ [Tóth and Valtr (2005). See binomial coefficient and Big O notation for notation used here and Catalan numbers or Stirling's approximation for the asymptotic expansion.]

Empty polygons

One may also consider the question of whether any sufficiently large set of points in general position has an "empty" quadrilateral, pentagon, etc.,that is, one that contains no other input point. The original solution to the Happy Ending problem can be adapted to show that any five points in general position have an empty convex quadrilateral, as shown in the illustration, and any ten points in general position have an empty convex pentagon. [Harborth (1978).] However, there exist arbitrarily large sets of points in general position that contain no empty heptagon. [Horton (1983)]

For a long time the question of the existence of empty hexagons remained open, but in 2005 Tobias Gerken [Gerken's proof has been [http://www.springerlink.com/content/h04hr51082j7u4k8/ published online] and will appear in "Discrete and Computational Geometry"; it is cited by Valtr (2006), by [http://www.math.nyu.edu/~pach/combin_seminar/fall_2005/varon092105abs.ps an NYU seminar announcement] , and in [http://kam.mff.cuni.cz/%7Ematousek/dg-err.html the errata to Matoušek's Lectures on Discrete Geometry] .] and Carlos M. Nicolás [Nicolás's proof has been published in "Discrete and Computational Geometry"; it was announced in a [http://www.math.uky.edu/~readdy/Seminar/2005_06/nicolas.html University of Kentucky discrete mathematics seminar] .] announced proofs that every sufficiently large point set in general position contains a convex empty hexagon. More specifically, Gerken showed that the number of points needed is no more than "f"(9) for the same function "f" defined above, while Nicolás showed that the number of points needed is no more than "f"(25). Valtr (2006) supplies a simplification of Gerken's proof that however requires more points, "f"(15) instead of "f"(9). At least 30 points are needed: there exists a set of 29 points in general position with no empty convex hexagon. [Overmars (2003).]

Other related problems

The problem of finding sets of "n" points minimizing the number of convex quadrilaterals is equivalent to minimizing the crossing number in a straight-line drawing of a complete graph. The number of quadrilaterals must be proportional to the fourth power of "n", but the precise constant is not known. [harvtxt|Scheinerman|Wilf|1994]

Notes

References

*cite journal
author = Chung, F.R.K.; Graham, R.L.
title = Forced convex n-gons in the plane
journal = Discrete and Computational Geometry
volume = 19
year = 1998
pages = 367–371
doi = 10.1007/PL00009353

*cite journal
author = Erdős, P.; Szekeres, G.
title = A combinatorial problem in geometry
journal = Compositio Math
volume = 2
year = 1935
pages = 463–470
url = http://www.numdam.org/item?id=CM_1935__2__463_0

*cite journal
author = Erdős, P.; Szekeres, G.
title = On some extremum problems in elementary geometry
journal = Ann. Univ. Sci. Budapest. Eötvös Sect. Math.
volume = 3–4
year = 1961
pages = 53–62 Reprinted in: cite book
author = Erdős, P.
title = The Art of Counting: Selected Writings
editor = J. Spencer, ed.
pages = 680–689
publisher = MIT Press
location = Cambridge, MA
year = 1973

*cite journal
author = Harborth, Heiko
title = Konvexe Fünfecke in ebenen Punktmengen
journal = Elem. Math.
volume = 33
year = 1978
issue = 5
pages = 116–118

*cite journal
author = Horton, J. D.
title = Sets with no empty convex 7-gons
journal = Canad. Math. Bull.
volume = 26
year = 1983
issue = 4
pages = 482–484

*cite journal
author = Kalbfleisch J.D.; Kalbfleisch J.G.; Stanton R.G.
title = A combinatorial problem on convex regions
journal = Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing, Louisiana State Univ., Baton Rouge, La., Congr. Numer.
volume = 1
year = 1970
pages = 180–188

*cite journal
author = Kleitman, D.J.; Pachter, L.
title = Finding convex sets among points in the plane
journal = Discrete and Computational Geometry
volume = 19
year = 1998
pages = 405–410
doi = 10.1007/PL00009358

*cite journal
author = Morris, W.; Soltan, V.
year = 2000
title = The Erdős-Szekeres problem on points in convex position—A survey
journal = Bulletin of the American Mathematical Society
volume = 37
url = http://www.ams.org/bull/2000-37-04/S0273-0979-00-00877-6/home.html
pages = 437–458
doi = 10.1090/S0273-0979-00-00877-6

*cite journal
author = Nicolás, C. M.
title = The Empty Hexagon Theorem
doi = 10.1007/s00454-007-1343-6
year = 2007
journal = Discrete and Computational Geometry
volume = 38
pages = 389–397

*cite journal
author = Overmars, M.
authorlink = Mark Overmars
title = Finding sets of points without empty convex 6-gons
year = 2003
journal = Discrete and Computational Geometry
volume = 29
pages = 153–158
doi = 10.1007/s00454-002-2829-x

*cite journal
author = Peterson, Ivars
title = Planes of Budapest
year = 2000
journal = MAA Online
url = http://www.maa.org/mathland/mathtrek_10_3_00.html

*citation|title=The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability|first1=Edward R.|last1=Scheinerman|first2=Herbert S.|last2=Wilf|journal=American Mathematical Monthly|volume=101|issue=10|year=1994|pages=939–943|doi=10.2307/2975158

*cite journal
author = Szekeres, G.; Peters, L.
title = Computer solution to the 17-point Erdős-Szekeres problem
year = 2006
journal = ANZIAM Journal
volume = 48
pages = 151–164
url = http://www.austms.org.au/Publ/ANZIAM/V48P2/2409.html

*cite journal
author = Tóth G.; Valtr, P.
title = Note on the Erdős-Szekeres theorem
journal = Discrete and Computational Geometry
volume = 19
year = 1998
pages = 457–459
doi = 10.1007/PL00009363

*cite conference
author = Tóth G.; Valtr, P.
title = The Erdős-Szekeres theorem: upper bounds and related results
booktitle = Combinatorial and computational geometry
pages = 557–568
publisher = Mathematical Sciences Research Institute Publications, no. 52
year = 2005

*cite web
author = Valtr, P.
title = On the empty hexagons
year = 2006
url = http://kam.mff.cuni.cz/~valtr/h.ps

External links

* [http://planetmath.org/encyclopedia/HappyEndingProblem.html Happy ending problem] and [http://planetmath.org/encyclopedia/RamseyTheoreticProofOfTheErdHosSzekeresTheorem.html Ramsey-theoretic proof of the Erdős-Szekeres theorem] on PlanetMath

*