Happy Ending problem


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

*


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

  • Открытые математические проблемы — Открытые (нерешённые) математические проблемы  проблемы, которые рассматривались математиками, но до сих пор не решены. Часто имеют форму гипотез, которые предположительно верны, но нуждаются в доказательстве. В научном мире популярна… …   Википедия


We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.