Happy End-probléma

A Happy End-probléma: öt általános helyzetű, egy síkban fekvő pontból mindig kiválaszthatóak egy konvex négyszög csúcsai.

A Happy End-probléma a következő állítás:

Tétel. Bárhogyan veszünk fel öt általános helyzetű pontot a síkban,[1] mindig kiválasztható közülük egy konvex négyszög négy csúcsa.

Az állítás bizonyítása az egyik fontos eredmény volt, ami végső soron elvezetett a kombinatorikus geometria, illetve a Ramsey-elmélet (lásd: Ramsey-tétel) megalkotásához.

A problémát 1932 őszén vetette fel Klein Eszter az Anonymus-csoport tagjainak, akik a KöMaL lelkes feladatmegoldói voltak (köztük Erdős Pál, Grünwald (Gallai) Tibor, Szekeres György, Turán Pál). A „Happy End-probléma” nevet Erdős Páltól kapta, mivel Szekeres György és Klein Eszter házasságához vezetett.[2]

Az eredeti Happy End-problémafelvetés könnyen igazolható a lehetséges esetek vizsgálatával: ha négy vagy több pont egy konvex burok csúcsai, akkor ezek közül bármely négy pontot kiválaszthatjuk. Ha azonban az öt pont egy háromszög csúcsaiból és a háromszög belsejében lévő két pontból áll, a két belső pontot és a háromszög valamely oldalához tartozó csúcspontokat kell kiválasztani. Lásd még a bizonyítás illusztrált változatát (Peterson 2000), valamint a probléma részletesebb elemzését (Morris & Soltan 2000).

Nagyobb sokszögek

Nyolc általános helyzetű pont a síkban, melyekből nem választható ki konvex ötszög.

(Erdős & Szekeres 1935) bizonyította a következő általánosabb kijelentést:

Tétel. Bármilyen pozitív egész N-re a síkban általános helyzetben elhelyezkedő pontok kellően nagy halmazának van olyan N pontból álló részhalmaza, melyek egy konvex sokszög csúcsait alkotják.

A bizonyítás ugyanabban a dolgozatban jelent meg, amiben a számsorozatok monoton részsorozataival foglalkozó Erdős–Szekeres-tétel bizonyítása szerepelt.

Ha f(N) jelöli a legkisebb lehetséges M-et, ahol a síkban M általános helyzetű pontnak tartalmaznia kell egy konvex N-szöget, ismeretes, hogy:

  • f(3) = 3, triviálisan.
  • f(4) = 5.[3]
  • f(5) = 9.[4] Egy nyolc pontot tartalmazó ellenpélda az oldalsó ábrán látható, igazolva, hogy f(5) > 8; a bizonyítás nehezebbik része annak megmutatása, hogy bármely kilenc általános helyzetű pont tartalmaz konvex ötszöget.
  • f(6) = 17.[5]
  • Az f(N) értéke ismeretlen N > 6 esetében; (Erdős & Szekeres 1935) alapján tudjuk, hogy véges számról van szó.

Ismerve az f(N) értékét N = 3, 4 és 5-re, Erdős és Szekeres eredeti dolgozatukban megfogalmazták azt a sejtést, hogy

f ( N ) = 1 + 2 N − 2 , ha  N ≥ 3. {\displaystyle f(N)=1+2^{N-2},\quad {\mbox{ha }}N\geq 3.}

Később konkrét példák megkonstruálásával annyit sikerült belátniuk, hogy

f ( N ) ≥ 1 + 2 N − 2 , {\displaystyle f(N)\geq 1+2^{N-2},} [6]

de N ≥ 7-re az ismert legjobb felső korlát

f ( N ) ≤ ( 2 N − 5 N − 2 ) + 1 = O ( 4 N N ) . {\displaystyle f(N)\leq {2N-5 \choose N-2}+1=O\left({\frac {4^{N}}{\sqrt {N}}}\right).} [7]

2016-ban Andrew Suk bejelentette annak bizonyítását, hogy

f ( N ) ≤ 2 N + o ( N ) . {\displaystyle f(N)\leq 2^{N+o(N)}.} [8]

Üres sokszögek

Felmerülhet a kérdés, hogy kijelenthetjük-e, hogy kellően nagy számú, általános helyzetű pont tartalmaz üres négyszöget, ötszöget stb., tehát olyat, aminek a belsejében nincs másik pont a választottak közül. Maga Erdős és Szekeres mindig is meg volt győződve a (később cáfolt) állítás igazságáról, de nyomtatott formában a sejtés talán csak 1978-ban jelent meg először.[9] Miután Szekeres kezdeti bizonyítási kísérlete kudarcot vallott, úgy tűnt, csak technikai nehézségről van szó, nehéz és kellemetlen a hosszú és vékony üres sokszögekkel dolgozni.[2]

A Happy End-probléma eredeti megoldása adaptálható a módosított feladatra, és így könnyen megmutatható, hogy bármely öt általános helyzetű pont tartalmaz üres konvex négyszöget (ahogy az ábra is mutatja), és bármely tíz általános helyzetű pont közül kijelölhetők egy üres konvex ötszög csúcspontjai.[10] Azonban, meglepetésre, tetszőlegesen nagy számú, általános helyzetű pont kijelölhető olyan módon, hogy ne tartalmazzanak üres konvex hétszöget.[11]

Az üres hatszögek kérdése sokáig nyitott volt, de (Nicolás 2007) és (Gerken 2008) megmutatták, hogy kellően nagy számú általános helyzetű pont bizonyosan tartalmaz üres hatszöget. Pontosabban, Gerken megmutatta, hogy a szükséges pontok száma nem több f(9)-nél (a fentebb meghatározott f függvényről van szó), míg Nicolás azt mutatta meg, hogy a szükséges pontok száma nem több, mint f(25). Valtr (2006) megalkotta Gerken bizonyításának egy leegyszerűsített változatát, de több pontra van szüksége, f(15)-re f(9) helyett. Biztosan legalább 30 pontra van szükség, mivel sikerült szerkeszteni olyan 29 pontból álló példát, ami nem tartalmaz üres konvex hatszöget.[12]

Kapcsolódó problémák

Az n pontból álló olyan ponthalmazok keresése, melyek minimális számú konvex négyszöget tartalmaznak, ekvivalens az egyenes vonalakkal lerajzolt teljes gráf metszési számának minimalizálásával. A négyszögek száma n negyedik hatványával arányos, de a pontos konstans nem ismeretes.[13]

Könnyen megmutatható, hogy magasabb dimenziójú euklideszi terekben kellően nagy számú pontnak lesz olyan k pontból álló részhalmaza, amik egy konvex politóp csúcspontjait adják, bármilyen a dimenziószámnál nagyobb k értékre: ez közvetlenül levezethető a kellően nagy számú pontból felállítható konvex k-szögek létezéséből, ha a magasabb dimenziójú ponthalmazt egy tetszőleges kétdimenziós altérre vetítjük. Azonban a konvex pozíciójú k ponthoz szükséges pontok száma magasabb dimenzióban kevesebb lehet, mint sík esetében, és lehetséges korlátosabb részhalmazokat találni. Különösen, d dimenziós térben minden d + 3 általános helyzetű pontnak létezik d + 2 pontból álló részhalmaza, melynek pontjai egy ciklikus politóp csúcspontjait adják.[14] Általánosabban, minden d és k > d esetén létezik olyan m(d,k) szám, hogy minden általános helyzetű m(d,k) pontnak létezik k pontból álló részhalmaza, melynek pontjai egy neighborly polytope csúcspontjait alkotják.[15]

Jegyzetek

  1. ↑ itt: semelyik két pont nem esik egybe, és nincs közülük három egy egyenesen
  2. ↑ a b Pach János: A Happy End probléma – A kombinatorikus geometria kezdetei [1] és [2]
  3. ↑ Ez Klein Eszter eredeti problémafelvetése.
  4. ↑ (Erdős & Szekeres 1935) szerint először Makai Endre bizonyította; az első publikált bizonyítás megjelenési helye (Kalbfleisch, Kalbfleisch & Stanton 1970).
  5. ↑ A bizonyítás viszonylag friss eredmény: (Szekeres & Peters 2006). Számítógép segítségével zárták ki a 17 pont minden elképzelhető, konvex hatszög nélküli kombinációját, miközben a rendkívül nagy számú összes lehetséges konfiguráció csak kis hányadát kellett végigvizsgálniuk.
  6. ↑ (Erdős & Szekeres 1961)
  7. ↑ (Tóth & Valtr 2005). A használt jelölésekhez lásd a binomiális együtthatókról és az Ordo-jelölésről szóló cikkeket.
  8. ↑ Suk, Andrew (2016), On the Erdős–Szekeres convex polygon problem.
  9. ↑ Erdős Pál (1978). „Some more problems on elementary geometry”. Australian Mathematical Society Gazette 5, 52–54. o. [2012. március 2-i dátummal az eredetiből archiválva]. (Hozzáférés: 2010. október 8.)  
  10. ↑ (Harborth 1978).
  11. ↑ (Horton 1983)
  12. ↑ (Overmars 2003).
  13. ↑ (Scheinerman & Wilf 1994)
  14. ↑ (Grünbaum 2003), Ex. 6.5.6, p.120. Grünbaum Micha A. Perles-szel való magánkommunikációját jelöli meg az eredmény forrásaként.
  15. ↑ (Grünbaum 2003), Ex. 7.3.6, p. 126. Az eredmény Ramsey-elméleti megfontolások alkalmazásánál alapul Szekeres eredeti bizonyításán és Perles eredményein a k = d + 2 esetre.

Fordítás

  • Ez a szócikk részben vagy egészben a Happy Ending problem című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Irodalom

  • Chung, F.R.K. & Graham, R.L. (1998), "Forced convex n-gons in the plane", Discrete and Computational Geometry 19: 367–371, DOI 10.1007/PL00009353.
  • Erdős, P. & Szekeres, G. (1935), "A combinatorial problem in geometry", Compositio Math 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 Sect. Math. 3–4: 53–62. Reprinted in: Erdős, P. (1973), Spencer, J., ed., The Art of Counting: Selected Writings, Cambridge, MA: MIT Press, pp. 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., eds., Convex Polytopes, vol. 221 (2nd ed.), Graduate Texts in Mathematics, Springer-Verlag, ISBN 0-387-00424-6.
  • Harborth, Heiko (1978), "Konvexe Fünfecke in ebenen Punktmengen", Elem. Math. 33 (5): 116–118.
  • Horton, J. D. (1983), "Sets with no empty convex 7-gons", Canad. Math. Bull. 26 (4): 482–484.
  • Kalbfleisch, J.D.; Kalbfleisch, J.G. & Stanton, R.G. (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., pp. 180–188.
  • Kleitman, D.J. & Pachter, L. (1998), "Finding convex sets among points in the plane", Discrete and Computational Geometry 19: 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: 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 38 (2): 389–397, DOI 10.1007/s00454-007-1343-6.
  • Overmars, M. (2003), "Finding sets of points without empty convex 6-gons", Discrete and Computational Geometry 29: 153–158, DOI 10.1007/s00454-002-2829-x.
  • Peterson, Ivars (2000), "Planes of Budapest", MAA Online, <https://web.archive.org/web/20010121105100/http://www.maa.org/mathland/mathtrek_10_3_00.html>.
  • 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, <http://jstor.org/stable/2975158>.
  • Szekeres, G. & Peters, L. (2006), "Computer solution to the 17-point Erdős-Szekeres problem", ANZIAM Journal 48: 151–164, doi:10.1017/S144618110000300X, <http://www.austms.org.au/Publ/ANZIAM/V48P2/2409.html>. Hozzáférés ideje: 2010-10-08 Archiválva 2019. december 13-i dátummal a Wayback Machine-ben.
  • Tóth, G. & Valtr, P. (1998), "Note on the Erdős-Szekeres theorem", Discrete and Computational Geometry 19: 457–459, DOI 10.1007/PL00009363.
  • Tóth, G. & Valtr, P. (2005), "The Erdős-Szekeres theorem: upper bounds and related results", Combinatorial and computational geometry, Mathematical Sciences Research Institute Publications, no. 52, pp. 557–568.
  • Valtr, P. (2006), On the empty hexagons, <http://kam.mff.cuni.cz/~valtr/h.ps>.

További információk

  • Matematika Matematikaportál • összefoglaló, színes tartalomajánló lap