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

5. Pontok helyett konvex halmazok

5. Pontok helyett konvex halmazok

Bisztriczky Tibor és Fejes Tóth Gábor [3],[5] rájött, hogy az Erdős–Szekeres-tétel olyan rendszerekre is általánosítható, melyek pontok helyett tetszőleges konvex testekből (zárt konvex halmazokból) állnak. Konvex testek egy rendszeréről azt mondjuk, hogy konvex helyzetben van, ha egyik eleme sincs benne a többi egyesítésének konvex burkában (ld. 6. ábra).

6. ábra. Konvex helyzetben lévő testek

Ahhoz, hogy kimondhassuk, hogy páronként diszjunkt, konvex testek minden elég nagy rendszerének van sok konvex helyzetben lévő eleme, szükségünk van valamilyen további feltételre, ami annak a pontokra vonatkozó tulajdonságnak az általánosítása, hogy nincs három kollineáris elem. Annak illusztrálására, hogy milyen feltételre lehet szükség, tekintsük az s 1 , , s n szakaszokat a síkban, ahol s i két végpontja ( i , i 2 ) és ( i , - i 2 ) . Nyilvánvaló, hogy ezek között a szakaszok között még három sincs konvex helyzetben.

5.1. Tétel [3]. Minden m ? 4 egészhez van egy legkisebb F = F ( m ) szám, amely eleget tesz a következő feltételnek: akárhogyan is veszünk fel legalább F páronként diszjunkt, konvex testet a síkon úgy, hogy bármely három konvex helyzetben van, mindig kiválasztható közülük m , ami konvex helyzetben van.

Bisztriczky és Fejes Tóth mindkét bizonyítása a Ramsey-tételt használta, ezért az F ( m ) függvényre csak gyenge, szuper-exponenciális felső korlátot szolgáltatott. A ma ismert legjobb becslést Tóth Gézával közösen találtuk.

5.2. Tétel [22]. Minden m ? 4 egész számra

F ( m ) ? 2 n - 4 n - 2 2 + 1 .

Bizonyítás. Legyen K egy legalább 2 n - 4 n - 2 2 + 1 páronként diszjunkt, konvex testből álló rendszer, melynek bármely három eleme konvex helyzetben van. Könnyű belátni, hogy ekkor van egy olyan K ' ? K részrendszer, melynek legalább 2 n - 4 n - 2 + 1 eleme van, és eleget tesz a következő feltételek egyikének:

  1. K ' bármely két eleme elválasztható egy függőleges egyenessel,

  2. van egy olyan függőleges egyenes, amely K ' összes elemét metszi.

Az 1. esetben a hegyek és völgyek fogalmát könnyen kiterjeszthetjük pontokról tetszőleges konvex testekre úgy, hogy a 2.1. Tétel bizonyítása szinte szó szerint megismételhető legyen. Azt kapjuk tehát, hogy ekkor K ' -ben van m -elemű hegy vagy völgy, aminek elemei szükségképpen konvex helyzetben vannak.

A 2. esetben az ábrát célszerű 90 fokkal elfordítani úgy, hogy a K ' elemeit metsző egyenes vízszintes legyen. Egy kis elővigyázatossággal a fenti bizonyítási ötlet most is keresztülvihető, de ennek részleteit ezúttal a nyájas olvasóra bízzuk.

Ismeretes, hogy az m = 4 és m = 5 esetben F ( m ) értéke megegyezik a – pontrendszerekre vonatkozó – Erdős–Szekeres-tételben szereplő f ( m ) számmal [4]. Érdekes lenne eldönteni, hogy vajon F ( m ) = f ( m ) minden m -re.

Felmerül az a kérdés is, hogy az ebben a szakaszban szereplő tételeknél fontos-e feltenni, hogy a szóbanforgó konvex testek páronként diszjunktak. Valamilyen feltételre nyilván szükség van. Amint azt a 7. ábra mutatja, megadható a síkon végtelen sok konvex test (szakasz) úgy, hogy közülük bármely három konvex helyzetben van, de semelyik négy nem rendelkezik ezzel a tulajdonsággal [23].

7. ábra. Bármely 3 szakasz konvex helyzetben van, de semelyik 4 nincs.

Két belső ponttal rendelkező (vagyis nem elfajuló) síkbeli konvex testről azt mondjuk, hogy keresztezik egymást, ha határaik több mint két pontban metszik egymást. Ha az ilyen kereszteződéseket megtiltjuk, akkor a 5.1. Tétel akkor is érvényben marad, ha nem kötjük ki, hogy halmazaink páronként diszjunktak.

5.3. Tétel [23]. Minden m ? 4 egészhez van egy legkisebb F * = F * ( m ) szám, amely eleget tesz a következő feltételnek: akárhogyan is veszünk fel legalább F * páronként nem kereszteződő, belső ponttal rendelkező, konvex testet a síkon úgy, hogy bármely három konvex helyzetben van, mindig kiválasztható közülük m , ami konvex helyzetben van.

Megjegyezzük, hogy ha a 6. ábrán szereplő szakaszokat kissé „felfújjuk” (hogy legyen belső pontjuk), akkor bármely kettő határa négy pontban keresztezi egymást, tehát a 5.3. Tételben szereplő feltétel nem teljesül. Ha az 5.2. Tételt nem feltétlenül diszjunkt szakaszokra kívánjuk általánosítani, akkor nem elég megkövetelnünk, hogy bármely három szakasz konvex helyzetben legyen. Többre van szükség.

5.4. Tétel [23]. Minden m ? 5 egészhez van egy legkisebb F ' = F ' ( m ) szám, ami eleget tesz a következő feltételnek: akárhogyan is veszünk fel legalább F ' szakaszt a síkon úgy, hogy bármely négy konvex helyzetben van, mindig kiválasztható közülük m , ami konvex helyzetben van.