En uppgift med ett lyckligt slut

Ett problem med ett lyckligt slut är påståendet att varje uppsättning av fem pekar på planet i allmänt läge [1] har en delmängd av fyra punkter som är hörn av en konvex fyrhörning .

Historik

Detta resultat av kombinatorisk geometri kallas av Pal Erdős för ett "problem med ett lyckligt slut", eftersom lösningen av problemet slutade med György Sekeres och Esther Kleins bröllop ( Hung. Eszter Klein ). Även känd som Erdős-Szekeres konvexa polygonsats .

Generaliseringar av resultatet till ett godtyckligt antal punkter är av intresse för matematiker från 1900- och 2000-talen.

Bevis

Om minst fyra punkter bildar ett konvext skrov , kan vilken uppsättning av fyra skrovpunkter som helst väljas som en konvex fyrhörning. Annars finns det en triangel och två punkter inuti den. En rät linje som går genom två inre punkter skär inte en av triangelns sidor på grund av punkternas allmänna position. Topparna på denna sida och två inre punkter bildar en konvex fyrhörning.

Polygoner med ett godtyckligt antal hörn

Erdős och Szekeres generaliserade detta resultat till ett godtyckligt antal poäng, en ursprunglig utveckling av Ramsey-teorin . De lade också fram "Erdős-Szekeres-förmodan" - en exakt formel för det maximala antalet hörn av en konvex polygon som måste finnas i en uppsättning av ett givet antal punkter i allmän position.

I ( Erdős & Szekeres 1935 ) bevisades följande generalisering: för alla naturliga , varje tillräckligt stor uppsättning punkter i allmän position på planet har en delmängd av punkter som är hörn av en konvex polygon. Detta bevis förekom i samma artikel där Erdős-Szekeres sats om monotona delsekvenser i numeriska sekvenser bevisas. $N$ $N$

Ställ in storlek som en funktion av antalet polygonhörn

Låt beteckna det minimum för vilket en uppsättning punkter i allmän position innehåller en konvex -gon. Det är känt att: $f(N)$ $M$ $M$ $N$

$f(3)=3$ , självklart.
$f(4)=5$ , bevisade Esther Sekeres.
$f(5)=9$ , enligt ( Erdős & Szekeres 1935 ), var E. Makai den första att bevisa detta; det första publicerade beviset dök upp i ( Kalbfleisch, Kalbfleisch & Stanton 1970 ). En uppsättning med åtta punkter som inte innehåller en konvex femhörning i illustrationen visar att ; det är svårare att bevisa att en uppsättning av nio punkter i allmän position innehåller en konvex femhörning. $f(5)>8$
$f(6)=17$ , detta har bevisats i ( Szekeres & Peters 2006 ). Tidningen implementerar en förkortad datoruppräkning av möjliga konfigurationer från 17 punkter.
Värden är okända för . $f(N)$ $N>6$

Erdős-Szekeres gissningar om det minsta antalet poäng

Baserat på de kända värdena för , föreslog Erdős och Székeres att: $f(N)$ $N=3,4,5$

f(N)=1+2^{{N-2}}

för alla .

N

Denna gissning har inte bevisats, men övre och nedre gränser är kända.

Uppskattningar av tillväxthastigheten f(N)

Genom en konstruktiv konstruktion kunde författarna till gissningen senare bevisa den lägre skattningen, som sammanfaller med den hypotetiska likheten:

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

, ( Erdős & Szekeres 1961 )

Den mest kända övre gränsen för är dock inte nära: $N\geq 7$

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

, ( Toth & Valtr 2005 )

(använde binomialkoefficienter ).

Tomma polygoner

Av intresse är också frågan om en tillräckligt stor uppsättning punkter i allmän position innehåller en tom konvex fyrhörning, en femhörning , och så vidare. Det vill säga en polygon som inte innehåller några inre punkter.

Om det finns en punkt inuti fyrkanten som existerar enligt satsen med lyckligt slut, då genom att koppla denna punkt med två hörn på diagonalen får vi två fyrkanter, varav en är konvex och tom. Således innehåller fem punkter i allmän position en tom konvex fyrhörning, som ses i illustrationen. Alla tio punkter i allmän position innehåller en tom konvex femhörning ( Harborth 1978 ). Det finns dock godtyckligt stora uppsättningar av punkter i allmän position som inte innehåller en tom konvex heptagon ( Horton 1983 )

Problemet med tomma polygoner är alltså inte ett problem inom Ramsey-teorin och har lösts i princip.

Frågan om existensen av en tom hexagon förblev öppen under lång tid. Men i ( Nicolás 2007 ) och ( Gerken 2008 ) bevisades att varje tillräckligt stor uppsättning punkter i allmän position innehåller en tom hexagon. Idag är det känt att denna uppsättning bör innehålla högst f (9) (förmodligen 129) och minst 30 poäng ( Overmars 2003 ).

Anteckningar

↑ I detta sammanhang betyder allmän position att inga tre punkter ligger på samma linje.

Litteratur

Chung, FRK & Graham, R. L. (1998), Forced convex n-gons in the plane , Discrete and Computational Geometry vol. 19 (3): 367–371 , DOI 10.1007/PL00009353 .
Erdős, P. & Szekeres, G. (1935), A combinatorial problem in geometry , Compositio Math vol. 2: 463–470 , < http://www.numdam.org/item?id=CM_1935__2__463_0 > .
Erdős, P. & Szekeres, G. (1961), On some extremum problems in elementary geometry, Ann. Univ. sci. Budapest. Eötvös Sect. Matematik. T. 3–4: 53–62 . Omtryckt i: Erdős, P. (1973), Spencer, J., red., The Art of Counting: Selected Writings , Cambridge, MA: MIT Press, sid. 680–689 .
Gerken, Tobias (2008), Empty convex hexagons in planar point sets , Discrete and Computational Geometry vol. 39 (1–3): 239–272 , DOI 10.1007/s00454-007-9018-x .
Grünbaum, Branko (2003), Kaibel, Volker; Klee, Victor & Ziegler, Günter M. , eds., Convex Polytopes , vol. 221 (2nd ed.), Graduate Texts in Mathematics, Springer-Verlag , ISBN 0-387-00424-6 .
Harborth, Heiko (1978), Konvexe Fünfecke i ebenen Punktmengen, Elem. Matematik. T. 33(5): 116–118 .
Horton, JD (1983), Uppsättningar utan tomma konvexa 7-goner , Canadian Mathematical Bulletin T. 26 (4): 482–484 , DOI 10.4153/CMB-1983-077-8 .
Kalbfleisch, JD; Kalbfleisch, JG & Stanton, RG (1970), A combinatorial problem on convex regions, Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing , vol. 1, Congressus Numerantium, Baton Rouge, La.: Louisiana State Univ., sid. 180–188 .
Kleitman, DJ & Pachter, L. (1998), Hitta konvexa mängder bland punkter i planet , Discrete and Computational Geometry vol 19 (3): 405–410 , DOI 10.1007/PL00009358 .
Morris, W. & Soltan, V. (2000), The Erdős-Szekeres problem on points in convex position—A survey , Bulletin of the American Mathematical Society vol. 37 (04): 437–458, doi : 10.1090/S0273- 0979-00-00877-6 , < http://www.ams.org/bull/2000-37-04/S0273-0979-00-00877-6/home.html > .
Nicolás, Carlos M. (2007), The empty hexagon theorem , Discrete and Computational Geometry vol. 38 (2): 389–397 , DOI 10.1007/s00454-007-1343-6 .
Overmars, M. (2003), Hitta uppsättningar av punkter utan tomma konvexa 6-goner , Discrete and Computational Geometry vol 29 (1): 153–158 , DOI 10.1007/s00454-002-2829-x .
Peterson, Ivars (2000), Planes of Budapest , MAA Online , < http://www.maa.org/mathland/mathtrek_10_3_00.html > .
Scheinerman, Edward R. & Wilf, Herbert S. (1994), Det rätlinjiga korsningsnumret för en komplett graf och Sylvesters "fyrapunktsproblem" med geometrisk sannolikhet , American Mathematical Monthly (Mathematical Association of America). - T. 101 (10): 939–943 , DOI 10.2307/2975158 .
Szekeres, G. & Peters, L. (2006), Computer solution to the 17-point Erdős-Szekeres problem , ANZIAM Journal vol . 48 (02): 151–164, doi : 10.1017/S144618110000300X , < http://www. .austms.org.au/Publ/ANZIAM/V48P2/2409.html > Arkiverad 13 december 2019 på Wayback Machine .
Tóth, G. & Valtr, P. (1998), Note on the Erdős-Szekeres theorem , Discrete and Computational Geometry vol 19 (3): 457–459 , DOI 10.1007/PL00009363 .
Tóth, G. & Valtr, P. (2005), Erdős-Szekeres teorem: övre gränser och relaterade resultat, kombinatorisk och beräkningsgeometri , Matematiska vetenskaper forskningsinstitutets publikationer, nr. 52, sid. 557–568 .
Valtr, P. (2006), On the empty hexagons , < http://kam.mff.cuni.cz/~valtr/h.ps > .

Länkar

Happy ending problem Arkiverad 25 september 2006 på Wayback Machine och Ramsey-teoretiska bevis för Erdős-Szekeres sats på PlanetMath
Weisstein, Eric W. Happy End Problem (engelska) på Wolfram MathWorld- webbplatsen .