En opgave med en lykkelig slutning

Et problem med en lykkelig slutning er påstanden om, at ethvert sæt af fem punkter på planet i generel position [1] har en delmængde af fire punkter, der er hjørner af en konveks firkant .

Historie

Dette resultat af kombinatorisk geometri kaldes af Pal Erdős et "problem med en lykkelig slutning", eftersom løsningen af problemet endte med brylluppet mellem György Sekeres og Esther Klein ( Hung. Eszter Klein ). Også kendt som Erdős-Szekeres konvekse polygonsætning .

Generaliseringer af resultatet til et vilkårligt antal punkter er af interesse for matematikere i det 20. og 21. århundrede.

Bevis

Hvis mindst fire punkter danner et konveks skrog , så kan ethvert sæt af fire skrogpunkter vælges som en konveks firkant. Ellers er der en trekant og to punkter inde i den. En ret linje, der går gennem to indre punkter, skærer ikke en af trekantens sider på grund af punkternes generelle position. Hjørnerne på denne side og to indre punkter danner en konveks firkant.

Polygoner med et vilkårligt antal hjørner

Erdős og Szekeres generaliserede dette resultat til et vilkårligt antal punkter, en original udvikling af Ramsey-teorien . De fremlagde også "Erdős-Szekeres formodning" - en nøjagtig formel for det maksimale antal hjørner af en konveks polygon, der skal eksistere i et sæt af et givet antal punkter i generel position.

I ( Erdős & Szekeres 1935 ) blev følgende generalisering bevist: for enhver naturlig , et tilstrækkeligt stort sæt af punkter i den generelle position på planet har en delmængde af punkter, der er hjørner af en konveks polygon. Dette bevis dukkede op i den samme artikel, hvor Erdős-Szekeres sætning om monotone undersekvenser i numeriske sekvenser er bevist. $N$ $N$

Indstil størrelse som en funktion af antallet af polygon-spidser

Lad betegne det minimum , for hvilket ethvert sæt punkter i generel position indeholder en konveks -gon. Det er kendt, at: $f(N)$ $M$ $M$ $N$

$f(3)=3$ , naturligvis.
$f(4)=5$ , beviste Esther Sekeres.
$f(5)=9$ ifølge ( Erdős & Szekeres 1935 ) var E. Makai den første til at bevise dette; det første publicerede bevis optrådte i ( Kalbfleisch, Kalbfleisch & Stanton 1970 ). Et sæt på otte punkter, der ikke indeholder en konveks femkant i illustrationen, viser, at ; det er vanskeligere at bevise, at ethvert sæt af ni punkter i generel position indeholder en konveks femkant. $f(5)>8$
$f(6)=17$ , dette er blevet bevist i ( Szekeres & Peters 2006 ). Papiret implementerer en forkortet computeropregning af mulige konfigurationer fra 17 punkter.
Værdier er ukendte for . $f(N)$ $N>6$

Erdős-Szekeres formodning om minimumsantallet af point

Baseret på de kendte værdier for , foreslog Erdős og Székeres, at: $f(N)$ $N=3,4,5$

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

for alle .

N

Denne formodning er ikke blevet bevist, men øvre og nedre grænser er kendt.

Estimater af vækstraten f(N)

Ved en konstruktiv konstruktion var forfatterne af formodningen senere i stand til at bevise det lavere skøn, som falder sammen med den hypotetiske lighed:

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

, ( Erdős & Szekeres 1961 )

Den bedst kendte øvre grænse for er dog ikke tæt: $N\geq 7$

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

, ( Toth & Valtr 2005 )

(brugte binomiale koefficienter ).

Tomme polygoner

Også af interesse er spørgsmålet om, hvorvidt et tilstrækkeligt stort sæt punkter i generel position indeholder en tom konveks firkant, en femkant , og så videre. Det vil sige en polygon, der ikke indeholder nogen indre punkter.

Hvis der er et punkt inde i firkanten, der eksisterer ifølge happy end-sætningen, så får vi ved at forbinde dette punkt med to hjørner af diagonalen to firkanter, hvoraf den ene er konveks og tom. Således indeholder fem punkter i generel position en tom konveks firkant, som det ses på illustrationen. Enhver ti punkter i generel position indeholder en tom konveks femkant ( Harborth 1978 ). Der er dog vilkårligt store sæt af punkter i den generelle position, som ikke indeholder en tom konveks sekskant ( Horton 1983 )

Problemet med tomme polygoner er således ikke et problem i Ramsey-teorien og er blevet løst i princippet.

Spørgsmålet om eksistensen af en tom sekskant forblev åbent i lang tid. Men i ( Nicolás 2007 ) og ( Gerken 2008 ) blev det bevist, at hvert tilstrækkeligt stort sæt punkter i generel position indeholder en tom sekskant. I dag er det kendt, at dette sæt højst bør indeholde f (9) (formodentlig 129) og mindst 30 point ( Overmars 2003 ).

Noter

↑ I denne sammenhæng betyder generel position, at ingen tre punkter ligger på samme linje.

Litteratur

Chung, FRK & Graham, R. L. (1998), Forced convex n-gons in the plane , Discrete and Computational Geometry bind 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 geometri, Ann. Univ. sci. Budapest. Eötvös sekt. Matematik. T. 3–4: 53–62 . Genoptrykt i: Erdős, P. (1973), Spencer, J., red., The Art of Counting: Selected Writings , Cambridge, MA: MIT Press, s. 680-689 .
Gerken, Tobias (2008), Empty convex hexagons in planar point sets , Discrete and Computational Geometry bind 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 (2. udgave), 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), Sæt uden tomme konvekse 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., s. 180–188 .
Kleitman, DJ & Pachter, L. (1998), Finding af konvekse mængder blandt punkter i planet , Discrete and Computational Geometry bind 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 bind 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 bind 38 (2): 389–397 , DOI 10.1007/s00454-007-1343-6 .
Overmars, M. (2003), Finde sæt af punkter uden tomme konvekse 6-goner , Diskret og beregningsgeometri bind 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 retlinede krydsningsnummer for en komplet graf og Sylvesters "firepunktsproblem" med geometrisk sandsynlighed , American Mathematical Monthly (Mathematical Association of America). - T. 101 (10): 939–943 , DOI 10.2307/2975158 .
Szekeres, G. & Peters, L. (2006), Computerløsning til 17-punkts Erdős-Szekeres-problemet , ANZIAM Journal vol . 48 (02): 151–164, doi : 10.1017/S144618110000300X , < http://www. .austms.org.au/Publ/ANZIAM/V48P2/2409.html > Arkiveret 13. december 2019 på Wayback Machine .
Tóth, G. & Valtr, P. (1998), Note om Erdős-Szekeres-sætningen , Diskret og beregningsgeometri bind 19 (3): 457–459 , DOI 10.1007/PL00009363 .
Tóth, G. & Valtr, P. (2005), Erdős-Szekeres-sætningen: øvre grænser og relaterede resultater, kombinatorisk og beregningsmæssig geometri , Matematiske videnskabers forskningsinstituts publikationer, nr. 52, s. 557-568 .
Valtr, P. (2006), On the tomme sekskanter , < http://kam.mff.cuni.cz/~valtr/h.ps > .