Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

4. Üres sokszögek – egy meglepetés

4. Üres sokszögek – egy meglepetés

Erdős és Szekeres mindig is úgy gondolták, hogy elég sok általános helyzetű pont közül kiválasztható m , melyek konvex helyzetben vannak, és konvex burkukban nincs további pont. Nyomtatásban ez a sejtés mégis talán csak 1978-ban jelent meg [9]. Más szóval úgy képzelték, hogy minden m -re van egy legkisebb g = g ( m ) szám, mely eleget tesz a következő feltételnek: akárhogyan veszünk fel legalább g általános helyzetű pontot a síkon, ezek között mindig van m , amely egy üres konvex m -szöget határoz meg. Sok évvel ezelőtt a Bolyai Társulat egyik konferenciáján Szekeres vázolt is egy bizonyítást erre az állításra, de hamarosan kiderült, hogy a bizonyítás hiányos. Ennek dacára úgy tűnt, hogy csupán technikai jellegű nehézséggel van dolgunk: az üres sokszögek többnyire nagyon hosszúak és vékonyak, ezért kellemetlen kezelni őket.

Nyilvánvaló, hogy g ( 3 ) = 3 , g ( 4 ) = 5 , Harborth [14] pedig belátta, hogy g ( 5 ) = 10 ( ? f ( 5 ) = 9 ) . Nagy meglepetésre a kérdés negatív irányban dőlt el: Horton [15] 1983-ban egy viszonylag egyszerű konstrukció segítségével megmutatta, hogy g ( 7 ) nem létezik!

4.1. Tétel [15]. Megadható tetszőlegesen sok általános helyzetű pont a síkon úgy, hogy ezek közül semelyik 7 sem határoz meg üres konvex hétszöget.

Bizonyítás: Rögzítsünk egy ( x , y ) merőleges koordinátarendszert a síkban, és jelöljük Q 1 -gyel a ( 0 , 0 ) és ( 1 , 0 ) pontokból álló kételemű halmazt. A konstrukció rekurzív.

Tegyük fel, hogy valamely i ? 1 egészre már definiáltunk egy 2 i -elemű Q i halmazt, melyben bármely négyelemű hegy alatt, ill. négyelemű völgy fölött van legalább egy további pont.

Toljuk el a Q i halmazt egy kevéssel jobbra és messzire felfelé úgy, hogy a keletkező Q i ' halmaz eleget tegyen a következő feltételeknek:

  1. Q i és Q i ' elemeinek x -koordinátái felváltva követik egymást,

  2. a Q i pontpárjait összekötő egyenesek mindegyike Q i ' összes pontja alatt halad el, a Q i ' pontpárjait összekötő egyenesek mindegyike pedig Q i pontjai felett.

Legyen Q i + 1 = Q i ? Q i ' . (Ld. 4. ábra.)

4. ábra. Q 4 konstrukciója

Be fogjuk látni, hogy Q i + 1 eleget tesz az indukciós feltevéseknek ( i + 1 -re), vagyis Q i + 1 = 2 i + 1 , és bármely négyelemű hegy alatt, ill. négyelemű völgy fölött van legalább egy további pont. Az első állítás nyilvánvaló.

Tekintsük Q i + 1 egy négyelemű hegyét (ill. völgyét). Ha ennek mind a négy pontja Q i -hez vagy mind a négy pontja Q i ' -höz tartozik, akkor az indukciós feltevés szerint mindig van alatta (ill. felette) további pont. Feltehetjük tehát, hogy a kérdéses hegy (ill. völgy) mind Q i -ből, mind pedig Q i ' -ből tartalmaz legalább egy-egy pontot. Vegyük észre, hogy ekkor a két középső elem feltétlenül Q i ' -höz (ill. Q i -hez) tartozik, tehát a fenti 1. tulajdonság miatt van közöttük legalább egy további pont, ami szükségszerűen a hegy alatt (ill. a völgy felett) helyezkedik el.

Nem nehéz bebizonyítani, hogy Q i + 1 -ben nincs üres konvex hétszög. A feltételek szerint ugyanis egy ilyen H hétszög csúcsai két összefüggő sorozatra bomlanának, melyek közül az egyik Q i ' egy hegye, a másik pedig Q i egy völgye. Az általánosság megszorítása nélkül feltehető, hogy ezek közül Q i völgyének legalább 4 eleme van. Ekkor az indukciós feltevés szerint e völgy felett Q i -nek (tehát Q i + 1 -nek is) van legalább egy további pontja, ami a fenti 2. tulajdonság miatt csak a H hétszög belsejében lehet. Ez ellentmond annak, hogy H üres, vagyis a 4.1. Tételt maradéktalanul bebizonyítottuk.

Érdekes lenne eldönteni, hogy létezik-e (véges-e) az utolsó ismeretlen érték, g ( 6 ) . Más szóval megadható-e tetszőlegesen sok általános helyzetű pont a síkon úgy, hogy ne határozzanak meg egyetlen üres konvex sokszöget sem?

Solymosi József [25], aki Pavel Valtr-hoz [28] hasonlóan matematikus pályáját az Erdős–Szekeres-tétellel kapcsolatos feladatok vizsgálatával kezdte, és doktori disszertációjának is részben ez a témája, erre vonatkozóan a következő érdekes kérdést vetette fel:

4.2. Probléma: Adott n általános helyzetű pont a síkon. Színezzük ki az általuk meghatározott összes szakaszt pirossal és kékkel. Igaz-e, hogy ha n elég nagy, akkor mindig van olyan üres háromszög, amelynek mind a három oldala ugyanolyan színű?

Ha erre a kérdésre a válasz tagadó, akkor g ( 6 ) nem létezik. Tegyük fel ugyanis, hogy minden elég nagy, általános helyzetű pontrendszer meghatároz agy üres konvex H hatszöget. Ha a H csúcsai között futó 6 3 = 15 szakaszt két színnel megszínezzük, akkor mindig találunk egy egyszínű háromszöget, ami persze üres is (hiszen – a Ramsey tételben használt jelöléssel élve – R ( 2 , 2 , 3 ) = 6 ).

Bialostocki, Dierker es Voxman [2] azzal az első pillantásra meglepő ötlettel álltak elő, hogy a nagy üres konvex sokszögek létezésére vonatkozó sejtés esetleg igaz valamilyen „moduláris” értelemben. Hogy a kérdést pontosabban megfogalmazhassuk, szükségünk lesz egy definícióra. Legyen q egy pozitív egész szám, P pedig egy általános helyzetű halmaz. Egy Q ? P részhalmazról azt mondjuk hogy mod q üres konvex sokszöget határoz meg, ha konvex helyzetben van, és P azon elemeinek a száma, melyek Q konvex burkának belsejében vannak osztható q -val (másképpen: egyenlő 0-val mod q ).

4.3. Sejtés [2]: Minden q ? 2 és m ? 3 egészhez van egy olyan legkisebb g = g q ( m ) szám, amely eleget tesz a következő feltételnek: akárhogyan veszünk fel legalább g általános helyzetű pontot a síkon, ezek között mindig van m , mely egy modulo q üres konvex m -szöget határoz meg.

Bialostocki és szerzőtársai észrevették, hogy az m ? q + 2 esetben g q ( m ) létezése könnyen igazolható. Írjuk fel m -et m = i q + 2 + j alakban, ahol i ? 1 és 0 ? j //<// q . Azt állítjuk, hogy g q ( m ) ? f R ( 3 , q , m ) , ahol f és R az Erdős–Szekeres-tételben, ill. a Ramsey-tételben szereplő függvényeket jelenti (ld. a második szakaszban).

5. ábra. Modulo q üres sokszögek konstrukciója

Tekintsünk n ? f R ( 3 , q , m ) általános helyzetű pontot a síkon. Az Erdős–Szekeres-tétel értelmében mindig kiválasztható ezek közül R ( 3 , q , m ) pont, amely konvex helyzetben van. Osszuk be az ezen pontok által meghatározott háromszögeket q osztályba aszerint, hogy a belsejükben lévő pontok száma q -val osztva milyen maradékot ad. Ramsey tétele szerint vannak olyan p 1 , p 2 , , p m pontok (az óra járásával ellentétes irányban számozva), hogy az általuk feszített háromszögek mindegyike ugyanabba az osztályba esik. Jelölje S azt a konvex m - j = i q + 2 -szöget, melynek csúcsai p 1 , p 3 , , p 2 j + 1 , p 2 j + 2 , p 2 j + 3 , , p m . Minden k -ra ( 1 ? k ? j ) vizsgáljuk meg a p 2 k - 1 p 2 k p 2 k + 1 háromszöget. Amennyiben ebben a háromszögben van pont, válasszunk a belsejében egy olyan p 2 k ' pontot, melyre a p 2 k - 1 p 2 k ' p 2 k + 1 háromszög már üres. Ellenkező esetben legyen p 2 k ' = p 2 k .(Ld. 4. ábra.) Világos, hogy a p 1 , p 2 ' , p 3 , p 4 ' , , p 2 j + 1 , p 2 j + 2 , , p m pontok által meghatározott T konvex m -szög belsejében ugyanannyi pont van, mint S belsejében. Ha S tetszőleges pontjából minden átlót behúzunk, akkor az m - j - 2 = i q háromszögre esik szét. Mivel ezen háromszögek mindegyike mod q ugyanannyi pontot tartalmaz, az S (és a T ) sokszög belsejében lévő pontok száma q -val osztható, amit bizonyítani akartunk.

A fenti gondolatmenetből csak egy nagyon gyenge, szuper-exponenciális felső becslés nyerhető a g q ( m ) függvény értékeire. Később Yair Caro [7] egy másik bizonyítást talált, miszerint g q ( m ) ? C q m , ahol C q egy alkalmas, q -tól függő konstans. Mindkét bizonyítás erősen kihasználta az ( m ? q + 2 ) feltevést.

Nemrég Károlyi Gyulával és Tóth Gézával közösen [17] sikerült valamit enyhítenünk ezen a feltételen. Megmutattuk, hogy g q ( m ) minden olyan m -re létezik, ami nagyobb, mint 5 6 q + C . (Itt C egy 50-nél kisebb konstans.) Egy síkbeli ponthalmazról azt mondjuk, hogy majdnem konvex helyzetben van, ha általános helyzetű és minden általa meghatározott háromszög belsejében legfeljebb egy pont van. A bizonyítás egyik döntő eleme a következő tétel:

4.4. Tétel [17]. Minden m ? 3 egészhez van egy legkisebb g * = g * ( m ) szám, amely eleget tesz a következő feltételnek: akárhogyan veszünk fel legalább g * majdnem konvex helyzetben lévő pontot a síkon, ezek között mindig van m , ami egy üres konvex m -szöget határoz meg.