Problém se šťastným koncem - Happy ending problem

Problém šťastného konce: každá sada pěti bodů v obecné poloze obsahuje vrcholy konvexního čtyřúhelníku

V matematice je „ problém šťastného konce “ (tak jej pojmenoval Paul Erdős, protože vedl ke sňatku George Szekeres a Esther Klein ):

Věta : jakákoli sada pěti bodů v rovině v obecné poloze má podmnožinu čtyř bodů, které tvoří vrcholy konvexního čtyřúhelníku .

To byl jeden z původních výsledků, které vedly k rozvoji Ramseyovy teorie .

Věta o šťastném konci může být prokázána jednoduchou analýzou případů: pokud jsou čtyři nebo více bodů vrcholy konvexního trupu , lze vybrat libovolné čtyři takové body. Pokud má naopak konvexní trup tvar trojúhelníku se dvěma body uvnitř, lze zvolit dva vnitřní body a jednu ze stran trojúhelníku. Viz Peterson (2000) pro ilustrované vysvětlení tohoto důkazu a Morris & Soltan (2000) pro podrobnější průzkum problému.

Erdős-Szekeres domněnka uvádí přesně obecnější vztah mezi počtem bodů v bodě sadě pro obecné polohy a jejím největším konvexní polygon , a sice, že nejmenší počet bodů, pro které žádná obecná uspořádání pozice obsahuje konvexní podmnožina bodů . Zůstává neprokázané, ale jsou známy méně přesné hranice. ${\ displaystyle n}$ ${\ displaystyle 2^{n-2} +1}$

Větší polygony

Sada osmi bodů v obecné poloze bez konvexního pětiúhelníku

Erdős & Szekeres (1935) prokázal následující zobecnění:

Věta : pro jakékoli kladné celé číslo N má každá dostatečně velká konečná množina bodů v rovině v obecné poloze podmnožinu N bodů, které tvoří vrcholy konvexního mnohoúhelníku.

Důkaz se objevil ve stejném dokumentu, který dokazuje Erdős – Szekeresovu větu o monotónních subsekvencích v posloupnostech čísel.

Nechť f ( N ) označuje minimální M, pro které jakákoli sada M bodů v obecné poloze musí obsahovat konvexní N -gon. Je známo že

f (3) = 3, triviálně.
f (4) = 5.
f (5) = 9. Na obrázku je znázorněna sada osmi bodů bez konvexního pětiúhelníku , což ukazuje, že f (5)> 8; obtížnější částí důkazu je ukázat, že každá sada devíti bodů v obecné poloze obsahuje vrcholy konvexního pětiúhelníku.
f (6) = 17.
Hodnota f ( N ) je neznámá pro všech N > 6. Výsledkem Erdős & Szekeres (1935) je známo, že je konečný.

Na základě známých hodnot f ( N ), pro N = 3, 4 a 5, a Erdős Szekeres se domníval, ve své původní papíru, který

{\ Displaystyle f (N) = 1+2^{N-2} \ quad {\ mbox {pro všechny}} N \ geq 3.}

Později dokázali, že konstruovali explicitní příklady, že

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

ale nejznámější horní hranice, když N ≥ 7 je

{\ Displaystyle f (N) \ leq 2^{N+o (N)}.}

Prázdné konvexní mnohoúhelníky

Nabízí se také otázka, zda má nějaká dostatečně velká množina bodů v obecné poloze „prázdný“ konvexní čtyřúhelník, pětiúhelník atd., Tedy takový, který neobsahuje žádný další vstupní bod. Původní řešení problému šťastného konce lze přizpůsobit tak, aby ukázalo, že všech pět bodů v obecné poloze má prázdný konvexní čtyřúhelník, jak je znázorněno na obrázku, a všech deset bodů v obecné poloze má prázdný konvexní pětiúhelník. Existují však libovolně velké sady bodů v obecné poloze, které neobsahují žádný prázdný konvexní sedmiúhelník .

Otázka existence prázdných šestiúhelníků zůstala dlouho otevřená, ale Nicolás (2007) a Gerken (2008) dokázali, že každý dostatečně velký bod nastavený v obecné poloze obsahuje konvexní prázdný šestiúhelník. Gerken konkrétněji ukázal, že počet bodů potřebných pro stejnou funkci f definovanou výše není větší než f (9) , zatímco Nicolás ukázal, že počet potřebných bodů není větší než f (25). Valtr (2008) přináší zjednodušení Gerkenova důkazu, který však vyžaduje více bodů, f (15) místo f (9). Je zapotřebí alespoň 30 bodů; existuje sada 29 bodů v obecné poloze bez prázdného konvexního šestiúhelníku.

Související problémy

Problém nalezení sad n bodů minimalizuje počet konvexních čtyřúhelníků je ekvivalentní k minimalizaci počtu přechod v přímočarým výkresu z kompletního grafu . Počet čtyřúhelníků musí být úměrný čtvrté mocnině n , ale přesná konstanta není známa.

Je jednoduché ukázat, že ve vyšších dimenzionálních euklidovských prostorech budou mít dostatečně velké množiny bodů podmnožinu k bodů, které tvoří vrcholy konvexního mnohostěnu , pro každé k větší než rozměr: to vyplývá bezprostředně z existence konvexních k -gons v dostatečně velkých rovinných bodových sadách, promítnutím množiny vyšších dimenzí do libovolného dvourozměrného podprostoru. Počet bodů nutných k nalezení k bodů v konvexní poloze však může být ve vyšších dimenzích menší, než je v rovině, a je možné najít podmnožiny, které jsou více omezené. Zejména v dimenzích d má každé d + 3 body v obecné poloze podmnožinu d + 2 bodů, které tvoří vrcholy cyklického polytopu . Obecněji řečeno, pro každé d a k > d existuje číslo m ( d , k ) takové, že každá sada m ( d , k ) bodů v obecné poloze má podmnožinu k bodů, které tvoří vrcholy sousedního polytopu .

Poznámky

Reference

Chung, FRK ; Graham, RL (1998), „Forced convex n-gons in the plane“, Discrete and Computational Geometry , 19 (3): 367–371, doi : 10.1007/PL00009353.
Erdős, P .; Szekeres, G. (1935), „Kombinatorický problém v geometrii“ , Compositio Mathematica , 2 : 463–470.
Erdős, P .; Szekeres, G. (1961), „O některých extrémních problémech v elementární geometrii“, Ann. Univ. Sci. Budapešť. Sekta Eötvös. Matematika. , 3–4 : 53–62. Přetištěno v: Erdős, P. (1973), Spencer, J. (ed.), The Art of Counting: Selected Writings , Cambridge, MA: MIT Press, s. 680–689.
Gerken, Tobias (2008), „Prázdné konvexní šestiúhelníky v množinách planárních bodů“, Diskrétní a výpočetní geometrie , 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 , Graduate Texts in Mathematics, 221 (2. ed.), Springer-Verlag , ISBN 0-387-00424-6.
Harborth, Heiko (1978), „Konvexe Fünfecke in ebenen Punktmengen“, Elemente der Mathematik , 33 (5): 116–118.
Horton, JD (1983), „Sady bez prázdných konvexních 7 gonů“, Canadian Mathematical Bulletin , 26 (4): 482–484, doi : 10,4153/CMB-1983-077-8.
Kalbfleisch, JD; Kalbfleisch, JG ; Stanton, RG (1970), „Kombinatorický problém na konvexních oblastech“, Proc. Louisiana Conf. Combinatorics, Graph Graphory and Computing , Congressus Numerantium, 1 , Baton Rouge, La .: Louisiana State Univ., S. 180–188.
Kleitman, DJ ; Pachter, L. (1998), „Hledání konvexních množin mezi body v rovině“ (PDF) , Diskrétní a výpočetní geometrie , 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 , 37 (4): 437–458, doi : 10.1090/S0273-0979-00- 00877-6.
Nicolás, Carlos M. (2007), „Prázdná šestihranná věta“, Diskrétní a výpočetní geometrie , 38 (2): 389–397, doi : 10,1007/s00454-007-1343-6.
Overmars, M. (2003), „Hledání množin bodů bez prázdných konvexních 6 gonů“, Diskrétní a výpočetní geometrie , 29 (1): 153–158, doi : 10,1007/s00454-002-2829-x.
Peterson, Ivars (2000), „Planes of Budapest“ , MAA Online , archivováno od originálu dne 2013-07-02.
Scheinerman, Edward R .; Wilf, Herbert S. (1994), „Přímočaré číslo křížení kompletního grafu a Sylvesterův„ čtyřbodový problém “geometrické pravděpodobnosti“, American Mathematical Monthly , Mathematical Association of America, 101 (10): 939–943, doi : 10.2307/2975158 , JSTOR 2975158.
Suk, Andrew (2016), „O konvexním polygonovém problému Erdős – Szekeres“, J. Amer. Matematika. Soc. , 30 (4): 1047–1053, arXiv : 1604.08657 , doi : 10,1090 /jams/869 , S2CID 15732134.
Szekeres, G .; Peters, L. (2006), „Počítačové řešení 17bodového problému Erdős-Szekeres“ , ANZIAM Journal , 48 (2): 151–164, doi : 10,1017/S144618110000300X.
Tóth, G .; Valtr, P. (1998), „Note on the Erdős-Szekeres theorem“, Discrete and Computational Geometry , 19 (3): 457–459, doi : 10.1007/PL00009363.
Tóth, G .; Valtr, P. (2005), „Erdősova-Szekerova věta: horní hranice a související výsledky“, Goodman, Jacob E .; Pach, János ; Welzl, Emo (eds.), Combinatorial and Computational Geometry (PDF) , Mathematical Sciences Research Institute Publications, 52 , Cambridge University Press, s. 557–568.
Valtr, P. (2008), "O prázdných šestiúhelnících", v Goodman, Jacob E .; Pach, János ; Pollack, Richard (eds.), Surveys on Discrete and Computational Geometry: Twenty Years Later: AMS-IMS-SIAM Joint Summer Research Conference, 18.-22. června 2006, Snowbird, Utah , Contemporary Mathematics, 453 , American Mathematical Society, pp . 433–442, ISBN 9780821842393.

Languages

In other projects