Happy End-probléma

Innen: testwiki
Ugrás a navigációhoz Ugrás a kereséshez
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 Sablon:Harvard citation, valamint a probléma részletesebb elemzését Sablon:Harvard citation.

Nagyobb sokszögek

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

Sablon:Harvard citation 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; Sablon:Harvtxt 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+2N−2,ha N≥3.

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

f(N)≥1+2N−2,[6]

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

f(N)≤(2N−5N−2)+1=O(4NN).[7]

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

f(N)≤2N+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 Sablon:Harvtxt és Sablon:Harvtxt 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

Sablon:Jegyzetek

Fordítás

Irodalom

Sablon:Refbegin

Sablon:Refend

További információk

Sablon:Portál

  1. ↑ itt: semelyik két pont nem esik egybe, és nincs közülük három egy egyenesen
  2. ↑ 2,0 2,1 Pach János: A Happy End probléma – A kombinatorikus geometria kezdetei [1] és [2]
  3. ↑ Ez Klein Eszter eredeti problémafelvetése.
  4. ↑ Sablon:Harvtxt szerint először Makai Endre bizonyította; az első publikált bizonyítás megjelenési helye Sablon:Harvtxt.
  5. ↑ A bizonyítás viszonylag friss eredmény: Sablon:Harvtxt. 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. ↑ Sablon:Harvtxt
  7. ↑ Sablon:Harvtxt. 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. ↑ Sablon:Citation.
  9. ↑ Sablon:Cite journal
  10. ↑ Sablon:Harvtxt.
  11. ↑ Sablon:Harvtxt
  12. ↑ Sablon:Harvtxt.
  13. ↑ Sablon:Harvtxt
  14. ↑ Sablon:Harvtxt, 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. ↑ Sablon:Harvtxt, 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.
A lap eredeti címe: „https://hu.wiki.beta.math.wmflabs.org/w/index.php?title=Happy_End-probléma&oldid=2467”