Áttörés az Erdős—Szekeres problémában

1. Konvex sokszögek

Egy véges síkbeli $P$ ponthalmazt konvex helyzetűnek nevezünk, ha mindegyik pontja elválasztható a többitől egy egyenessel, azaz bármelyik $p\in P$ ponthoz található olyan egyenes, melynek $p$ az egyik, míg $P$ többi pontja a másik oldalán van. Eszerint egy legfeljebb két pontú ponthalmaz mindig konvex helyzetben van, a legalább három pontú ponthalmazok közül éppen a konvex sokszögek csúcshalmazai vannak konvex helyzetben. Így egy egyenes pontjai között sosem találunk hármat konvex helyzetben. Hogy ezt a problémát elkerüljük, a továbbiakban csak általános helyzetű ponthalmazokkal foglalkozunk, azaz feltesszük, hogy a pontok közt nincs három egy egyenesen.

1. ábra. Öt pont (a) konvex, (b) nem konvex helyzetben.

Klein Eszter, az akkor 22 éves egyetemista 1932-ben vette észre, hogy öt általános helyzetű pont között a síkon mindig van négy, ami konvex helyzetben van. A bizonyítás nagyon egyszerű. Ha a pontok konvex burka (a legnagyobb sokszög, amit meghatároznak) ötszög vagy négyszög, akkor az állítás nyilvánvaló. Ha a konvex burok egy $abc$ háromszög, akkor további két pont, $d$ és $e$ , ennek a belsejében van. A $de$ egyenes az $abc$ háromszög két oldalát metszi, mondjuk $ab$ -t és $ac$ -t. Ekkor viszont $b$ , $c$ , $d$ és $e$ konvex helyzetben van. Klein Eszter megkérdezte, hogy ez az egyszerű észrevétele általánosítható-e: vajon elég sok általános helyzetű pont között már feltétlenül találunk-e ötöt (hatot, stb.) konvex helyzetben? Tehát Klein Eszter kérdése a következő.

Igaz-e, hogy minden $n\ge 3$ természetes számhoz létezik egy $N$ szám azzal a tulajdonsággal, hogy $N$ általános helyzetű pont között a síkon mindig van $n$ amelyek konvex helyzetben vannak.

Érdekes meghatározni a legkisebb megfelelő $N$ számot, legyen tehát $f(n)$ az a legkisebb $N$ egész szám, hogy $N$ általános helyzetű pont közül a síkon mindig van $n$ konvex helyzetben. Ebben a megfogalmazásban Klein Eszter kérdése az, hogy létezik-e egyáltalán $f(n)$ minden $n$ -re.

Világos, hogy $f(3)=3$ és az előbbi észrevétel alapján $f(4)\le 5$ . De egy háromszög három csúcsa és egy belső pontja mutatja, hogy négy általános helyzetű pont nem mindig van konvex helyzetben, tehát $f(4)=5$ . Makai Endre és Turán Pál néhány héten belül belátták, hogy $f(5)=9$ [2], majd Szekeres György még abban az évben bebizonyította, hogy $f(n)$ létezik minden $n$ -re. Természetesen adódott a következő kérdés:

Erdős—Szekeres probléma. Határozzuk meg $f(n)$ értékét.

Nem sokkal később Erdős alaposan megjavította Szekeres korlátját, majd közösen publikálták az eredményt [2], amely szerint minden $n\ge 3$ -ra

$\displaystyle f(n)\le \binom{2n-4}{n-2}+1.$

Sőt, $f(3)$ , $f(4)$ és $f(5)$ értékei alapján a következő merész sejtést is megfogalmazták:

Sejtés. Minden $n\ge 3$ -ra

$\displaystyle f(n)=2^{n-2}+1.$

Ez az egyszerű probléma, eredmény, illetve sejtés korszakalkotó jelentőségűnek bizonyult, egyfelől azért, mert hozzájárult F. P. Ramsey öt évvel korábban megjelent eredményeinek [13] újrafelfedezéséhez és ezzel a Ramsey-elmélet megalapozásához, másfelől azért is, mert megnyitotta az utat ponthalmazok kombinatorikájának tanulmányozásához, ami mára szép és gazdag területe lett a matematikának.

Klein Eszter és Szekeres György nem sokkal később összeházasodtak, ezért a problémát Erdős „Happy End Problem”-nek nevezte.

A legjobb ismert alsó korlát $f(n)$ -re éppen a sejtett értéke, $f(n)\ge 2^{n-2}+1$ , az ezt bizonyító konstrukciót Erdős és Szekeres találták 25 évvel később [3]. A konstrukció $2^{n-2}$ pontból áll és semelyik $n$ pontja sincs konvex helyzetben. Nagyon szimmetrikus és „merev”, ha bármelyik pontját lényegesen elmozdítjuk, keletkezik $n$ pont konvex helyzetben. Ezért a konstrukció alapján könnyen gondolhatja az ember, hogy nem javítható, vagyis a sejtés igaz.

Erdős és Szekeres felső korlátja, $\binom{2n-4}{n-2}\approx 4^n/\sqrt{n}$ , tehát majdnem a négyzete az alsó korlátnak. A problémával nagyon sokan foglalkoztak, szépsége és fontossága miatt, ennek ellenére a felső korlátot először 60 évvel később sikerült megjavítani. 1998-ban Fan Chung és Ron Graham [1] egy unalmas repülőúton azt vizsgálta, hogy ha az igazság pontosan a felső korlát lenne, tehát $f(n)=\binom{2n-4}{n-2}+1$ , akkor hogyan nézne ki egy $\binom{2n-4}{n-2}$ elemű ponthalmaz, amiben még nincs konvex $n$ -szög. Belátták egy nagyon ügyes érveléssel, hogy ilyen ponthalmaz nem létezhet, és ezzel a felső korlátot a lehető legkisebb mértékben, $1$ -gyel megjavították. Ezen felbuzdulva Kleitman és Pachter [6] nagyjából egy hónappal később belátták, hogy $f(n)\le \binom{2n-4}{n-2}+7-2n$ , tehát a javítás mértéke már tart a végtelenbe. Majd újabb egy hónap múlva Tóth és Valtr [16] belátták, hogy $f(n)\le \binom{2n-5}{n-2}+2$ , ami már nagyjából a fele az eredeti korátnak. Ez a három javítás időben olyan közel volt egymáshoz, hogy a Discrete and Computational Geometry című újságnak ugyanabban a számában jelentek meg. Itt leállt a javítások sorozata egy időre, és továbbra is óriasi volt az eltérés a felső és az alsó korát között. 2005-ben Tóth és Valtr [17] kombinálták a saját módszerüket Chung és Graham módszerével, így újra megjavították eggyel a felső korlátot.

2015-ben aztán újra megindult a lavina, Georgios Vlachos, egy MSc diák az MIT-ről, tovább javította a felső korlátot egy $\frac{29}{32}$ [15] faktorral. Hossein Mojarraddal közösen alaposan leegyszerűsítették és tökéletesítették a bizonyítást, végül a $\frac{29}{32}$ faktor helyett egy $\frac{7}{8}$ faktorral javítottak [7]. Közben Norin és Yuditsky [9] is elérték lényegében ugyanezt a korlátot, de még egyszerűbb bizonyítással.

Ezután jött az igazi áttörés, 2016-ban Andrew Suk (ld. a fotón) elképesztő javítással állt elő [14]. Több korábbi módszert, ötletet ügyesen kombinálva sikerült a felső korlátot levinnie az alsó korlát közelébe. Belátta, hogy $f(n)\le 2^{n+6n^{2/3}\log n}$ , ezzel kis híján megoldotta Klein, Erdős és Szekeres problémáját. Az elegáns bizonyítást Andreas Holmsen, Hossein Mojarrad, Pach János és Tardos Gábor tovább egyszerűsítette, és a korlátot is sikerült egy kicsit megjavítaniuk [5]. A pillanatnyilag ismert legjobb felső korlát $f(n)$ -re az övék:

$\displaystyle f(n)\le 2^{n+6\sqrt{n\log n}}.$

Könnyebb áttekinteni a különböző korlátokat, ha nem a fenti $f(n)$ függvényt, hanem az ekvivalens inverz problemát, és az alábbi $g(N)$ függvényt vizsgáljuk. Legyen $g(N)$ az a legnagyobb $n$ egész szám, amelyre $N$ általános helyzetű pont között a síkon mindig található $n$ konvex helyzetben. Az Erdős—Szekeres sejtés ekvivalans azzal, hogy

$\displaystyle g(N)=\lceil\log N\rceil+1$

minden pozitív $N$ egészre. Itt, és a továbbiakban $\log$ a kettes alapú logaritmust jelöli. Az $f(n)$ -re adott alsó és felső korlátok szerepe megfordul. Erdős és Szekeres 1935-ös felső korlátjából [2] alsó korlát lesz $g(N)$ -re, míg az 1961-es alsó korlátjukból [3] $g(N)$ -re felső korlát adódik:

$\displaystyle \frac{\log N}2+h(N)\le g(N)\le\lceil\log N\rceil+1.$

Itt $h(N)$ egy aszimptotikusan $(\log\log N)/2$ közeli függvény, ami az alsó becslés nagyságrendjét nem befolyásolja. Az $f(n)$ -re adott alsó és felső becslés közötti majdnem négyzetes eltérésből a $g(N)$ esetében egy majdnem kettes faktor eltérés marad. Chung és Graham [1] 1-gyel javította az $f(n)$ -re adott felső becslést, ebből a $g(N)$ -re adott aló becslés javítása következik 1-gyel, de csak bizonyos (ritka) $N$ értékekre. A további javítások [6,16,17,15,7,9] ugyancsak eggyel javították csak Erdős és Szekeres alsó becslését a $g(N)$ függvényre, de egyre több és több $N$ érték esetén. Suk átütő eredménye [14] azonban aszimptotikusan bezárta az alsó és felső becslés közötti kettes faktor eltérést:

$\displaystyle g(N)\ge\log N-6\log^{2/3}N\log\log N.$

A hibatag nagyságrendjét [5] tovább csökkenti $\sqrt{\log N\log\log N}$ -re.

Az eddig tárgyalt becslések nem segítettek abban, hogy az $f(n)$ értéket minél több (kicsi) $n$ értékre meghatározzuk. Említettük, hogy Klein Eszter 1932-ben belátta, hogy $f(4)=5$ , valamint hogy Makai és Turán ugyanakkor belátták, hogy $f(5)=9$ . Szekeres György bő hetven év elteltével visszatért a problémához és Lindsay Petersszel közös publikációban [12] belátták, hogy $f(6)=17$ . Ez az eredmény komolyabb komputeres esetvizsgálaton alapul és már Szekeres halála után jelent meg. Az $f(n)$ érték semmilyen $n>6$ számra nem ismert.

Ebben a cikkben áttekintjük az alsó korlát konstrukciót, a felső korlát javításait, a felhasznált módszereket, és vázoljuk a legjobb ismert korlát bizonyítását.

Az Erdős—Szekeres problémának számos általánosítását, módosítását vizsgálták, sok izgalmas és szép eredménnyel. Ezekről ad kiváló összefoglalót magyarul Pach János [10], angolul Morris és Soltan [8]. Suk eredményéről nagyon szórakoztató ismeretterjesztő cikket írt Hartnett [4].

2. Hegyek és völgyek

Szekeres legelső bizonyítása [2] $f(n)$ létezésére a Ramsey tételt használta, amit újra bebizonyított, mert nem ismerte Ramsey publikációját. Erdős javítása, [2] és az összes további javítás legfontosabb segédeszközei a hegyek és völgyek.

Definíció. Rögzítsünk egy $xy$ koordinátarendszert a síkon. Ezentúl egy ponthalmazra akkor mondjuk, hogy általános helyzetű, ha nincs három pontja egy egyenesen és nem egyezik meg két pontjának az $x$ -koordinátája. Legyen $k\ge 2$ és legyenek $p_1$ , $p_2, \ldots$ , $p_k$ általános helyzetű pontok, balról jobbra, vagyis növekvő $x$ -koordináta szerint rendezve. A $p_1,p_2,\ldots,p_k$ pontok egy $k$ -hegyet ( $k$ -völgyet) alkotnak, ha konvex helyzetben vannak és $p_2, \ldots$ , $p_{k-1}$ a $p_1p_k$ egyenes fölött (alatt) van (2. ábra).

A $k$ -völgyek, illetve $k$ -hegyek $k\ge3$ esetén speciális konvex $k$ -szögek. Vegyük észre, hogy három általános helyzetű pont vagy 3-hegyet, vagy 3-völgyet alkot. Erdős és Szekeres bizonyításának alapja a következő észrevétel.

Ha egy $k$ -hegy utolsó pontja és egy $l$ -völgy első pontja megegyezik, akkor valamelyiket egy ponttal meg lehet hosszabbítani.

2. ábra. (a) A $4$ -hegy kiegészíthető $r$ -rel, (b) a $4$ -völgy kiegészíthető $q$ -val.

Valóban, legyen $p$ a $k$ -hegy utolsó pontja és az $l$ -völgy első pontja, legyen $q$ a $k$ -hegy utolsó előtti pontja és legyen $r$ az $l$ -völgy második pontja. Ekkor $qpr$ vagy hegyet, vagy völgyet alkot. Az első esetben $r$ -rel kiegészíthetjük a hegyet egy $k+1$ -heggyé, a második esetben pedig a völgyet egészíthetjük ki $q$ -val egy $l+1$ -völggyé (2. ábra).

Minden $k, l\ge 2$ -re legyen $f(k, l)$ az a legkisebb $f$ szám, amelyre igaz, hogy $f$ általános helyzetű pont között a síkon mindig van egy $k$ -hegy vagy egy $l$ -völgy. Nyilván $f(n)\le f(n,n)$ , ezért az alábbi tételből azonnal következik Erdős és Szekeres korlátja $f(n)$ -re. (Kicsit zavaró, hogy az „általános helyzet” fogalmát szigorítottuk, így elsőre csak az ilyen szigorúbb értelemben vett általános helyzetű $f(n,n)$ méretű síkbeli ponthalmazra adódik, hogy kiválasztható belőle $n$ konvex helyzetű pont. Ez a probléma kezelhető azzal, hogy az $xy$ koordinátarendszert úgy választjuk, hogy ne legyen két pontnak azonos az $x$ koordinátája.) Meglepő módon, $f(n)$ -nel ellentétben, $f(k, l)$ értéket pontosan tudjuk.

1. Tétel. [2]

$\displaystyle f(k, l)=\binom{k+l-4}{k-2}+1.$

Bizonyítás. Először belátjuk, hogy minden $k, l\ge 3$ -ra

$\displaystyle f(k, l)\le f(k-1, l)+f(k, l-1)-1.$

Tekintsünk egy $f(k-1, l)+f(k, l-1)-1$ elemű általános helyzetű $P$ ponthalmazt. Belátjuk, hogy mindenképpen tartalmaz $k$ -hegyet vagy $l$ -völgyet. Legyen $Q$ a $P$ -ben található $(k-1)$ -hegyek utolsó pontjainak a halmaza. Ha $\vert Q\vert\ge f(k, l-1)$ , akkor $Q$ vagy tartalmaz egy $k$ -hegyet, és készen vagyunk, vagy egy $(l-1)$ -völgyet. De ekkor ennek az $(l-1)$ -völgynek az első pontja egyben egy $(k-1)$ -hegy utolsó pontja is, tehát vagy a hegy, vagy a völgy meghosszabbítható és megint készen vagyunk. Vagyis feltehetjük, hogy $\vert Q\vert\le f(k, l-1)-1$ , ekkor viszont $\vert P\setminus Q\vert\ge f(k-1, l)$ , tehát $P\setminus Q$ tartalmaz egy $l$ -völgyet és ismét készen vagyunk, vagy egy $k-1$ -hegyet, ami ellentmondás, mert ennek az utolsó pontja $Q$ -hoz tartozna.

Legyen $g(k, l)=\binom{k+l-4}{k-2}+1$ . Könnyű ellenőrizni, hogy

$\displaystyle g(k, l)=g(k-1, l)+g(k, l-1)-1.$

Ezenkívül ha $k=2$ vagy $l=2$ , akkor $f(k, l)=g(k, l)$ . Ezekből pedig indukcióval adódik, hogy minden $k, l\ge 2$ -re $f(k, l)\le g(k, l)$ .

Az alsó korláthoz minden $k, l\ge 2$ -re konstruálunk egy $P(k,l)$ ponthalmazt, amely éppen $\binom{k+l-4}{k-2}$ pontból áll és nem tartalmaz $k$ -hegyet és $l$ -völgyet. A $k=2$ , illetve $l=2$ esetben egy egy pontból álló halmaz jó lesz. Tegyük fel, hogy már megkonstruáltuk a $P(k-1, l)$ és a $P(k, l-1)$ ponthalmazokat. Helyezzük el őket egymás mellé úgy, hogy $P(k-1, l)$ az $y$ -tengelytől balra, $P(k, l-1)$ pedig jobbra legyen, $P(k-1, l)$ minden pontja a $P(k, l-1)$ pontjai által meghatározott egyenesek fölött legyen, és $P(k, l-1)$ minden pontja a $P(k-1, l)$ pontjai által meghatározott egyenesek alatt legyen. Az utóbbi két feltétel biztosítható azzal, ha a $P(k-1, l)$ ponthalmazt az $y$ -tengellyel párhuzamosan megfelelő magasra toljuk. Ekkor minden $P(k-1, l)$ -beli hegy maximum egy $P(k, l-1)$ -beli ponttal egészíthető ki, és fordítva, minden $P(k, l-1)$ -beli völgy maximum egy $P(k-1, l)$ -beli ponttal egészíthető ki. Ebből adódik, hogy az így kapott $\binom{k+l-5}{k-2}+\binom{k+l-5}{k-3}=\binom{k+l-4}{k-2}$ elemű $P(k,l)$ halmaz nem tartalmaz sem $k$ -hegyet, sem $l$ -völgyet. $\Box$

Vegyük észre, hogy ha $n$ pont konvex helyzetben van, akkor felbontható két részhalmaz úniójára, amiből az egyik hegy, a másik völgy. A hegy a konvex $n$ -szög „teteje”, a völgy az „alja” lesz. Ha feltesszük, hogy a pontok $x$ -koordinátája páronként különböző, akkor a hegynek és a völgynek két közös pontja is lesz: a legkisebb és legnagyobb $x$ -koordinátájú csúcsa a konvex $n$ -szögnek. Láttuk, hogy $f(n,n)$ általános helyzetű pont közül mindig kiválaszthatunk $n$ -et konvex helyzetben: egy $n$ -hegyet, vagy egy $n$ völgyet. Találhatunk viszont $f(n,n)-1$ pontot általános helyzetben, hogy nincs köztük sem $n$ -hegy, sem $n$ -völgy. Egy ilyen ponthalmaz nem tartalmaz $2n-3$ pontot konvex pozicióban, hiszen az ellentmondana a fentebbi felbontásnak hegyre és völgyre.

Ez a gondolatmenet jól mutatja, hogy $g(N)$ értékere (ez a legnagyobb $n$ szám, hogy $N$ általános helyzetű pontból mindig kiválasztható $n$ konvex helyzetben) Erdős és Szekeres által adott alsó és felső becslések között miért körülbelül egy kettes faktor differencia van: Pontosan tudjuk, hogy mekkora hegy vagy völgy választható ki $N$ általános helyzetű pont közül, de azt már nehezebb meghatározni, hogy ezek mikor „illeszthetőek össze” egy konvex ponthalmazzá.

A fenti gondolatmenetet direktben is használhatjuk arra, hogy $f(n)$ -re alső becslést adjunk. Ha $k+l=n+3$ , akkor $f(n)\ge f(k,l)$ , hiszen $n$ konvex helyzetű pont között van $k$ -hegy vagy $l$ -völgy. A korábban megkonstruált $P(k,l)$ ponthalmazok ügyes kombinálásával kissé erősebb alsó becslést kapunk, ami egyben megegyezik $f(n)$ sejtett értékével is:

2. Tétel. [3]

$\displaystyle f(n)\ge 2^{n-2}+1.$

Bizonyítás. Legyen $n\ge 4$ . Minden $i$ -re ( $2\le i\le n$ ) helyezzük el $P(i, n+2-i)$ egy nagyon pici és nagyon lapos példányát az $(i, i^2)$ pont közelébe úgy, hogy a pontjai által meghatározott egyenesek mind majdnem vizszintesek. Nevezzük ezeket blokkoknak. Mindez azért lehetséges, mert a $P(i,j)$ ponthalmazt szabadon eltolhatjuk, kicsinyíthetjük, sőt „lapíthatjuk” is (alkalmazhatunk affin transzformációt az $y$ -tengely irányában), mindez nem befolyásolja hogy mekkora hegyek és völgyek vannak a ponthalmazban. Legyen $P_n$ a kapott halmaz. Világos, hogy

$\displaystyle \vert P_n\vert=\sum_{i=2}^{n}\vert P(i, n+2-i)\vert=\sum_{i=0}^{n-2}\binom{n-2}{i}=2^{n-2}.$

Azt állítjuk, hogy $P_n$ nem tartalmaz konvex $n$ -szöget. Legyen $Q$ egy konvex ponthalmaz $P_n$ -ben. Legyen $P(k, n+2-k)$ a legalsó blokk, amiben $Q$ -nak van pontja, és $P(l, n+2-l)$ a legfelső. Ha $k=l$ , akkor $Q$ a $P(k, n+2-k)$ blokk része, így a tétel kimondása előtti gondolatmenet alapján $\vert Q\vert\le n-1$ . Ha viszont $k<l$ , akkor $Q$ $P(k, n+2-k)$ -ből egy völgyet tartalmaz, amelynek a mérete legfeljebb $n+1-k$ , $P(l, n+2-l)$ -ből egy hegyet, aminek a mérete legfeljebb $l-1$ , és a köztük levő $k-l-1$ blokk mindegyikéből legfeljebb egy pontot.

Ezért $\vert Q\vert\le n+1-k+l-1+k-l-1=n-1$ . $\Box$

3. Javítások

Mint említettük, az első javítást Chung és Graham érte el 1998-ban, [1]. Azt látták be, hogy $f(n)\le f(n,n)-1=\binom{2n-4}{n-2}$ . Tekintsünk egy $f(n,n)-1$ méretű ponthalmazt. Ha tartalmaz egy $n$ -hegyet vagy $n$ -völgyet, akkor készen vagyunk. Ha nem, akkor viszont Chung és Graham megmutatják, hogy található egy $n-1$ -hegy és „alatta” egy pont, vagy egy $n-1$ -völgy és „fölötte” egy pont, ami egy konvex $n$ -szöget alkot.

A következő javítás Kleitman és Pachter eredménye, [6]. Észrevették, hogy az Erdős—Szekeres-féle hegyes-völgyes bizonyítás tetszőleges $xy$ koordinátarendszerben elmondható. Úgy forgatták el a koordinátarendszert, hogy a konvex burok egyik éle függőleges legyen, és ezt a szakaszt „duplán” használták. Kiterjesztették a hegy és a völgy definícióját úgy, hogy ez a függőleges él lehet egy hegynek és egy völgynek is az utolsó éle. Ezzel egy kicsit jobb rekurziót kaptak, és azt, hogy $f(n)\le \binom{2n-4}{n-2}-2n+7$ .

Ezután következett Tóth és Valtr javítása, [16]. A módszerük lényege az, hogy a forgatásnál sokkal általánosabb transzformációt alkalmaznak a hegy-völgy érvelés előtt, mégpedig egy alkalmas projektív transzformációt. Tóth és Valtr azt látták be, hogy $f(n)\le f(n-1,n)+1$ . Legyen $P$ egy $f(n-1,n)+1$ elemű ponthalmaz és $p$ a konvex burok egy csúcsa. Legyen $Q=P\setminus\{ p\}$ . Legyen $\ell$ egy $p$ -t tartalmazó egyenes, amelynek $Q$ minden pontja ugyanazon az oldalán van. Alkalmazzunk egy projektív transzformációt, amely $\ell$ -et a végtelen távoli egyenesbe viszi, $p$ -t az $y=-\infty$ végtelen távoli pontba, $Q$ -t pedig az $R$ halmazba. Mivel $\vert R\vert=f(n-1,n)$ , $R$ tartalmaz egy $n-1$ -hegyet vagy egy $n$ -völgyet. Ha $n$ -völgyet tartalmaz, akkor könnyen látható, hogy a megfelelő pontok $Q$ -ban is konvex helyzetben vannak. Ha $n-1$ -hegyet tartalmaz, akkor pedig a megfelelő pontok és $p$ együtt is konvex helyzetben vannak. Tehát kész vagyunk.

A következő javítás nem túl izgalmas, ugyancsak Tóth és Valtr, [17], a fenti $P\setminus\{ p\}$ halmazra hasonlóan érvelt, mint Chung és Graham, így újból 1-et faragtak a korlátból.

További tíz évvel később Georgios Vlachos következett, [15]. Gondolatmenete úgy indul, mint Tóth és Valtr bizonyítása: Legyen $P$ egy ponthalmaz, amely nem tartalmaz $n$ pontot konvex helyzetben és legyen $p$ egy pontja a konvex burkon. Legyen $Q=P\setminus\{ p\}$ . Legyen $\ell$ egy $p$ -t tartalmazó egyenes, amelynek $Q$ minden pontja ugyanazon az oldalán van. Alkalmazzunk egy projektív transzformációt, amely $\ell$ -et a végtelen távoli egyenesbe viszi, $p$ -t az $y=-\infty$ végtelen távoli pontba, $Q$ -t pedig az $R$ halmazba.

Az eddigiek alapján megállapíthatjuk, hogy $R$ nem tartalmaz $n-1$ -hegyet és $n$ -völgyet. Sőt, nem tartalmaz olyan $r$ pontot, amely egyszerre végpontja egy $n-1$ -völgynek és kezdőpontja egy $n-2$ -hegynek.

Vlachos egy ennél bonyolultabb tiltott konfigurációt talált.

3. Lemma [15] Tegyük fel, hogy az $R$ ponthalmaz tartalmaz egy $r$ pontot, amely (1) egy $n-2$ -völgy végpontja, (2) egy $n-2$ -hegy kezdőpontja, (3) egy $n-1$ -völgy kezdőpontja, és az $n-1$ -völgy végpotja nem esik egybe az $n-2$ -hegy második pontjával.

Ekkor $R$ tartalmaz egy $n-1$ -hegyet vagy $n$ pontot konvex helyzetben, következésépp $P$ tartalmaz $n$ pontot konvex helyzetben.

3. ábra. Vlachos tiltott konfigurációja.

Ez a bonyolult tiltott konfiguráció egy jobb rekurzióra adott lehetőséget, mint az eredeti, Vlachos ennek felhasználásával azt kapta, hogy

$\displaystyle f(n)\le \binom{2n-5}{n-2}-\binom{2n-8}{n-3}+\binom{2n-10}{n-3}+2\approx \frac{29}{64}\binom{2n-4}{n-2}.$

A gondolatmenetet tovább finomitották és egyszerűsítették Hossein Mojarraddal [7], es azt kapták, hogy

$\displaystyle f(n)\le \binom{2n-5}{n-2}-\binom{2n-8}{n-3}+2\approx \frac{7}{16}\binom{2n-4}{n-2}.$

Norin és Yuditsky [9] is ezt a tiltott konfigurációt használták, a korlátjuk lényegében ugyanennyi, sőt, valamivel gyengébb, de az ő érvelésük nagyon egyszerű, impozáns, és remekül rámutat arra, hogy az új tiltott konfiguráció miért ad jobb korlátot. Nagyon élvezetes olvasmány.

4. Suk áttörése

Sok konvex $n$ -szög

Legyen $n\ge 3$ es legyen $Q$ egy konvex $n$ -szög. Legyen $R=\{p_1,\dots,p_n\}$ $Q$ csúcsainak halmaza egy fix körüljárás szerint felsorolva. Tehát $R$ konvex helyzetben van. Tekintsük a sík azon $y\notin R$ pontjait, amire $R\cup\{y\}$ is konvex helyzetű. Ezek a pontok $n$ „tüskét” alkotnak, ahol az $i$ -edik tüske (jelöljük ezt $T_i$ -vel) azon pontokbol áll, amelyeket az $p_ip_{i+1}$ egyenes elválaszt $Q$ belsejétől, de sem a $p_{i-1}p_i$ sem a $p_{i+1}p_{i+2}$ egyenes nem választ el $Q$ belsejétől (4. ábra). Itt az indexeket modulo $n$ értjük. Ha $n\ge5$ , akkor a tüskék közül legfeljebb kettő lehet végtelen tartomány, a többi tüske háromszög lesz. Vegyük észre, hogy akárhogy is veszünk ki egy-egy pontot mindegyik tüskéből, a kapott ponthalmaz konvex helyzetű lesz. A következő lemma tehát nagyon sok konvex $n$ -szöget talál egy általános helyzetű ponthalmazban, ráadásul ezek jól struktúráltan helyezkednek el. Ez Pór Attila és Pavel Valtr [11] eredménye kicsit átfogalmazva.

4. ábra. A $Q$ konvex sokszög és a hozzá tartozó $T_i$ tüskék.

4. Lemma [11] Legyen $P$ általános helyzetű ponthalmaz a síkon. Ha $N=\vert P\vert>f(2n)$ , akkor található egy $n$ elemű $R\subset P$ ponthalmaz konvex helyzetben, hogy az általa meghatározott $T_i$ tüskékre

$\displaystyle \prod_{i=1}^n\vert T_i\cap P\vert\ge\frac{N^n}{(f(2n))^{2n}}.$

Bizonyítás. Egy egyszerű kettős leszámolással belátjuk, hogy sok konvex $2n$ -szög van $P$ -ben. Minden $f(2n)$ elemű részében $P$ -nek találunk legalább egy konvex $2n$ -szöget. Ez tehát $\binom N{f(2n)}$ konvex $2n$ -szög, de ezek nem mind különbözőek. Egy fix $2n$ elemű konvex helyzetű halmaz $P$ pontosan $\binom{N-2n}{f(2n)-2n}$ darab $f(2n)$ elemű részhalmazában szerepel, tehát legalább

$\displaystyle \frac{\binom N{f(2n)}}{\binom{N-2n}{f(2n)-2n}}\ge\frac{N^{2n}}{(f(2n))^{2n}}$

különböző konvex $2n$ -szöget találtunk $P$ -ben.

Most hagyjuk el ezen konvex $2n$ -szögek minden második csúcsát. Így egy konvex $n$ -szöget kapunk. Nagyon durva felső becslést alkalmazva látjuk, hogy ilyen konvex $n$ -szög maximum $N^n$ van, így legalább $N^n/(f(2n))^{2n}$ különböző konvex $2n$ -szögből ugyanazt az $R$ konvex $n$ -szöget kell kapnunk. Márpedig ha egy konvex $2n$ -szög minden második csúcsát elhagyva pont $R$ -et kapjuk, akkor az $R$ -hez tartozó $T_i$ tüskék mindegyikéből pontosan egy pontot hagytunk el, így a szóba jöhető konvex $2n$ -szögek száma maximum $\prod_{i=1}^n\vert T_i\cap P\vert$ . Ez pont a lemma állítását igazolja. $\Box$

Áttekintés

Andrew Suk bizonyítása így foglalható össze. Megfelelően nagy általános helyzetű ponthalmazban próbál konvex $n$ -szöget találni. Ehhez a 4. Lemmát használja $n$ helyett egy sokkal kisebb $k$ értékre, és az így talált $Q$ konvex $k$ -szög $T_i$ tüskéiben használja külön-külön Erdős és Szekeres hegyekre és völgyekre vonatkozó éles eredményét. Nem kétféle (hegy és völgy) részhalmazt keres $T_i$ -ben, hanem négyféle „irányultságot” különböztet meg: (1) a $Q$ -felől nézve domború (az $Q$ sokszögre „ráboruló”) íveket; (2) a $Q$ felől nézve homorú ( $Q$ -tól „elhajló”) íveket; (3) a balról, $T_{i-1}$ felől nézve domború íveket; és végül (4) a jobbról, $T_{i+1}$ -felől nézve domború íveket. A pontos definiciót lásd később. A gondolatmenet lényege, hogy (1)-es típusú íveket minden második tüskéből egyesíteni lehet, és még így is konvex helyzetű ponthalmazokat kapunk (5. ábra), valamint egy $T_i$ tüskében lévő „jobbról domború”, azaz (4)-es típusú ív és a következő $T_{i+1}$ tüskében lévő „balról domború”, azaz (3)-as típusú ív úniója is konvex helyzetű (6. ábra).

Ha $k$ megfelelően kicsi $n$ -hez képest, akkor a 4. Lemma nagyon hatékony. Legyen $Q$ a lemma által biztosított $k$ -szög. A $Q$ -hoz tartozó egyetlen átlagos $T$ tüskében a ponthalmazunk $N$ pontjából legalább $N/(f(2k))^2$ darab esik, szóval alig vesztünk valamit. A következő lépés a $T$ -be eső pontpárok közötti szakaszok osztályozása „laposra” , azaz a $Q$ $k$ -szög $T$ -t határoló oldalával majdnem párhuzamosra és „meredekre”. Egy klasszikus kombinatorikai tétel, a Dilworth-tétel biztosítja, hogy találunk egy nagy halmazt a $T$ -ben, hogy a köztük levő szakaszok mind laposak, vagy mind meredekek. A lapos esetben a klasszikus hegy-völgy tétel alapján találunk nagy (1)-es vagy (2)-es típusú ívet, a meredek esetben ugyanez a tétel biztosítja, hogy nagy (3)-as vagy (4)-es típusú ívet találunk. Itt az (1)-es típusú ívekből olyan sokat tudunk összefűzni, hogy ha így sem kapunk konvex $n$ -szöget, akkor a lapos részek nagyon kicsik kell, hogy legyenek. A meredek részeknél meg épp két ívet tudunk összefűzni, ez adja a körülbelül kettes faktor javulást (konvex $n/2$ -szög helyett konvex $n$ -szög), ami Suk bizonyításának a lényege.

A fenti intuíciót a következőkben precízebbé tesszük. A részletekben Suk eredeti bizonyítása, [14], helyett a Holmsen-Mojarrad-Pach-Tardos bizonyítást követjük, [5].

Részletek

Rögzítsünk egy nagy $n$ természetes számot és egy általános helyzetű $P$ ponthalmazt a síkban, ami nem tartalmaz $n$ pontot konvex helyzetben. Célunk egy felső korlátot adni $n$ függvényében az $N=\vert P\vert$ számosságra. Ez a korlát (pontosabban az eggyel nagyobb szám) nyilván $f(n)$ -nek is korlátja.

Először is választunk egy páros $k$ számot, mely jóval kisebb $n$ -nél. Alkalmazzuk a 4. Lemmát erre a $k$ számra. Ha $N\ge f(2k)$ , akkor kapunk egy $Q=p_1p_2\dots p_k$ konvex $k$ -szöget úgy hogy a hozzátartozó $T_i$ tüskék teljesítik, hogy

$\displaystyle \prod_{i=1}^k\vert P_i\vert\ge\frac{N^k}{(f(2k))^{2k}},$

(1)

ahol $P_i=P\cap T_i$ .

Tegyük fel az egyszerűség kedvéért, hogy a $T_i$ tüskék mind háromszögek. Ez a feltevés két különböző okból sem jelent valódi megszorítást. Egyfelől pontosan ugyanezt a becslést lehet nagyon hasonlóan bizonyítani a feltételezés nélkül is, csak ehhez a végtelen tüskékben keresett ponthalmazokat kicsit körülményesebben kellene definiálnunk. Másfelől pedig használhatjuk, hogy $k\ge5$ esetén legfeljebb kettő tüske nem háromszög. Ha ezekben a végtelen tüskékben egyáltalán nem keresünk konvex helyzetű ponthalmazokat, és csak a véges tüskékre koncentrálunk, akkor a hasonló módszerrel kapott becslés csak egy konstans faktorral lesz rosszabb, azaz a kitevőben szereplő hibatag csak egy additív konstanssal nő.

Most egy fix $P_i$ halmazt vizsgálunk és definiálunk rajta egy részbenrendezést. Az $x,y\in P_i$ pontokra azt mondjuk, hogy $x\prec_iy$ , ha a $p_{i-1}p_{i+2}y$ háromszög tartalmazza a $p_{i-1}p_{i+2}x$ háromszöget. Itt és a továbbiakban az indexeket modulo $k$ értjük. Ez nyilván részbenrendezés. A bizonyítás áttekintésében az összehasonlítható pontpárok közötti szakaszt mondtuk meredeknek, a nem összehasonlíthatóak közöttit meg laposnak. Láncnak mondjuk $P_i$ egy részhalmazát, ha bármely két eleme összehasonlítható ebben a részbenrendezésben, antiláncnak meg az olyan részhalmazt mondjuk, amely nem tartalmaz összehasonlítható elemeket. Dilworth tétele (illetve annak egyszerűbb iránya) szerint van olyan $Q_i$ lánc és $R_i$ antilánc $P_i$ -ben, amelyekre

$\displaystyle \vert Q_i\vert\cdot\vert R_i\vert\ge\vert P_i\vert.$

(2)

Válasszuk meg a koordináta-rendszert úgy, hogy a $p_{i-1}p_i$ egyenes az $y$ -tengellyel párhuzamos (függőleges) legyen, és $p_i$ $p_{i-1}$ fölött helyezkedjen el. Ezzel meghatároztuk, hogy $R$ részhalmazai közül melyek a hegyek és melyek a völgyek. Legyen $A_i$ és $B_i$ a legnagyobb hegy, illetve völgy az $R_i$ antiláncon belül. A bizonyítás áttekintésében ezeket hívtuk (1)-es és (2)-es típusú íveknek. Az $R_i$ halmazban nincs sem $(\vert A_i\vert+1)$ -hegy sem $(\vert B_i\vert+1)$ -völgy, így az 1. Tétel szerint

$\displaystyle \vert R_i\vert\le\binom{\vert A_i\vert+\vert B_i\vert-2}{\vert A_i\vert-1}.$

(3)

Meg kell még említeni, hogy az 1. Tétel csak olyan ponthalmazokra alkalmazható, ahol az $x$ -koordináták mind különböznek, de mivel feltettük, hogy a $T_i$ tüske egy háromszög, $R$ pedig egy antilánc, ez teljesül.

Most forgassuk el a koordináta-rendszert, mégpedig úgy, hogy $p_{i+1}$ épp függőlegesen $p_i$ fölött legyen. Legyen $C_i$ , illetve $D_i$ a legnagyobb hegy, illetve völgy a $Q_i$ láncban erre a koordináta-rendszerre nézve. A bizonyítás áttekintésében ezeket hívtuk (3)-as, illetve (4)-es típusú íveknek. Mivel $Q_i$ lánc, pontjainak $x$ -koordinátái különbözőek, így alkalmazhatjuk az 1. Tételt:

$\displaystyle \vert Q_i\vert\le\binom{\vert C_i\vert+\vert D_i\vert-2}{\vert C_i\vert-1}.$

(4)

Egyszerű geometriai megfontolás mutatja, hogy $A_1\cup A_3\cup\cdots\cup A_{k-1}$ konvex helyzetben van (5. ábra), és ugyanez vonatkozik $A_2\cup A_4\cup\cdots\cup A_k$ -ra is. (Itt is használjuk a feltevést, hogy minden tüske véges.) Feltettük, hogy a $P$ ponthalmazban nincs $n$ pont konvex helyzetben, így

$\displaystyle \sum_{i=1}^k\vert A_i\vert<2n.$

(5)

5. ábra. $A_2\cup A_4$ konvex helyzetben van.

A $B_i$ halmazokat nem tudjuk kombinálni, de egyenként mindegyik konvex helyzetben van, tehát

$\displaystyle \vert B_i\vert<n$

(6)

teljesül minden $i$ -re.

Nem nehéz azt sem belátni, hogy a $D_i\cup C_{i+1}$ halmaz is konvex helyzetben van minden $i$ esetén (6. ábra), így $\vert D_i\vert+\vert C_{i+1}\vert<n$ , tehát

$\displaystyle \sum_{i=1}^k(\vert C_i\vert+\vert D_i\vert)<kn.$

(7)

6. ábra. $D_2\cup C_3$ konvex helyzetben van.

A bizonyítás befejezéséhez már csak némi számolásra van szükség. Először a (3) és (6) egyenlőtlenségekből, valamint egy elemi binomiális együtthatókra vonatkozó becslésből kapjuk az alábbiakat:

$\displaystyle \vert R_i\vert\le\binom{\vert A_i\vert+\vert B_i\vert-2}{\vert A_i\vert-1}<\vert B_i\vert^{\vert A_i\vert}<n^{\vert A_i\vert}.$

Szorozzuk össze ezt a becslést minden $i$ -re és alkalmazzuk az (5) egyenlőtlenséget:

$\displaystyle \prod_{i=1}^n\vert R_i\vert<n^{\sum_{i=1}^n\vert A_i\vert}<n^{2n}$

(8)

A (4) egyenlőtlenségnél a binomiális együtthatót durván becsülve kapjuk, hogy $\vert Q_i\vert<2^{\vert C_i\vert+\vert D_i\vert}$ és így a (7) egyenlőtlenséget is használva adódik, hogy

$\displaystyle \prod_{i=1}^n\vert Q_i\vert<2^{\sum_{i=1}^n(\vert C_i\vert+\vert D_i\vert)}<2^{kn}.$

(9)

Végül az (1), (2), (8) és (9) egyenlőtlenségekből kapjuk, hogy

$\displaystyle \frac{N^k}{(f(2k))^{2k}}\le\prod_{i=1}^k\vert P_i\vert\le\left(\p... ...^k\vert Q_i\vert\right) \left(\prod_{i=1}^k\vert R_i\vert\right)<2^{kn}n^{2n}.$

Itt elég a durva $f(2k)\le f(2k,2k)=\binom{4k-4}{2k-2}\le2^{4k}$ becslést alkalmaznunk, és átrendezéssel kapjuk, hogy

$\displaystyle N<2^{n+8k+2n\log n/k}.$

Látszik, hogy $k$ legjobb választása $\sqrt{n\log n}/2$ körül van, ahonnan

$\displaystyle f(n)\le2^{n+8\sqrt{n\log n}+1}$

lesz a végső korlátunk. A $+1$ azért került a kitevőbe, mert $k$ értéke nem mindig lehet pont $\sqrt{n\log n}/2$ , hiszen páros egész számot kell választanunk.

Itt $f(n)$ sejtett értéke (és egyben az alsó korlátja) $2^{n-2}+1$ , így a fenti becslés kitevőjében $8\sqrt{n\log n}+3$ tekinthető a hibatagnak. Ebben a 8-as faktor 6 alá csökkenthető azzal, ha $f(2k)$ értékének becslésére a bizonyításban nem Erdős és Szekeres eredeti felső korlátját használtuk, hanem az épp bizonyított jobb becslést alkalmazzuk indukcióval.

Irodalomjegyzék

[1] F. R. K. Chung and R. L. Graham, Forced convex $n$ -gons in the plane, Discrete and Computational Geometry 19 (1998), 367—371.

[2] P. Erdős, G. Szekeres, A combinatorial problem in geometry, Compositio Mathematica 2 (1935), 463—470.

[3] P. Erdős, G. Szekeres, On some extremum problems in elementary geometry, Ann. Univ. Sci. Eötvös Sect. Math 3-4 (1961), 53—62.

[4] K. Hartnett, A Puzzle of Clever Connections Nears a Happy End, Quanta Magazine (2017).

[5] A. Holmsen, H. Mojarrad, J. Pach, G. Tardos, Two extensions of the Erdős—Szekeres problem, arXiv:1710.11415, (2017).

[6] D. J. Kleitman and L. Pachter, Finding convex sets among points in the plane, Discrete and Computational Geometry 19 (1998), 405—410.

[7] H. Mojarrad, G. Vlachos, An Improved Upper Bound for the Erdős—Szekeres Conjecture, Discrete and Computational Geometry 56 (2016), 165—180.

[8] W. Morris, V. Soltan, The Erdős—Szekeres problem on points in convex position—a survey, Bulletin of the American Mathematical Society 37, (2000), 437—458.

[9] S. Norin, Y. Yuditsky, Erdős—Szekeres without induction, Discrete and Computational Geometry 55 (2016), 963—971.

[10] Pach J., A Happy End probléma — A kombinatorikus geometria kezdetei, Új matematikai mozaik (Hraskó A., szerk.) Typotex, Budapest, 2002, 223-242.

[11] A. Pór and P. Valtr, The partitioned version of the Erdős—Szekeres theorem, Discrete and Computational Geometry 28 (2002), 625—637.

[12] G. Szekeres, L. Peters, Computer solution to the 17-point Erdős—Szekeres problem, The ANZIAM Journal 48 (2006), 151—164.

[13] F. P. Ramsey: On a problem of formal logic, Proceedings of the London Mathematical Society 30 (1930), 338—384.

[14] A. Suk, On the Erdős—Szekeres convex polygon problem, Journal of the American Mathematical Society 30 (2017), 1047—1053.

[15] G. Vlachos, On a conjecture of Erdős and Szekeres, arXiv:1505.07549, (2015).

[16] G. Tóth and P. Valtr, Note on the Erdős—Szekeres theorem, Discrete and Computational Geometry 19 (1998), 457—459.

[17] G. Tóth and P. Valtr, The Erdős—Szekeres theorem, upper bounds and generalizations, Discrete and Computational Geometry — Papers from the MSRI Special Program (J. E. Goodman et al. eds.), MSRI Publications 52 Cambridge University Press, Cambridge (2005), 557—568.

Tardos Gábor és Tóth Géza

MTA Rényi Alfréd Matematikai Kutatóintézet

Tardos Gábor kutatásait az MTA Kriptográfia „Lendület” programja valamint a Nemzeti Kutatási és Innovációs Hivatal K-116769-es és SSN-117879-es számú programjai támogatják, Tóth Géza kutatásait a Nemzeti Kutatási és Innovációs Hivatal K-111827-es számú programja támogatja.

Andrew Suk bemutatása: https://math.ucsd.edu/people/profiles/andrew-suk/