matematikai probléma From Wikipedia, the free encyclopedia
A Happy End-probléma a következő állítás:
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).
(Erdős & Szekeres 1935) bizonyította a következő általánosabb kijelentést:
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:
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
Később konkrét példák megkonstruálásával annyit sikerült belátniuk, hogy
de N ≥ 7-re az ismert legjobb felső korlát
2016-ban Andrew Suk bejelentette annak bizonyítását, hogy
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]
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]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.