Happy End-Probléma: Matematikai probléma

Tétel. Bárhogyan veszünk fel öt általános helyzetű pontot a síkban, 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.

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).

 

(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.
• f(5) = 9. 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.
• 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

${\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

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

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

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

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

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

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. 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.

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. 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.

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.

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.

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. Á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.

• 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.

• A Happy End-probléma Archiválva 2006. szeptember 25-i dátummal a Wayback Machine-ben és annak Ramsey-elmélet szerinti megoldása Archiválva 2006. szeptember 25-i dátummal a Wayback Machine-ben a PlanetMathon
• Weisstein, Eric W.: Happy End-probléma (angol nyelven). Wolfram MathWorld
• Tardos Gábor, Tóth Géza: Áttörés az Erdős—Szekeres problémában (magyar nyelven). Érintő (Bolyai János Matematikai Társulat), 2018. március 1.