Problem med ett lyckligt slut

Problemet med det lyckliga slutet: varje uppsättning av fem punkter i allmän position innehåller hörnen på en konvex fyrhörning

Inom matematik är " problemet med lyckligt slut " (så kallat av Paul Erdős eftersom det ledde till George Szekeres och Esther Kleins äktenskap) följande uttalande:

Sats - vilken som helst uppsättning av fem punkter i planet i allmän position har en delmängd av fyra punkter som bildar hörnen på en konvex fyrhörning .

Detta var ett av de ursprungliga resultaten som ledde till utvecklingen av Ramsey-teorin .

Teoremet med lyckligt slut kan bevisas genom en enkel fallanalys: om fyra eller fler punkter är hörn av det konvexa skrovet , kan vilka fyra sådana punkter som helst väljas. Om å andra sidan det konvexa skrovet har formen av en triangel med två spetsar inuti kan de två inre punkterna och en av triangelsidorna väljas. Se Peterson (2000) för en illustrerad förklaring av detta bevis, och Morris & Soltan (2000) för en mer detaljerad översikt av problemet.

Erdős –Szekeres gissningar anger exakt ett mer generellt förhållande mellan antalet punkter i en punktuppsättning med generella positioner och dess största delmängd som bildar en konvex polygon , nämligen att det minsta antalet punkter för vilka ett allmänt positionsarrangemang innehåller en konvex delmängd av $n$ punkter är $2^{n-2}+1$ . Det förblir obevisat, men mindre exakta gränser är kända.

Större polygoner

En uppsättning med åtta punkter i allmän position utan konvex femhörning

Erdős & Szekeres (1935) bevisade följande generalisering:

Sats — för vilket positivt heltal $N som helst$ , har varje tillräckligt stor ändlig uppsättning punkter i planet i den allmänna positionen en delmängd av $N$ punkter som bildar hörnen i en konvex polygon.

Beviset dök upp i samma tidning som bevisar Erdős–Szekeres sats om monotona delsekvenser i talföljder.

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

$f (3) = 3$ , trivialt.
$f (4) = 5$ .
$f (5) = 9$ . En uppsättning av åtta punkter utan konvex femhörning visas i illustrationen, vilket visar att $f (5) > 8$ ; den svårare delen av beviset är att visa att varje uppsättning av nio punkter i allmän position innehåller hörnen på en konvex femhörning.
$f (6) = 17$ .
Värdet på $f (N)$ är okänt för alla $N > 6$ . Genom resultatet av Erdős & Szekeres (1935) är $f (N) känt för att$ vara finit för alla finita $N.$

På grundval av de kända värdena för $f (N)$ för N = 3, 4 och 5, antog Erdős och Szekeres i sin originalartikel att

A set of sixteen points in general position with no convex hexagon

En uppsättning av sexton punkter i allmän position utan konvex hexagon

f(N)=1+2^{N-2}\quad {\text{för alla }}N\geq 3.

De bevisade senare, genom att konstruera tydliga exempel, att

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

men den mest kända övre gränsen när

N \geq 7

är

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

Tomma konvexa polygoner

Det är också frågan om någon tillräckligt stor uppsättning punkter i allmän position har en "tom" konvex fyrhörning, femhörning, etc., det vill säga en som inte innehåller någon annan ingångspunkt. Den ursprungliga lösningen på problemet med lyckligt slut kan anpassas för att visa att alla fem punkter i allmän position har en tom konvex fyrhörning, som visas i illustrationen, och alla tio punkter i allmän position har en tom konvex femhörning. Det finns dock godtyckligt stora uppsättningar av punkter i allmän position som inte innehåller någon tom konvex heptagon .

Länge förblev frågan om förekomsten av tomma hexagoner öppen, men Nicolás (2007) och Gerken (2008) bevisade att varje tillräckligt stor punktuppsättning i allmän position innehåller en konvex tom hexagon. Mer specifikt visade Gerken att antalet poäng som behövs inte är mer än f (9) för samma funktion f definierad ovan, medan Nicolás visade att antalet poäng som behövs inte är mer än f (25). Valtr (2008) ger en förenkling av Gerkens bevis som dock kräver fler poäng, f (15) istället för f (9). Minst 30 poäng behövs; det finns en uppsättning av 29 punkter i allmän position utan tom konvex hexagon.

Relaterade problem

Problemet med att hitta uppsättningar av n punkter som minimerar antalet konvexa fyrhörningar är likvärdigt med att minimera korsningstalet i en rätlinjeritning av en komplett graf . Antalet fyrhörningar måste vara proportionellt mot fjärde potensen av n , men den exakta konstanten är inte känd.

Det är enkelt att visa att i högre dimensionella euklidiska utrymmen kommer tillräckligt stora uppsättningar av punkter att ha en delmängd av k punkter som bildar hörnen på en konvex polytop , för varje k som är större än dimensionen: detta följer omedelbart av att det finns en konvex polytop. k -goner i tillräckligt stora plana punktuppsättningar, genom att projicera den högredimensionella punktuppsättningen in i ett godtyckligt tvådimensionellt delrum. Emellertid kan antalet punkter som krävs för att hitta k punkter i konvex position vara mindre i högre dimensioner än det är i planet, och det är möjligt att hitta delmängder som är mer begränsade. I synnerhet, i d , har varje d + 3 punkter i allmän position en delmängd av d + 2 punkter som bildar hörn av en cyklisk polytop . Mer generellt, för varje d och k > d finns det ett antal m ( d , k ) så att varje uppsättning av m ( d , k ) punkter i allmän position har en delmängd av k punkter som bildar hörnen av en grannpolytop .

Anteckningar

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), "Ett kombinatoriskt problem i geometrin" , Compositio Mathematica , 2 : 463–470 .
Erdős, P. ; Szekeres, G. (1961), "Om några extrema problem i elementär geometri", Ann. Univ. Sci. Budapest. Eötvös Sect. Matematik. , 3–4 : 53–62 . Återtryckt 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 , 39 (1–3): 239–272, doi : 10.1007/s00454-007-9018-x .
Grünbaum, Branko (2003), Kaibel, Volker; Klee, Victor ; Ziegler, Günter M. (red.), Convex Polytopes , Graduate Texts in Mathematics, vol. 221 (2:a upplagan), 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), "Set utan tomma konvexa 7-goner", Canadian Mathematical Bulletin , 26 (4): 482–484, doi : 10.4153/CMB-1983-077-8 , S2CID 120267029 .
Kalbfleisch, JD; Kalbfleisch, JG ; Stanton, RG (1970), "A combinatorial problem on convex regions", Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing , Congressus Numerantium, vol. 1, Baton Rouge, La.: Louisiana State Univ., s. 180–188 .
Kleitman, DJ ; Pachter, L. (1998), "Finding convex sets among points in the plane" (PDF) , Discrete and Computational Geometry , 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), "The empty hexagon theorem", Discrete and Computational Geometry , 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 , 29 (1): 153–158, doi : 10.1007/s00454-002-2829-x .
Peterson, Ivars (2000), "Planes of Budapest" , MAA Online , arkiverad från originalet 2013-07-02 .
Scheinerman, Edward R .; Wilf, Herbert S. (1994), "The rectilinear crossing number of a complete graph and Sylvester's four point problem" of geometric probability", American Mathematical Monthly , Mathematical Association of America, 101 (10): 939–943, doi : 10.2307/2975158 , JSTOR 2975158 .
Suk, Andrew (2016), "Om Erdős–Szekeres konvexa polygonproblem", J. Amer. Matematik. Soc. , 30 (4): 1047–1053, arXiv : 1604.08657 , doi : 10.1090/jams/869 , S2CID 15732134 .
Szekeres, G. ; Peters, L. (2006), "Computer solution to the 17-point Erdős-Szekeres problem" , 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ős-Szekeres teorem: övre gränser och relaterade resultat", i Goodman, Jacob E. ; Pach, János ; Welzl, Emo (red.), Combinatorial and Computational Geometry (PDF) , Mathematical Sciences Research Institute Publications, vol. 52, Cambridge University Press, s. 557–568 .
Valtr, P. (2008), "On tomma hexagoner", i Goodman, Jacob E. ; Pach, János ; Pollack, Richard (red.), Surveys on Discrete and Computational Geometry: Twenty Years Later: AMS-IMS-SIAM Joint Summer Research Conference, 18-22 juni 2006, Snowbird, Utah, Contemporary Mathematics, vol. 453, American Mathematical Society, s. 433–442, ISBN 9780821842393 .

externa länkar