A fenti Ramsey-tételnek több általánosítása is ismert. Mi két lehetőségről teszünk említést.
Az első általanosítás a színek számát növeli. Legyen f:E(G)->{piros, kék, zöld, sárga, ...}=S élszinezése a teljesgráfnak, ahol S egy véges színhalmaz. Igaz-e hogy, ha a pontszám elég nagy, akkor található k elemű homogén halmaz?
A válasz: Igaz. A bizonyítást vázoljuk (a szükséges formalizálást könnyen elvegezheti mindenki): Tegyük fel, hogy S={piros, világos kék, sötét kék}. Ha valaki a kék két árnyalatát nem tudja megkülönböztetni, akkor Ramsey-tétel alapján kész van. Persze a probléma az, hogy a számára kék-homogén halmaz lehet, hogy nem homogén. De biztos kétszínezett, így előre gondolva, Ramsey-tételét úgy alkalmazzuk, hogy a színtévesztő számára kék-``homogén'' halmaz akkora nagy legyen, hogy Ramsey tételének egy második alkalmazása garantálja a világos kék vagy sötét kék k elemű homogén halmaz létét. Ezzel az |S|=3 esetet beláttuk. Az általános állítás |S|-re vonatkozó teljes indukcióval adódik. Az indukció formalizálásához csupán gyakorlatra van szükség, új ötlet nem kell.
Egy második általánosításban a színezett objektumokat változtatjuk meg. Az eredeti változatban egy véges halmaz párjait színeztük. A párok helyett színezhetünk hármasokat, négyeseket, ...
Legyen V egy véges halmaz és legyen (Vk) a V halmaz összes részhalmazát tartalmazó halmaz. V k-asai kétszínezése alatt egy f:(Vk)->{piros, kék} függvényt értünk. Egy H halmaz monokromatikus, ha f megszorítva (Hk)-ra egy konstans függvény. Igaz-e, hogy ha V elég nagy, akkor k-asai tetszőleges két színezésénél lesz k elemű homogén halmaz?
A válasz: igaz. A bizonyítást ismét csak vázlatosán ismertetjük. Előtte azonben egy megjegyzést teszünk.
A fenti állítás akkor is értelmes, ha a k=1 értéket nézzük. Ekkor V elemeit soroljuk osztályokba (színezés) és azzt állítjuk, hogy ha |V| elég nagy akkor lesz olyan osztály ami sok (legalább k) elemet tartalmaz. Ez a skatulya-elv egy változata. A Ramsey-tétel bizonyításában a skatulya-elv, ha bújtatva is, de jól felismerhető. A skatulya-elvről a Ramsey-tételre ugrás egy indukciós bizonyítást sejtet. Valóban a fentiek után a gyakorlott feladatmegoldó már rá is jöhet a bizonyításra.
Mi a fentiekben elővetített k-ra vonatkozó indukciós bizonyításnak csak első lépését végezzük el. Azaz a k=3 esetet igazoljuk. Ennek az állításnak (Ramsey tételéhez hasonlóan) az aszimetrikus változatát igazoljuk. Azaz adott egy t és s szám. Piros-homogén halmaz esetén t mérettel ``elégszünk meg'', kék-homogén halmaz esetén s mérettel ``elégszünk meg''.
V hármasait színezzük ki tetszőlegesen. legyen x V-nek egy tetszőleges eleme. A fenti színezés alapján V-{x} párjait is kiszínezzük: egy {y,z} pár kapja az {x,y,z} hármas színét. Ramsey-tétel alapján elég nagy V halamz esetén erre a színezésre nézve nagy homogén halmazt találunk. Tegyük fel, hogy így egy piros-homogén halmazhoz jutunk. A továbbiakban ezen halmazra szorítkozunk. Ennek a hármasainak színezését vizsgáljuk. A lényeges észrevétel, hogy elég egy t-1 elemszámú piros homogén halmazt (hiszen ez x-szel bővíthető) vagy egy s elemszámú kék-homogén halmazt talánunk. Ezekután az s+t-re vonatkozó indukció ugyanúgy elvégezhető, ahogy a Ramsey-tétel bizonyítása történt.
Források az interneten: