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].