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).
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(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.
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áfmetszé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
↑itt: semelyik két pont nem esik egybe, és nincs közülük három egy egyenesen
↑ abPach János: A Happy End probléma – A kombinatorikus geometria kezdetei [1] és [2]
↑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.
↑(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.
↑(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.
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.
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.
Tóth, G. & Valtr, P. (1998), "Note on the Erdős-Szekeres theorem", Discrete and Computational Geometry19: 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.