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

2. Ramsey és tételének újrafelfedezése

2. Ramsey és tételének újrafelfedezése

Szekeres fent említett bizonyítása a következő állításon alapult, melyről hamarosan kiderült, hogy néhány évvel korábban Frank Plumpton Ramsey már felfedezte és publikálta a Londoni Matematikai Társulat Közleményeiben [24].

Ramsey tétele. Tetszőleges i , j és k ? i pozitív egészekhez van egy csak tőlük függő R = R ( i , j , k ) szám, amely eleget tesz a következő feltételnek: akárhogyan osztjuk be egy legalább R -elemű H halmaz összes i -elemű részhalmazát j osztályba, mindig van H -nak olyan k -elemű részhalmaza, melynek összes i -elemű része ugyanabba az osztályba esik.

Ebből valóban könnyen levezethető az

Erdős–Szekeres-tétel. Minden m ? 4 egészhez van egy legkisebb f ( m ) szám, ami eleget tesz a következő feltételnek: akárhogyan is veszünk fel legalább f ( m ) általános helyzetű pontot a síkon, mindig kiválasztható közülük m , ami konvex helyzetben van.

A tételre két bizonyítást is adunk.

Első bizonyítás. Az m = 4 esetet a fentiekben már elintéztük, tehát feltehető, hogy m ? 5 . Vegyünk egy n ? R ( 4 , 2 , m ) pontból álló általános helyzetű P halmazt a síkon, és osszuk be P összes 4-elemű részhalmazát 2 osztályba aszerint, hogy konvex helyzetben vannak vagy sem. Ramsey tétele szerint van olyan m -elemű Q ? P részhalmaz, melynek minden négyese ugyanabba az osztályba esik. Klein Eszter észrevétele szerint Q -nak van legalább egy olyan négyese, amely konvex helyzetben van. Következésképp Q összes négyese konvex helyzetben van, tehát Q maga is konvex helyzetben van.

Második bizonyítás. (S. Johnson [16]): Vegyünk n ? R ( 3 , 2 , m ) általános helyzetű pontot a síkon, és osszuk be az általuk meghatározott n 3 háromszöget 2 osztályba aszerint, hogy a belsejükben páros sok pont van vagy páratlan. Ramsey tétele értelmében kiválasztható m pont, hogy az összes általuk meghatározott háromszög ugyanabba az osztályba esik. Ezek a pontok szükségképpen konvex helyzetben vannak. Tegyük fel ugyanis, hogy van közöttük négy pont, melyek közül az egyik – nevezzük d -nek – a másik három által meghatározott a b c háromszögbe esik. Az a b c háromszög belsejében eggyel több pont van, mint az a b d , b c d , a c d háromszögek belsejében együttvéve. Ha tehát az a , b , c , d pontok által meghatározott összes háromszög belsejében páros (ill. páratlan) sok pont van, akkor az a b c háromszög belsejében páros + páros + páros + 1 = páratlan sok (ill. páratlan + páratlan + páratlan + 1 = páros sok), ami nyilván lehetetlen.

Ramsey a John Maynard Keynes Cambridge-i filozófus és közgazdász köréhez tartozó fiatal kutatók talán legtehetségesebbike volt. Számos különböző tudományban alkotott maradandót: a filozófiában, a közgazdaságtanban, a logikában és a matematika elméleti megalapozásában. A fenti tételt egyetlen tisztán matematikai tárgyú dolgozatában közölte, de ennek hátterében is az a századelő legkiválóbb elméit foglalkoztató kérdés állt, hogy létezik-e egy általános eljárás, mellyel minden matematikai állítás vagy formula igazsága eldönthető. Bár Ramsey tételének segítségével igazolható volt, hogy bizonyos nagyon speciális formájú állítások eldönthetőek, hamarosan kiderült, hogy nincs „univerzálisan jó algoritmus”. A szomorú felismerés alapjaiban rázta meg a tudományt.

Amikor Szekeres 1932-ben újra felfedezte Ramsey tételét, Ramsey már nem élt. 1930. január 19-ikén hunyt el; nem volt még huszonhét éves. Erdős és Szekeres korszakos jelentőségű dolgozata [11] nagyban hozzájárult a Ramsey-tétel népszerűsítéséhez. A Ramsey által találtaknál sokkal jobb, explicit korlátokat adtak az R ( i , j , k ) függvény értékeire, melyek nagy részét máig sem sikerült jelentősen megjavítani. A kérdéskörből az utóbbi harminc évben Ramsey-elmélet néven a kombinatorika egészen új, önálló fejezete nőtt ki [13]. A Klein Eszter feladatának általánosítására adott válaszból szintén új tudományág született: a kombinatorikus geometria [20].