Feladat happy enddel

A happy enddel kapcsolatos probléma az az állítás, hogy a síkon [1] általános helyzetben lévő bármely öt pontból álló halmaznak van egy négy pontból álló részhalmaza, amelyek egy konvex négyszög csúcsai .

Történelem

A kombinatorikus geometriának ezt az eredményét Erdős Pál "szerencsés végű problémának" nevezi, hiszen a probléma megoldása Sekeres György és Klein Esther ( Hung. Klein Eszter ) esküvőjével zárult. Erdős-Szekeres konvex sokszög tételként is ismert .

Az eredmény tetszőleges számú pontra történő általánosítása érdekli a 20. és 21. század matematikusait.

Bizonyítás

Ha legalább négy pont egy konvex hajótestet alkot , akkor bármely négy hajótestből álló halmaz választható konvex négyszögként. Egyébként van egy háromszög és benne két pont. Két belső ponton áthaladó egyenes a pontok általános helyzete miatt nem metszi a háromszög egyik oldalát. Ennek az oldalnak a csúcsai és két belső pont egy konvex négyszöget alkotnak.

Tetszőleges számú csúcsú sokszögek

Erdős és Szekeres ezt az eredményt tetszőleges számú pontra általánosította, ami a Ramsey-elmélet eredeti továbbfejlesztése . Előadták az "Erdős-Szekeres sejtést" is - egy pontos képletet egy konvex sokszög csúcsainak maximális számára, amelyeknek egy adott számú pontból álló halmazban létezniük kell általános helyzetben.

( Erdős & Szekeres 1935 ) a következő általánosítást igazolták: bármely természetes esetén a síkon általános helyzetű pontok bármely kellően nagy halmaza rendelkezik olyan pontok részhalmazával , amelyek egy konvex sokszög csúcsai. Ez a bizonyítás ugyanabban a cikkben jelent meg, ahol az Erdős-Szekeres tételt a numerikus sorozatok monoton részsorozatairól igazolják. $N$ $N$

Állítsa be a méretet a sokszög csúcsok számának függvényében

Jelölje azt a minimumot , amelyre az általános helyzetben lévő bármely ponthalmaz tartalmaz egy konvex -gont. Ismeretes, hogy: $f(N)$ $M$ $M$ $N$

$f(3)=3$ , nyilvánvalóan.
$f(4)=5$ , bizonyította Sekeres Eszter.
$f(5)=9$ szerint ( Erdős & Szekeres 1935 ) Makai E. volt az első, aki ezt bizonyította; az első publikált bizonyíték ben jelent meg ( Kalbfleisch, Kalbfleisch & Stanton 1970 ). Egy nyolc pontból álló halmaz, amely az ábrán nem tartalmaz konvex ötszöget, azt mutatja, hogy ; nehezebb bizonyítani, hogy bármely általános helyzetben lévő kilenc pontból álló halmaz konvex ötszöget tartalmaz. $f(5)>8$
$f(6)=17$ , ezt bebizonyították ( Szekeres & Peters 2006 ). A dolgozat 17 pontból valósítja meg a lehetséges konfigurációk rövidített számítógépes felsorolását.
Az értékek ismeretlenek a számára . $f(N)$ $N>6$

Az Erdős-Szekeres sejtés a minimális pontszámról

Erdős és Székeres az ismert értékek alapján a következőket javasolta: $f(N)$ $N=3,4,5$

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

mindenkinek .

N

Ez a sejtés nem bizonyított, de a felső és az alsó határ ismert.

Az f(N) növekedési ütem becslései

Konstruktív konstrukcióval a sejtés szerzői később igazolni tudták az alacsonyabb becslést, amely egybeesik a hipotetikus egyenlőséggel:

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

, ( Erdős & Szekeres 1961 )

A legismertebb felső korlát azonban nem közeli: $N\geq 7$

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

, ( Tóth és Valtr 2005 )

( binomiális együtthatókat használtunk ).

Üres sokszögek

Szintén érdekes kérdés, hogy az általános helyzetben lévő pontok kellően nagy halmaza tartalmaz- e üres konvex négyszöget, ötszöget stb. Vagyis egy sokszög, amely nem tartalmaz belső pontokat.

Ha a négyszögön belül van egy pont, amely a happy end tétel szerint létezik, akkor ezt a pontot az átló két csúcsával összekötve két négyszöget kapunk, amelyek közül az egyik konvex és üres. Így az általános helyzetben lévő öt pont egy üres konvex négyszöget tartalmaz, amint az az ábrán látható. Az általános helyzetben lévő bármely tíz pont tartalmaz egy üres konvex ötszöget ( Harborth 1978 ). Vannak azonban tetszőlegesen nagy ponthalmazok általános helyzetben, amelyek nem tartalmaznak üres konvex hétszöget ( Horton 1983 ) .

Így az üres sokszögek problémája nem a Ramsey-elmélet problémája, és elvileg megoldódott.

Az üres hatszög létezésének kérdése sokáig nyitva maradt. De ( Nicolás 2007 ) és ( Gerken 2008 ) bebizonyosodott, hogy általános helyzetben minden kellően nagy ponthalmaz tartalmaz egy üres hatszöget. Ma már ismert, hogy ennek a halmaznak legfeljebb f (9)-et (feltehetően 129) és legalább 30 pontot kell tartalmaznia ( Overmars 2003 ).

Jegyzetek

↑ Ebben az összefüggésben az általános helyzet azt jelenti, hogy nincs három pont egy egyenesen.

Irodalom

Chung, FRK & Graham, R. L. (1998), Forced convex n-gons in the plane , Discrete and Computational Geometry , 19. kötet (3): 367–371 , DOI 10.1007/PL00009353 .
Erdős, P. & Szekeres, G. (1935), A kombinatorial 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 Szekt. Math. T. 3–4: 53–62 . Újranyomva: Erdős, P. (1973), Spencer, J., szerk., The Art of Counting: Selected Writings , Cambridge, MA: MIT Press, p. 680–689 .
Gerken, Tobias (2008), Empty convex hexagons in planar point sets , Discrete and Computational Geometry , 39. kötet (1–3): 239–272 , DOI 10.1007/s00454-007-9018-x .
Grünbaum, Branko (2003), Kaibel, Volker; Klee, Victor & Ziegler, Günter M. , szerk., Convex Polytopes , vol. 221 (2. kiadás), Graduate Texts in Mathematics, Springer-Verlag , ISBN 0-387-00424-6 .
Harborth, Heiko (1978), Konvexe Fünfecke in ebenen Punktmengen, Elem. Math. T. 33(5): 116–118 .
Horton, JD (1983), készletek üres konvex 7-szögűek nélkül , Canadian Mathematical Bulletin T. 26 (4): 482–484 , DOI 10.4153/CMB-1983-077-8 .
Kalbfleisch, JD; Kalbfleisch, JG & Stanton, RG (1970), A kombinatorikus probléma konvex régiókon, Proc. Louisiana konf. Kombinatorika, gráfelmélet és számítástechnika , vol. 1, Congressus Numerantium, Baton Rouge, La.: Louisiana State Univ., p. 180–188 .
Kleitman, DJ & Pachter, L. (1998), Konvex halmazok keresése pontok között a síkban , Discrete and Computational Geometry , 19. kötet (3): 405–410 , DOI 10.1007/PL00009358 .
Morris, W. & Soltan, V. (2000), The Erdős-Szekeres probléma pontokon konvex pozícióban – A felmérés , 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), Az üres hatszög tétel , Discrete and Computational Geometry , 38. kötet (2): 389–397 , DOI 10.1007/s00454-007-1343-6 .
Overmars, M. (2003), Ponthalmazok keresése üres konvex 6-szögek nélkül , Discrete and Computational Geometry , 29. kötet (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), A teljes gráf egyenes vonalú keresztezési száma és a geometriai valószínűség Sylvester-féle „négypontos problémája” , American Mathematical Monthly (Mathematical Association of America). - T. 101 (10): 939–943 , DOI 10.2307/2975158 .
Szekeres, G. & Peters, L. (2006), Számítógépes megoldás a 17 pontos Erdős-Szekeres problémára , ANZIAM Journal vol . 48 (02): 151–164, doi : 10.1017/S144618110000300X , < http://www. .austms.org.au/Publ/ANZIAM/V48P2/2409.html > Archiválva : 2019. december 13. a Wayback Machine -nél .
Tóth, G. & Valtr, P. (1998), Megjegyzés az Erdős-Szekeres tételhez , Discrete and Computational Geometry , 19 (3): 457–459 , DOI 10.1007/PL00009363 .
Tóth, G. & Valtr, P. (2005), Az Erdős-Szekeres tétel: felső határok és a kapcsolódó eredmények, Kombinatorikus és számítási geometria , Matematikai Tudományok Kutatóintézet Publikációi, sz. 52. o. 557–568 .
Valtr, P. (2006), Az üres hatszögeken , < http://kam.mff.cuni.cz/~valtr/h.ps > .

Linkek

Happy ending probléma Archivált 2006. szeptember 25-én a Wayback Machine és az Erdős-Szekeres tétel Ramsey-elméleti bizonyítása a PlanetMath -on
Weisstein, Eric W. Happy End Problem (angolul) a Wolfram MathWorld webhelyén .