- Happy Ending problem
The

**Happy Ending problem**(so named byPaul Erdős since it led to the marriage ofGeorge Szekeres and Esther Klein) is the following statement::

**Theorem.**Any set of five points in the plane ingeneral 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 convexquadrilateral .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 positiveinteger "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 andBig O notation for notation used here andCatalan number s orStirling'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 emptyheptagon . [*Horton (1983)*]For a long time the question of the existence of empty

hexagon s remained open, but in 2005 Tobias Gerken [*Gerken's proof has been [*] and Carlos M. Nicolás [*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*] .*Nicolás's proof has been published in "Discrete and Computational Geometry"; it was announced in a [*] 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. [*http://www.math.uky.edu/~readdy/Seminar/2005_06/nicolas.html University of Kentucky discrete mathematics seminar*] .*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 acomplete 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*] onPlanetMath *

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Happy ending (disambiguation)**— Happy ending may refer to: * Happy ending in fiction, when everything turns out well in the end * Happy Ending (story), a science fiction story by Henry Kuttner * Happy Ending (song), a ballad by London based singer Mika * Happy Ending (Fredric… … Wikipedia**Problem plays (Shakespeare)**— In Shakespeare studies, the term problem plays normally refers to three plays that William Shakespeare wrote between the late 1590s and the first years of the seventeenth century: All s Well That Ends Well , Measure for Measure and Troilus and… … Wikipedia**Happy Seven**— Infobox animanga/Header name = Happy 7 caption = ja name = はっぴぃセブン ～ざ・テレビまんが～ ja name trans = Happy 7 The TV Manga genre = FantasyInfobox animanga/Novel light = yes title = author = Hiroyuki Kawasaki illustrator = COM publisher = flagicon|Japan… … Wikipedia**Problem of evil**— Part of a series on God General conceptions … Wikipedia**Happy Mondays**— Infobox musical artist 2 Name = Happy Mondays Img capt = Happy Mondays in 2007 Background = group or band Birth name = Alias = Born = Died = Origin = Little Hulton, Greater Manchester, England Instrument = Genre = Alternative dance Alternative… … Wikipedia**Twist ending**— A twist ending or surprise ending is an unexpected conclusion or climax to a work of fiction, and which often contains irony or causes the audience to reevaluate the narrative or characters. A twist ending is the conclusive form of plot twists.… … Wikipedia**List of Happy Tree Friends characters**— This is a list of fictional characters from Happy Tree Friends. There are 22 main characters, and some other supporting characters. To celebrate the 10th anniversary of the series in 2010, the creators of Happy Tree Friends announced that there… … Wikipedia**B. Happy**— (1999) was a Cartoon Network World Premiere Toons series Originally produced in Flash 3.0 by Funny Garbage. The series lasted four episodes and ran 24 hours a day on cartoonnetwork.com from 1999 ndash;2003. In each episode B. Happy, a reluctant… … Wikipedia**George Szekeres**— Infobox Scientist name = George Szekeres |300px image width = 300px caption = George Szekeres, 2001 birth date = birth date|1911|5|29|mf=y birth place = Budapest, Hungary death date = death date and age|2005|8|28|1911|5|29|mf=y death place =… … Wikipedia**Открытые математические проблемы**— Открытые (нерешённые) математические проблемы проблемы, которые рассматривались математиками, но до сих пор не решены. Часто имеют форму гипотез, которые предположительно верны, но нуждаются в доказательстве. В научном мире популярна… … Википедия