View source for Happy ending problem

{{Short description|Five coplanar points have a subset forming a convex quadrilateral}}
{{for|the Fred Frith album|The Happy End Problem}}
{{Redirect|Erdős–Szekeres conjecture|their theorem on monotonic subsequences|Erdős–Szekeres theorem}}

[[Image:Happy-End-problem.svg|thumb|300px|The happy ending problem: every set of five points in general position contains the vertices of a convex quadrilateral]]
In [[mathematics]], the "'''happy ending problem'''" (so named by [[Paul Erdős]] because it led to the marriage of [[George Szekeres]] and [[Esther Szekeres|Esther Klein]]<ref>[http://www.smh.com.au/news/obituaries/a-world-of-teaching-and-numbers--times-two/2005/11/06/1131211943674.html A world of teaching and numbers - times two], [[Michael Cowling]], [[The Sydney Morning Herald]], 2005-11-07, cited 2014-09-04</ref>) is the following statement:

{{math theorem | math_statement = any set of five points in the plane in [[general position]]<ref>In this context, general position means that no two points coincide and no three points are collinear.</ref> has a subset of four points that form the vertices of a [[convex polygon|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 convex hull 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 {{harvtxt|Peterson|2000}} for an illustrated explanation of this proof, and {{harvtxt|Morris|Soltan|2000}} for a more detailed survey of the problem.

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 subset forming a convex [[polygon]], namely that the smallest number of points for which any general position arrangement contains a convex subset of <math>n</math> points is <math>2^{n-2} + 1</math>. It remains unproven, but less precise bounds are known.

==Larger polygons==
[[Image:8-points-no-pentagon.svg|thumb|A set of eight points in general position with no convex pentagon]]
{{harvtxt|Erdős|Szekeres|1935}} proved the following generalisation:

{{math theorem | math_statement = for any positive [[integer]] {{mvar|N}}, any sufficiently large finite set of points in the plane in general position has a subset of {{mvar|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.

Let {{math|''f''(''N'')}} denote the minimum {{mvar|M}} for which any set of {{mvar|M}} points in general position must contain a convex ''N''-gon. It is known that
* {{math|1=''f''(3) = 3}}, trivially.
* {{math|1=''f''(4) = 5}}.<ref>This was the original problem, proved by Esther Klein.</ref>
* {{math|1=''f''(5) = 9}}.<ref>According to {{harvtxt|Erdős|Szekeres|1935}}, this was first proved by E. Makai; the first published proof appeared in {{harvtxt|Kalbfleisch|Kalbfleisch|Stanton|1970}}.</ref> A set of eight points with no convex [[pentagon]] is shown in the illustration, demonstrating that {{math|''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.
* {{math|1=''f''(6) = 17}}.<ref>This has been proved by {{harvtxt|Szekeres|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.</ref>
* The value of {{math|''f''(''N'')}} is unknown for all {{math|''N'' > 6}}. By the result of {{harvtxt|Erdős|Szekeres|1935}}, {{math|''f''(''N'')}} is known to be finite for all finite {{math|''N''}}.

On the basis of the known values of {{math|''f''(''N'')}} for ''N'' = 3, 4 and 5, Erdős and Szekeres [[conjecture]]d in their original paper that 
[[File:16nohexagon.svg|alt=A set of sixteen points in general position with no convex hexagon|thumb|A set of sixteen points in general position with no convex hexagon]]
<math display="block">f(N) = 1 + 2^{N-2} \quad \text{for all } N \geq 3.</math>
They proved later, by constructing explicit examples, that<ref>{{harvtxt|Erdős|Szekeres|1961}}</ref>
<math display="block">f(N) \geq 1 + 2^{N-2}.</math>
In 2016 Andrew Suk<ref>{{harvtxt|Suk|2016}}. See [[binomial coefficient]] and [[big O notation]] for notation used here and [[Catalan number]]s or [[Stirling's approximation]] for the asymptotic expansion.</ref> showed that for {{math|''N'' ≥ 7}}
<math display="block">f(N) \leq 2^{N + o(N)}.</math>

Suk actually proves, for N sufficiently large,  
<math display="block">f(N) \leq 2^{N + 6N^{2/3}logN}.</math>

This was subsequently improved to:{{sfnp|Holmsen|Mojarrad|Pach|Tardos|2020}}

<math display="block">f(N) \leq 2^{N + O(\sqrt{NlogN})}.</math>

==Empty convex polygons==
There is also the question of whether any sufficiently large set of points in general position has an "empty" convex 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.<ref>{{harvtxt|Harborth|1978}}.</ref> However, there exist arbitrarily large sets of points in general position that contain no empty convex [[heptagon]].<ref>{{harvtxt|Horton|1983}}</ref>

For a long time the question of the existence of empty [[hexagon]]s remained open, but {{harvtxt|Nicolás|2007}} and {{harvtxt|Gerken|2008}} proved 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). {{harvtxt|Valtr|2008}} 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.<ref>{{harvtxt|Overmars|2003}}.</ref> The question was finally answered by {{harvtxt|Heule|Scheucher|2024}}, who showed, using a SAT solving approach, that indeed every set of 30 points in general position contains an empty hexagon.

==Related problems==
The problem of finding sets of ''n'' points minimizing the number of convex quadrilaterals is equivalent to minimizing the [[Crossing number (graph theory)|crossing number]] in a straight-line [[graph drawing|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.<ref>{{harvtxt|Scheinerman|Wilf|1994}}</ref>

It is straightforward to show that, in higher-dimensional [[Euclidean space]]s, sufficiently large sets of points will have a subset of ''k'' points that forms the vertices of a [[convex polytope]], for any ''k'' greater than the dimension: this follows immediately from existence of convex {{nowrap|''k''-gons}} in sufficiently large planar point sets, by projecting the higher-dimensional point set into an arbitrary two-dimensional subspace. However, the number of points necessary to find ''k'' points in [[convex position]] may be smaller in higher dimensions than it is in the plane, and it is possible to find subsets that are more highly constrained. In particular, in ''d'' dimensions, every ''d''&nbsp;+&nbsp;3 points in general position have a subset of ''d''&nbsp;+&nbsp;2 points that form the vertices of a [[cyclic polytope]].<ref>{{harvtxt|Grünbaum|2003}}, Ex. 6.5.6, p.120. Grünbaum attributes this result to a private communication of Micha A. Perles.</ref> More generally, for every ''d'' and ''k''&nbsp;>&nbsp;''d'' there exists a number ''m''(''d'', ''k'') such that every set of ''m''(''d'', ''k'') points in general position has a subset of ''k'' points that form the vertices of a [[neighborly polytope]].<ref>{{harvtxt|Grünbaum|2003}}, Ex. 7.3.6, p. 126. This result follows by applying a Ramsey-theoretic argument similar to Szekeres's original proof together with Perles's result on the case ''k''&nbsp;=&nbsp;''d''&nbsp;+&nbsp;2.</ref>

==Notes==
{{Reflist|30em}}

==References==
{{Refbegin|30em}}
*{{citation
 | last1 = Chung | first1 = F.R.K. | author1-link = Fan Chung
 | last2 = Graham | first2 = R.L. | author2-link = Ronald Graham
 | doi = 10.1007/PL00009353
 | journal = [[Discrete and Computational Geometry]]
 | pages = 367–371
 | issue = 3
 | title = Forced convex n-gons in the plane
 | volume = 19
 | year = 1998| doi-access = free
 }}
*{{citation
 | last1 = Erdős
 | first1 = P.
 | author1-link = Paul Erdős
 | last2 = Szekeres
 | first2 = G.
 | author2-link = George Szekeres
 | journal = [[Compositio Mathematica]]
 | pages = 463–470
 | title = A combinatorial problem in geometry
 | url = http://www.numdam.org/item?id=CM_1935__2__463_0
 | volume = 2
 | year = 1935
 }}
*{{citation
 | last1 = Erdős | first1 = P. | author1-link = Paul Erdős
 | last2 = Szekeres | first2 = G. | author2-link = George Szekeres
 | journal = Ann. Univ. Sci. Budapest. Eötvös Sect. Math.
 | pages = 53–62
 | title = On some extremum problems in elementary geometry
 | volume = 3–4
 | year = 1961}}; reprinted in {{citation
 | last = Erdős | first = P. | author-link = Paul Erdős
 | editor-last = Spencer | editor-first = J.
 | location = Cambridge, MA
 | pages = 680–689
 | publisher = MIT Press
 | title = The Art of Counting: Selected Writings
 | year = 1973}}
*{{citation
 | last = Gerken | first = Tobias
 | doi = 10.1007/s00454-007-9018-x
 | issue = 1–3
 | journal = [[Discrete and Computational Geometry]]
 | pages = 239–272
 | title = Empty convex hexagons in planar point sets
 | volume = 39
 | year = 2008| doi-access = free
 }}
*{{citation
 | last = Grünbaum | first = Branko | authorlink = Branko Grünbaum
 | edition = 2nd
 | editor1-last = Kaibel | editor1-first = Volker
 | editor2-last = Klee | editor2-first = Victor | editor2-link = Victor Klee
 | editor3-last = Ziegler | editor3-first = Günter M. | editor3-link = Günter M. Ziegler
 | isbn = 0-387-00424-6
 | publisher = [[Springer-Verlag]]
 | series = Graduate Texts in Mathematics
 | title = Convex Polytopes
 | title-link = Convex Polytopes
 | volume = 221
 | year = 2003}}
*{{citation
 | last = Harborth | first = Heiko
 | issue = 5
 | journal = [[Elemente der Mathematik]]
 | pages = 116–118
 | title = Konvexe Fünfecke in ebenen Punktmengen
 | volume = 33
 | year = 1978}}
*{{citation
 | last1 = Heule | first1 = Marijn J. H.
 | last2 = Scheucher | first2 = Manfred
 | contribution = Happy Ending: An Empty Hexagon in Every Set of 30 Points
 | editor1-last = Finkbeiner | editor1-first = Bernd
 | editor2-last = Kovács | editor2-first = Laura
 | pages = 61–80
 | title = Tools and Algorithms for the Construction and Analysis of Systems
 | volume = 14570
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | doi = 10.1007/978-3-031-57246-3_5
 | doi-access = free
 | year = 2024| arxiv = 2403.00737
 | isbn = 978-3-031-57245-6
 }}
*{{citation
 | last1 = Holmsen | first1 = Andreas F.
 | last2 = Mojarrad | first2 = Hossein Nassajian
 | last3 = Pach | first3 = János | author3-link = János Pach
 | last4 = Tardos | first4 = Gábor
 | arxiv = 1710.11415
 | doi = 10.4171/jems/1000
 | issue = 12
 | journal = Journal of the European Mathematical Society (JEMS)
 | mr = 4176784
 | pages = 3981–3995
 | title = Two extensions of the Erdős–Szekeres problem
 | volume = 22
 | year = 2020}}
*{{citation
 | doi = 10.4153/CMB-1983-077-8
 | last = Horton | first = J. D.
 | issue = 4
 | journal = [[Canadian Mathematical Bulletin]]
 | pages = 482–484
 | title = Sets with no empty convex 7-gons
 | volume = 26
 | year = 1983| s2cid = 120267029 | doi-access = free
 }}
*{{citation
 | last1 = Kalbfleisch | first1 = J.D.
 | last2 = Kalbfleisch | first2 = J.G. |author2-link = James G. Kalbfleisch
 | last3 = Stanton | first3 = R.G.
 | title = Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing
 | publisher = Louisiana State Univ.
 | location = Baton Rouge, La.
 | series = Congressus Numerantium
 | pages = 180–188
 | contribution = A combinatorial problem on convex regions
 | volume = 1
 | year = 1970}}
*{{citation
 | last1 = Kleitman
 | first1 = D.J.
 | author1-link = Daniel Kleitman
 | last2 = Pachter
 | first2 = L.
 | author2-link = Lior Pachter
 | doi = 10.1007/PL00009358
 | journal = [[Discrete and Computational Geometry]]
 | pages = 405–410
 | issue = 3
 | title = Finding convex sets among points in the plane
 | volume = 19
 | year = 1998
 | doi-access = free
 }}
*{{citation
 | last1 = Morris | first1 = W.
 | last2 = Soltan | first2 = V.
 | doi = 10.1090/S0273-0979-00-00877-6
 | journal = [[Bulletin of the American Mathematical Society]]
 | pages = 437–458
 | title = The Erdős-Szekeres problem on points in convex position—A survey
 | issue = 4
 | volume = 37
 | year = 2000| doi-access = free
 }}
*{{citation
 | last = Nicolás | first = Carlos M.
 | doi = 10.1007/s00454-007-1343-6
 | issue = 2
 | journal = [[Discrete and Computational Geometry]]
 | pages = 389–397
 | title = The empty hexagon theorem
 | volume = 38
 | year = 2007| doi-access = free
 }}
*{{citation
 | last = Overmars | first = M. | author-link = Mark Overmars
 | doi = 10.1007/s00454-002-2829-x
 | journal = [[Discrete and Computational Geometry]]
 | pages = 153–158
 | title = Finding sets of points without empty convex 6-gons
 | issue = 1
 | volume = 29
 | year = 2003| doi-access = free
 }}
*{{citation
 | last = Peterson
 | first = Ivars
 | authorlink = Ivars Peterson
 | journal = MAA Online
 | title = Planes of Budapest
 | url = http://www.maa.org/mathland/mathtrek_10_3_00.html
 | archive-url = https://web.archive.org/web/20130702060326/http://www.maa.org/mathland/mathtrek_10_3_00.html
 | archive-date = 2013-07-02
 | url-status = dead
 | year = 2000
 }}
*{{citation
 | last1 = Scheinerman | first1 = Edward R. | author1-link = Ed Scheinerman
 | last2 = Wilf | first2 = Herbert S. | author2-link = Herbert Wilf
 | doi = 10.2307/2975158
 | issue = 10
 | journal = [[American Mathematical Monthly]]
 | pages = 939–943
 | title = The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability
 | volume = 101
 | year = 1994
 | publisher = Mathematical Association of America
 | jstor = 2975158}}
*{{citation
 | last = Suk | first = Andrew
 | doi = 10.1090/jams/869
 | journal = J. Amer. Math. Soc.
 | title = On the Erdős–Szekeres convex polygon problem
 | year = 2016
 | volume = 30
 | issue = 4
 | pages = 1047–1053
 | arxiv=1604.08657| s2cid = 15732134
 }}
*{{citation
 | last1 = Szekeres
 | first1 = G.
 | author1-link = George Szekeres
 | last2 = Peters
 | first2 = L.
 | doi = 10.1017/S144618110000300X
 | journal = [[ANZIAM Journal]]
 | pages = 151–164
 | title = Computer solution to the 17-point Erdős-Szekeres problem
 | issue = 2
 | volume = 48
 | year = 2006
 | doi-access = free
 }}
*{{citation
 | last1 = Tóth | first1 = G.
 | last2 = Valtr | first2 = P.
 | doi = 10.1007/PL00009363
 | journal = [[Discrete and Computational Geometry]]
 | pages = 457–459
 | title = Note on the Erdős-Szekeres theorem
 | issue = 3
 | volume = 19
 | year = 1998| doi-access = free
 }}
*{{citation
 | last1 = Tóth
 | first1 = G.
 | last2 = Valtr
 | first2 = P.
 | contribution = The Erdős-Szekeres theorem: upper bounds and related results
 | pages = 557–568
 | series = Mathematical Sciences Research Institute Publications
 | volume = 52
 | publisher = Cambridge University Press
 | title = Combinatorial and Computational Geometry
 | url = http://library.msri.org/books/Book52/files/30toth.pdf
 | editor1-first = Jacob E.
 | editor1-last = Goodman
 | editor1-link = Jacob E. Goodman
 | editor2-first = János
 | editor2-last = Pach
 | editor2-link = János Pach
 | editor3-first = Emo
 | editor3-last = Welzl
 | editor3-link = Emo Welzl
 | year = 2005
 | access-date = 2015-02-28
 | archive-date = 2019-07-28
 | archive-url = https://web.archive.org/web/20190728224026/http://library.msri.org/books/Book52/files/30toth.pdf
 | url-status = dead
 }}
*{{citation
 | last = Valtr
 | first = P.
 | contribution = On empty hexagons
 | pages = 433–442
 | url = http://kam.mff.cuni.cz/~valtr/h.ps
 | year = 2008
 | title = Surveys on Discrete and Computational Geometry: Twenty Years Later: AMS-IMS-SIAM Joint Summer Research Conference, June 18-22, 2006, Snowbird, Utah
 | volume = 453
 | series = Contemporary Mathematics
 | publisher = American Mathematical Society
 | editor1-first = Jacob E.
 | editor1-last = Goodman
 | editor1-link = Jacob E. Goodman
 | editor2-first = János
 | editor2-last = Pach
 | editor2-link = János Pach
 | editor3-first = Richard
 | editor3-last = Pollack
 | editor3-link = Richard M. Pollack
 | isbn = 9780821842393
 }}
{{Refend}}

==External links==
* [https://web.archive.org/web/20060925032614/http://planetmath.org/encyclopedia/HappyEndingProblem.html Happy ending problem] and [https://web.archive.org/web/20060925032736/http://planetmath.org/encyclopedia/RamseyTheoreticProofOfTheErdHosSzekeresTheorem.html Ramsey-theoretic proof of the Erdős-Szekeres theorem] on [[PlanetMath]]
*{{mathworld | urlname = HappyEndProblem | title = Happy End Problem|mode=cs2}}

[[Category:Discrete geometry]]
[[Category:Euclidean plane geometry]]
[[Category:Quadrilaterals]]
[[Category:Polygons]]
[[Category:Mathematical problems]]
[[Category:Ramsey theory]]
[[Category:Paul Erdős]]