Happy Ending problem

From Wikipedia, the free encyclopedia

The Happy Ending problem: every set of five points in general position contains the vertices of a convex quadrilateral.

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^[1] 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.

1 Larger polygons
2 Empty polygons
3 Notes
4 References
5 External links

[edit] Larger polygons

A set of eight points in general position with no convex pentagon.

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 convex position must contain a convex N-gon, it is known that

f(3) = 3. This is trivial.
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 in work yet to be published. 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. It is remarkable that Szekeres was writing computer code in Fortran in his mid-nineties to carry out such a project.
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 (Erdős and Szekeres, 1961), by constructing explicit examples, that

$f(N) \geq 1 + 2^{N-2},$

but the best known upper bound when $N \geq 5$ is only

$f(N) \leq {2N-5 \choose N-3} + 1 = O\left(\frac{4^N}{\sqrt N}\right),$

due to Tóth and Valtr (2005)^[2].

[edit] 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 Harborth (1978) showed that any ten points in general position have an empty convex pentagon. 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 ^[3] and Carlos M. Nicolás^[4] 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). Overmars (2003) showed that at least 30 points are needed: there exists a set of 29 points in general position with no empty convex hexagon.

[edit] Notes

^ In this context, general position means that no two points coincide and no three points are collinear.
^ See binomial coefficient and Big O notation for notation used here and Catalan numbers or Stirling's approximation for the asymptotic expansion.
^ Gerken's proof will be published in Discrete and Computational Geometry; it is cited by Valtr (2006), by an NYU seminar announcement, and in the errata to Matoušek's Lectures on Discrete Geometry.
^ Nicolás's proof will also be published in Discrete and Computational Geometry; it was announced in a University of Kentucky discrete mathematics seminar.

[edit] References

Chung, F.R.K.; Graham, R.L. (1998). "Forced convex n-gons in the plane". Discrete and Computational Geometry 19: 367–371.

Erdős, P.; Szekeres, G. (1935). "A combinatorial problem in geometry". Compositio Math 2: 463–470.

Erdős, P.; Szekeres, G. (1961). "On some extremum problems in elementary geometry". Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 3–4: 53–62. Reprinted in: Erdős, P. (1973). J. Spencer, ed.: The Art of Counting: Selected Writings. Cambridge, MA: MIT Press, 680–689.

Harborth, Heiko (1978). "Konvexe Fünfecke in ebenen Punktmengen". Elem. Math. 33 (5): 116–118.

Horton, J. D. (1983). "Sets with no empty convex 7-gons". Canad. Math. Bull. 26 (4): 482–484.

Kalbfleisch J.D.; Kalbfleisch J.G.; Stanton R.G. (1970). "A combinatorial problem on convex regions". Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing, Louisiana State Univ., Baton Rouge, La., Congr. Numer. 1: 180–188.

Kleitman, D.J.; Pachter, L. (1998). "Finding convex sets among points in the plane". Discrete and Computational Geometry 19: 405–410.

Morris, W.; Soltan, V. (2000). "The Erdős-Szekeres problem on points in convex position—A survey". Bulletin of the American Mathematical Society 37: 437–458.

Overmars, M. (2003). "Finding sets of points without empty convex 6-gons". Discrete and Computational Geometry 29: 153–158.

Peterson, Ivars (2000). "Planes of Budapest". MAA Online.

Tóth G.; Valtr, P. (1998). "Note on the Erdős-Szekeres theorem". Discrete and Computational Geometry 19: 457–459.

Tóth G.; Valtr, P. (2005). "The Erdős-Szekeres theorem: upper bounds and related results". Combinatorial and computational geometry, 557–568, Mathematical Sciences Research Institute Publications, no. 52.