Šťastný konec problému - Happy ending problem

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

„šťastný konec problém"(tak pojmenováno Paul Erdős protože to vedlo k uzavření manželství George Szekeres a Esther Kleinová^[1]) je následující prohlášení:

Teorém: libovolná sada pěti bodů v rovině v obecná pozice^[2] má podmnožinu čtyř bodů, které tvoří vrcholy a konvexní čtyřúhelník.

To byl jeden z původních výsledků, které vedly k vývoji Ramseyova 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í obal lze zvolit libovolné čtyři takové body. Pokud má naopak množina bodů tvar trojúhelníku se dvěma body uvnitř, lze zvolit dva vnitřní body a jednu ze stran trojúhelníku. Vidět Peterson (2000) pro ilustrované vysvětlení tohoto důkazu a Morris & Soltan (2000) pro podrobnější průzkum problému.

The Erdős – Szekeres dohad přesněji stanoví obecnější vztah mezi počtem bodů v bodové sadě s obecnou pozicí a jejím největším konvexním polygonem, a sice, že nejmenší počet bodů, pro které jakékoli obecné uspořádání polohy obsahuje konvexní podmnožinu ${ displaystyle n}$ body jsou ${ displaystyle 2 ^ {n-2} +1}$ . Zůstává neprokázané, ale jsou známy méně přesné hranice.

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í zevšeobecnění:

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

Důkaz se objevil ve stejném článku, který dokazuje Erdős – Szekeresova věta na monotónních subsekvencích v posloupnosti čísel

Nechat F(N) označují minimum M pro které je libovolná sada M body v obecné poloze musí obsahovat konvexní N-gon. Je známo že

F(3) = 3, triviálně.
F(4) = 5.^[3]
F(5) = 9.^[4] Na obrázku je ukázána sada osmi bodů bez konvexního pětiúhelníku, která to dokazuje 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.^[5]
Hodnota F(N) je neznámý pro všechny 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, domnívali se Erdős a Szekeres ve svém původním článku

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

Později to dokázali konstrukcí explicitních příkladů

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

^[6]

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

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

^[7]

Prázdné konvexní mnohoúhelníky

Existuje také otázka, zda nějaká dostatečně velká množina bodů v obecné poloze má „prázdný“ konvexní čtyřúhelník, Pentagon atd., tj. ten, který neobsahuje žádný další vstupní bod. Původní řešení problému se šťastným koncem lze upravit tak, aby ukazovalo, že jakýchkoli 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.^[8] Existují však libovolně velké sady bodů v obecné poloze, které neobsahují žádné prázdné konvexní sedmiúhelník.^[9]

Po dlouhou dobu otázka existence prázdného šestiúhelníky zůstal otevřený, ale Nicolás (2007) a Gerken (2008) dokázal, že každý dostatečně velký bod v obecné poloze obsahuje konvexní prázdný šestiúhelník. Gerken konkrétněji ukázal, že počet potřebných bodů není větší než F(9) pro stejnou funkci F definováno výše, zatímco Nicolás ukázal, že počet potřebných bodů není větší než F(25). Valtr (2008) poskytuje zjednodušení Gerkenova důkazu, že však vyžaduje více bodů, F(15) místo F(9). Je zapotřebí alespoň 30 bodů: v obecné poloze existuje sada 29 bodů bez prázdného konvexního šestiúhelníku.^[10]

Související problémy

Problém hledání sad n body minimalizující počet konvexních čtyřúhelníků jsou ekvivalentní minimalizaci číslo křížení v přímce výkres a kompletní graf. Počet čtyřúhelníků musí být úměrný čtvrté mocnině n, ale přesná konstanta není známa.^[11]

Je přímočaré to ukázat ve vyšší dimenzi Euklidovské prostory, dostatečně velké sady bodů budou mít podmnožinu k body, které tvoří vrcholy a konvexní mnohostěn, pro všechny k větší než dimenze: vyplývá to okamžitě z existence konvexní k-gony v dostatečně velkých sadách rovinných bodů promítnutím množiny vyšších dimenzí do libovolného dvourozměrného podprostoru. Je však třeba najít počet bodů k body v konvexní pozice může být ve vyšších dimenzích menší než v rovině a je možné najít podmnožiny, které jsou více omezené. Zejména v d rozměry, každý d + 3 body v obecné poloze mají podmnožinu d + 2 body, které tvoří vrcholy a cyklický mnohostěn.^[12] Obecněji pro každého d a k > d existuje číslo m(d,k) tak, že každá sada m(d,k) Body v obecné poloze mají podmnožinu k body, které tvoří vrcholy a sousedský polytop.^[13]

Poznámky

^ Svět výuky a čísel - krát dva, Michael Cowling, The Sydney Morning Herald, 2005-11-07, citováno 2014-09-04
^ V této souvislosti obecná poloha znamená, že žádné dva body se neshodují a žádné tři body nejsou kolineární.
^ To byl původní problém, který dokázala Esther Kleinová.
^ Podle Erdős & Szekeres (1935), toto poprvé prokázal E. Makai; první zveřejněný důkaz se objevil v Kalbfleisch, Kalbfleisch & Stanton (1970).
^ To bylo prokázáno Szekeres & Peters (2006). Provedli počítačové vyhledávání, které eliminovalo všechny možné konfigurace 17 bodů bez konvexních šestiúhelníků, přičemž zkoumaly jen nepatrný zlomek všech konfigurací.
^ Erdős & Szekeres (1961)
^ Suk (2016). Vidět binomický koeficient a velká O notace pro zde použitý zápis a Katalánská čísla nebo Stirlingova aproximace pro asymptotickou expanzi.
^ Harborth (1978).
^ Horton (1983)
^ Overmars (2003).
^ Scheinerman & Wilf (1994)
^ Grünbaum (2003), Př. 6.5.6, s. 120. Grünbaum připisuje tento výsledek soukromé komunikaci Micha A. Perlese.
^ Grünbaum (2003), Př. 7.3.6, s. 126. Tento výsledek následuje uplatněním Ramseyho-teoretického argumentu podobného původnímu Szekeresovu důkazu spolu s Perlesovým výsledkem případu k = d + 2.

Reference

Chung, FRK; Graham, R.L. (1998), „Forced convex n-gons in the plane“, Diskrétní a výpočetní geometrie, 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šť. Eötvös Sect. Matematika., 3–4: 53–62. Přetištěno v: Erdős, P. (1973), Spencer, J. (ed.), Umění počítání: Vybrané spisy, Cambridge, MA: MIT Press, s. 680–689.
Gerken, Tobias (2008), „Prázdné konvexní šestiúhelníky v sadách rovinný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.), Konvexní Polytopes, Postgraduální texty z matematiky, 221 (2. vyd.), Springer-Verlag, ISBN 0-387-00424-6.
Harborth, Heiko (1978), „Konvexe Fünfecke in ebenen Punktmengen“, Elemente der Mathematik, 33 (5): 116–118.
Horton, J. D. (1983), „Soupravy bez prázdných konvexních 7-gonů“, Kanadský matematický bulletin, 26 (4): 482–484, doi:10.4153 / CMB-1983-077-8.
Kalbfleisch, J.D .; Kalbfleisch, J.G.; Stanton, R.G. (1970), „Kombinatorický problém na konvexních oblastech“, Proc. Louisiana Conf. Kombinatorika, teorie grafů a výpočetní technika, Congressus Numerantium, 1„Baton Rouge, La .: Louisiana State Univ., Str. 180–188.
Kleitman, D.J.; 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), „Erdős-Szekeresův problém v bodech v konvexní poloze - průzkum“, Bulletin of the American Mathematical Society, 37 (04): 437–458, doi:10.1090 / S0273-0979-00-00877-6.
Nicolás, Carlos M. (2007), „Věta o prázdném šestiúhelníku“, Diskrétní a výpočetní geometrie, 38 (2): 389–397, doi:10.1007 / s00454-007-1343-6.
Overmars, M. (2003), „Hledání sad 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, Ivarsi (2000), "Letadla Budapešti", MAA online, archivovány z originál dne 02.07.2013.
Scheinerman, Edward R.; Wilf, Herbert S. (1994), „Přímočaré číslo křížení úplného grafu a Sylvestrova„ čtyřbodový problém “geometrické pravděpodobnosti“, Americký matematický měsíčník, Mathematical Association of America, 101 (10): 939–943, doi:10.2307/2975158, JSTOR 2975158.
Suk, Andrew (2016), „On the Erdős – Szekeres convex polygon problem“, J. Amer. Matematika. Soc., arXiv:1604.08657, doi:10.1090 / džemy / 869.
Szekeres, G.; Peters, L. (2006), „Počítačové řešení 17bodového problému Erdős-Szekeres“, ANZIAM Journal, 48 (02): 151–164, doi:10.1017 / S144618110000300X.
Tóth, G .; Valtr, P. (1998), „Note on the Erdős-Szekeres theorem“, Diskrétní a výpočetní geometrie, 19 (3): 457–459, doi:10.1007 / PL00009363.
Tóth, G .; Valtr, P. (2005), „Erdős-Szekeresova věta: horní hranice a související výsledky“, v Goodman, Jacob E.; Pach, János; Welzl, Emo (eds.), Kombinatorická a výpočetní geometrie (PDF)Publikace Výzkumného ústavu matematických věd, 52, Cambridge University Press, str. 557–568.
Valtr, P. (2008), „On empty hexagons“, v Goodman, Jacob E.; Pach, János; Pollack, Richarde (eds.), Průzkumy diskrétní a výpočetní geometrie: O dvacet let později: Společná letní výzkumná konference AMS-IMS-SIAM, 18. – 22. Června 2006, Snowbird, Utah, Současná matematika, 453, American Mathematical Society, str. 433–442, ISBN 9780821842393.

externí odkazy

[1] Svět výuky a čísel - krát dva, Michael Cowling, The Sydney Morning Herald, 2005-11-07, citováno 2014-09-04

[2] V této souvislosti obecná poloha znamená, že žádné dva body se neshodují a žádné tři body nejsou kolineární.

[3] To byl původní problém, který dokázala Esther Kleinová.

[4] Podle Erdős & Szekeres (1935), toto poprvé prokázal E. Makai; první zveřejněný důkaz se objevil v Kalbfleisch, Kalbfleisch & Stanton (1970).

[5] To bylo prokázáno Szekeres & Peters (2006). Provedli počítačové vyhledávání, které eliminovalo všechny možné konfigurace 17 bodů bez konvexních šestiúhelníků, přičemž zkoumaly jen nepatrný zlomek všech konfigurací.

[6] Erdős & Szekeres (1961)

[7] Suk (2016). Vidět binomický koeficient a velká O notace pro zde použitý zápis a Katalánská čísla nebo Stirlingova aproximace pro asymptotickou expanzi.

[8] Harborth (1978).

[9] Horton (1983)

[10] Overmars (2003).

[11] Scheinerman & Wilf (1994)

[12] Grünbaum (2003), Př. 6.5.6, s. 120. Grünbaum připisuje tento výsledek soukromé komunikaci Micha A. Perlese.

[13] Grünbaum (2003), Př. 7.3.6, s. 126. Tento výsledek následuje uplatněním Ramseyho-teoretického argumentu podobného původnímu Szekeresovu důkazu spolu s Perlesovým výsledkem případu k = d + 2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]