Gráfszínezés és Ramsey-számok

Definíció — csúcsszínezés

Legyen \(G\) gráf, \(C\) színek egy halmaza. Ekkor \(G\) egy csúcsszínezésén egy \(f: V(G) \to C\) függvényt értünk. Egy \(v \in V(G)\) csúcs színe \(f(v)\). Egy csúcsszínezést jó csúcsszínezésnek nevezünk, ha szomszédos csúcsok színe különböző.

Tétel

Egy \(G\) gráfnak van jó csúcsszínezése \(\iff G\) hurokélmentes.

Bizonyítás

⟹: ha lenne hurokél, annak végpontja önmagával lenne szomszédos, így nem színezhető jól.

⟸: hurokélmentes esetben legyen minden csúcs különböző színű — ez jó csúcsszínezés (legfeljebb \(|V(G)|\) színnel).

Definíció — kromatikus szám

Egy \(G\) egyszerű gráf kromatikus száma a legkisebb szám, ahány színnel \(G\)-nek van jó csúcsszínezése. Jelölés: \(\chi(G)\) (vagy \(\chi_v(G)\)). \(G\)-nek van jó csúcsszínezése \(k\) db színnel \(\iff \chi(G) \le k\).

Tétel

Legyen \(G\) egyszerű gráf.

1. \(\chi(G) = 1 \iff G\) üres gráf.
2. \(\chi(G) = 2 \iff G\) nem üres páros gráf.

Bizonyítás

(1) Nyilvánvaló (ha lenne legalább egy él, annak két végpontjára már két különböző szín kellene).

(2)

⟹: \(\chi(G) = 2 \neq 1 \implies G\) nem üres (az (1) miatt). \(\chi(G)=2 \implies G\) csúcsai 2 színnel jól kiszínezhetők, de mindkét színt használjuk is. Ekkor \(A = \{\text{egyik színű csúcsok}\}\), \(B = \{\text{másik színű csúcsok}\}\) megfelelő csúcsosztályok, azaz \(G\) páros.

⟸: tfh. \(G\) páros gráf \(A, B\) csúcsosztályokkal. Legyenek az \(A\)-beli csúcsok zöldek, a \(B\)-beliek pirosak: ez jó csúcsszínezés 2 színnel \(\implies \chi(G) \le 2\). Mivel \(G\) nem üres \(\implies \chi(G) \neq 1 \implies \chi(G) = 2\).

Tétel

Ha \(G\) egyszerű gráf, akkor \(\chi(G) \ge \omega(G)\), ahol \(\omega(G)\) a klikkszám.

Bizonyítás

Egy \(\omega(G)\) csúcsú klikk bármely két csúcsa szomszédos, így azokat mind különböző színűre kell színezni \(\implies\) legalább \(\omega(G)\) db szín szükséges.

Tétel

Ha \(G\) egyszerű gráf, akkor \(\chi(G) \le \Delta(G) + 1\).

Bizonyítás — \(|V(G)|\) szerinti teljes indukcióval

• \(|V(G)| = 1\): \(\chi(G) = 1, \Delta(G) = 0 \implies 1 \le 0 + 1\).
• Tfh. \(|V(G)| \ge 2\) és kevesebb csúcsú gráfokra igaz az állítás. Legyen \(v \in V(G)\) tetszőleges csúcs. Alkalmazzuk az indukciós feltételt a \((G - v)\) részgráfra: \(\chi(G-v) \le \Delta(G-v) + 1 \le \Delta(G) + 1\), azaz \(G-v\) csúcsai jól kiszínezhetők \(\Delta(G)+1\) db színnel. A \(v\) csúcsnak legfeljebb \(d(v) \le \Delta(G)\) szomszédja van \(G\)-ben. Mivel összesen \(\Delta(G)+1\) szín áll rendelkezésre, a szomszédai által használt színek száma legfeljebb \(\Delta(G)\). Így marad legalább egy olyan szín, amit \(v\) egyik szomszédja sem használ \(\implies\) ez a szín hozzárendelhető \(v\)-hez. \(\implies G\)-nek van jó csúcsszínezése \(\Delta(G)+1\) db színnel.

Tétel — Brooks-tétel

Ha \(G\) egyszerű, összefüggő gráf, amely nem teljes gráf és nem páratlan csúcsszámú körgráf, akkor:

\[ \chi(G) \le \Delta(G) \]

Tétel — Ötszín-tétel

Ha \(G\) egyszerű, síkbarajzolható gráf, akkor \(\chi(G) \le 5\).

Bizonyítás

\(|V(G)|\) szerinti teljes indukció.

• Alapeset: \(|V(G)| \le 5\) esetén a tétel triviális (\(\chi(G) \le |V(G)| \le 5\)).
• Indukciós lépés: tfh. \(|V(G)| \ge 6\) és kevesebb csúcsú síkgráfokra igaz az állítás. Mivel \(G\) síkbarajzolható, tudjuk, hogy \(\delta(G) \le 5\) (előző jegyzet). Legyen \(v \in V(G)\) olyan csúcs, amelyre \(d(v) = \delta(G) \le 5\). Tekintsük a \(G - v\) részgráfot. Az indukciós feltétel szerint \(G - v\) színezhető 5 színnel (legyenek a színek: \(1, 2, 3, 4, 5\)).

1. eset: ha \(d(v) \le 4\), vagy \(d(v) = 5\) de \(v\) szomszédai a \(G-v\) jó színezésében nem használják mind az 5 színt, akkor a szomszédok által fel nem használt színre színezve \(v\)-t, \(G\) jó színezését kapjuk 5 színnel.

2. eset: ha \(d(v) = 5\) és \(v\) szomszédai (\(v_1, v_2, v_3, v_4, v_5\) óramutató járása szerint ágyazva a síkba) mind az 5 különböző színt kapták (rendre az \(1, 2, 3, 4, 5\) színeket). Tekintsük a \(G_{1,3}\) feszített részgráfot, amelyet az \(1\)-es és \(3\)-as színű csúcsok alkotnak \(G-v\)-ben (Kempe-lánc).

• Ha \(v_1\) és \(v_3\) nincsenek egy komponensben \(G_{1,3}\)-ban: a \(v_1\)-et tartalmazó \(G_{1,3}\)-beli komponensben felcseréljük az \(1\)-es és \(3\)-as színeket. Így \(v_1\) a \(3\)-as színt kapja, miközben \(v_3\) színe \(3\)-as marad. Ezzel az \(1\)-es szín szabaddá válik \(v\) számára!
• Ha \(v_1\) és \(v_3\) egy komponensben vannak \(G_{1,3}\)-ban: ekkor létezik egy \(v_1\)-ből \(v_3\)-ba vezető útvonal, ami csak \(1\)-es és \(3\)-as színű csúcsokból áll. Ez az út a \(v\) csúccsal együtt egy zárt görbét (kört) alkot a síkban, ami elválasztja \(v_2\)-t és \(v_4\)-et! Emiatt a \(2\)-es és \(4\)-es színű \(G_{2,4}\) részgráfban \(v_2\) és \(v_4\) nem lehetnek egy komponensben (nem keresztezhetik az \(1\)-\(3\) utat a síkbeliség miatt). Így a \(v_2\)-t tartalmazó \(G_{2,4}\)-beli komponensben felcserélve a \(2\)-es és \(4\)-es színeket, \(v_2\) a \(4\)-es színt kapja, és a \(2\)-es szín szabaddá válik \(v\) számára.

Minden esetben sikerült \(v\)-t kiszínezni \(\implies \chi(G) \le 5\).

Definíció — kromatikus polinom

Legyen \(G\) egyszerű gráf és \(x \in \mathbb{N}\). Ekkor \(P_G(x)\) jelöli a \(G\) jó csúcsszínezéseinek számát pontosan \(x\) színnel (a \(G\) csúcsain értelmezett \(f: V(G) \to \{1, \dots, x\}\) jó csúcsszínezések száma). Belátható, hogy \(P_G(x)\) egy \(x\)-ben polinom (innen a neve): fokszáma \(|V(G)|\), főegyütthatója \(1\), és az együtthatók előjele felváltva vált.

Tétel

Ha \(G\) komponensei \(G_1, \dots, G_m\), akkor:

\[ P_G(x) = P_{G_1}(x) \cdot P_{G_2}(x) \cdots P_{G_m}(x) \]

Bizonyítás

Az egyes komponensek színezései egymástól függetlenül választhatók.

Tétel

Ha \(G\) nemüres egyszerű gráf, melynek \(m\) komponense van, akkor \(P_G(x)\)-ben az \(x^0, x^1, \dots, x^{m-1}\) együtthatói \(0\), az \(x^m\) együtthatója pedig \(\neq 0\) — azaz a legkisebb kitevőjű nemnulla együttható foka pontosan a komponensek számával egyezik meg.

Bizonyítás

Mivel \(P_{G_1}(x), \dots, P_{G_m}(x)\)-ben a konstans tag \(0\) (egy nemüres, összefüggő gráf nem színezhető 0 színnel) \(\implies\) szorzatukban \(x^0, x^1, \dots, x^{m-1}\) együtthatója \(= 0\). Másrészt \(G_1, \dots, G_m\) összefüggőek \(\implies P_{G_1}(x), \dots, P_{G_m}(x)\)-ben \(x^1\) együtthatója \(\neq 0\) \(\implies\) szorzatukban \(x^m\) együtthatója \(\neq 0\).

Emlékeztető

Ha \(G\) nemüres egyszerű gráf, akkor \(P_G(0) = P_G(1) = 0\): \(x=0\) színnel nyilván nincs csúcsszínezés, \(x=1\) színnel pedig bármely él két végpontja ugyanazt a színt kapná, ami nem jó színezés. Ebből az is következik, hogy a polinom együtthatóinak összege \(0\) (hiszen az összeg épp \(P_G(1)\)).

Definíció — élszínezés

Legyen \(G\) nemüres gráf és \(C\) a színek egy halmaza. Ekkor egy \(g: E(G) \to C\) függvényt élszínezésnek nevezünk. Az \(e \in E(G)\) él színe \(g(e)\). Egy élszínezést akkor nevezünk jó élszínezésnek, ha közös végponttal rendelkező élek színe különböző.

Tétel

Legyen \(G\) nemüres gráf. Ekkor \(G\)-nek van jó élszínezése \(\iff G\) hurokélmentes.

Bizonyítás

⟹: a hurokélnek van önmagával közös végpontja, így nem színezhető jól.

⟸: hurokélmentes esetben minden él legyen különböző színű.

Definíció — kromatikus index

Legyen \(G\) nemüres, hurokélmentes gráf. Ekkor \(G\) kromatikus indexe az a legkisebb szám, ahány színnel \(G\)-nek van jó élszínezése. Jelölés: \(\chi'(G)\).

Tétel

Ha \(G\) nemüres hurokélmentes gráf, akkor \(\chi'(G) \ge \Delta(G)\).

Bizonyítás

A \(\Delta(G)\) fokú csúcsból induló \(\Delta(G)\) db él mind különböző színű kell legyen, így legalább \(\Delta(G)\) db szín szükséges.

Tétel — Vizing, egyszerű változat

Ha \(G\) nemüres egyszerű gráf, akkor \(\chi'(G) \le \Delta(G) + 1\).

Tétel — Vizing, általános változat

Ha \(G\) nemüres hurokélmentes gráf, akkor \(\chi'(G) \le \Delta(G) + m(G)\), ahol \(m(G)\) a párhuzamos élek maximális száma.

Tétel — Shannon

Ha \(G\) nemüres hurokélmentes gráf, akkor \(\chi'(G) \le \frac{3}{2} \Delta(G)\).

Emlékeztető

Ezek a tételek nem javíthatók, azaz állhat fenn bennük egyenlőség. Példa: legyen \(G\) a 3 csúcsú multigráf, ahol minden csúcspár között \(\ell\) db él fut. Ekkor \(\chi'(G) = 3\ell\), mert minden élnek különböző színűnek kell lennie. Mivel \(\Delta(G) = 2\ell\) és \(m(G) = \ell\), a Shannon-korlátra: \(\frac{3}{2} \cdot 2\ell = 3\ell\), tehát éles a becslés.

Tétel

Ha \(G\) nemüres páros gráf, akkor \(\chi'(G) = \Delta(G)\).

Tétel — Vizing, Sanders, Zhao

Ha \(G\) nemüres, egyszerű, síkbarajzolható gráf és \(\Delta(G) \ge 7\), akkor \(\chi'(G) = \Delta(G)\).

Emlékeztető

• Vizing \(\Delta(G) \ge 8\)-cal látta be, és azt sejtette, hogy igaz \(\Delta(G) = 6\), illetve \(\Delta(G) = 7\) mellett is.
• Sanders és Zhao \(\Delta(G) = 7\)-re bizonyították.
• \(\Delta(G) = 6\)-ra még ma is nyitott.
• \(\Delta(G) \le 5\) esetén már nem igaz az állítás: pl. \(\Delta(G)=2\)-re \(G = K_3\) esetén \(\chi'(G) = 3 \neq \Delta(G) = 2\); \(\Delta(G) = 3, 4, 5\) esetén a szabályos testek (poliéderek) gráfjaiból kiindulva konstruálhatók ellenpéldák.

Híres feladat

Mutassuk meg, hogy 6 ember közt mindig van 3 olyan, akik ismerik egymást, vagy 3 olyan, akik nem ismerik egymást! Gráfelméleti nyelven: 6 csúcsú teljes gráf éleit akárhogyan kiszínezzük zöld és piros színekkel, biztosan keletkezik 3 csúcsú klikk zöld élekkel vagy 3 csúcsú klikk piros élekkel.

Definíció — kétszínes Ramsey-szám

Legyen \(k, \ell \in \mathbb{N}\). Jelölje \(R(k,\ell)\) a legkisebb olyan számot, hogy a következő teljesül: ha egy ennyi csúcsú teljes gráf éleit akárhogyan színezzük zölddel és pirossal, biztosan keletkezik \(k\) csúcsú klikk zöld élekkel vagy \(\ell\) csúcsú klikk piros élekkel. Ezt az \(R(k,\ell)\)-et kétszínes Ramsey-számnak nevezzük.

Tétel — Ramsey

\(\forall k, \ell \in \mathbb{N} : \exists R(k,\ell)\)

Bizonyítás — kettős indukció

\(k = 1\): \(R(1,\ell) = 1\) világos. \(\ell = 1\): \(R(k,1) = 1\) hasonlóan.

\(k, \ell \ge 2\) és \(\exists R(k-1,\ell)\) és \(\exists R(k,\ell-1)\) mind létezik: tekintsünk egy \(R(k-1,\ell) + R(k,\ell-1)\) csúcsú teljes gráfot. (Erről látjuk be, hogy "jó \(m\)".) Színezzük éleit zölddel és pirossal. Legyen \(v\) egy csúcs. Erre \(R(k-1,\ell) + R(k,\ell-1) - 1\) db él illeszkedik. Ezek közt van \(R(k-1,\ell)\) db zöld él vagy \(R(k,\ell-1)\) db piros él, hiszen ha a zöldek száma legfeljebb \(R(k-1,\ell)-1\), a pirosaké legfeljebb \(R(k,\ell-1)-1\) lenne, akkor csak legfeljebb \(R(k-1,\ell) + R(k,\ell-1) - 2\) db él lenne.

1. eset: ha \(v\)-re illeszkedik \(R(k-1,\ell)\) db zöld él. Ekkor ezen élek másik végpontjai által feszített \(R(k-1,\ell)\) csúcsú teljes gráfban van \(k-1\) csúcsú klikk zöld élekkel (ami \(v\)-vel együtt \(k\) csúcsú zöld klikket ad), vagy \(\ell\) csúcsú klikk piros élekkel.

2. eset: ha \(v\)-re illeszkedik \(R(k,\ell-1)\) db piros él. Ez az eset teljesen hasonlóan működik.

Emlékeztető

A bizonyításból adódik a rekurzív egyenlőtlenség: ha \(k, \ell \ge 2\), akkor:

\[ R(k,\ell) \le R(k-1,\ell) + R(k,\ell-1) \]

Tétel

\(\forall k, \ell \in \mathbb{N} : R(k,\ell) = R(\ell,k)\) (szimmetria tulajdonság).

Bizonyítás

A színek szerepe felcserélhető.

Tétel

1. \(\forall \ell \in \mathbb{N} : R(1,\ell) = 1\) és \(\forall k \in \mathbb{N} : R(k,1) = 1\)
2. \(\forall \ell \in \mathbb{N} : R(2,\ell) = \ell\) és \(\forall k \in \mathbb{N} : R(k,2) = k\)
3. \(R(3,3) = 6\)

Bizonyítás

(1) Lásd fent.

(2) Vegyünk egy \(\ell\) csúcsú teljes gráfot, színezzük éleit zölddel és pirossal: ha van zöld él, ott keletkezett 2 csúcsú klikk zöld élekkel; ha nincs zöld él, az egész gráf egy \(\ell\) csúcsú klikk piros élekkel. Másrészt \(\ell - 1\) csúcsú teljes gráf éleit lehet úgy színezni, hogy ne keletkezzen sem 2 csúcsú klikk zöld élekkel, sem \(\ell\) csúcsú klikk piros élekkel (legyen minden él piros). \(R(k,2) = R(2,k) = k\) a szimmetria miatt.

(3) I. Vegyünk egy 6 csúcsú teljes gráfot, színezzük éleit zölddel és pirossal. Legyen \(v\) egy csúcs. Erre 5 db él illeszkedik. A skatulyaelv szerint (2 szín van) ezek közt van 3 azonos színű, pl. zöld. Ha ezek másik végpontjai közt van zöld él, akkor \(v\)-vel együtt 3 csúcsú klikk keletkezik zöld élekkel. Ha pedig ezek közt minden él piros, akkor ott van egy 3 csúcsú klikk piros élekkel.

II. 5 csúcsú teljes gráf élei kiszínezhetők zölddel és pirossal úgy, hogy ne keletkezzen 3 csúcsú klikk sem zöld, sem piros élekkel: az 5 csúcsot egy körvonalra helyezve, a külső ötszög élei pirosak, a belső ötágú csillag (átlók) élei zöldek.

Emlékeztető

A tételben szereplőkön kívül csak kevés kétszínes Ramsey-szám pontos értéke ismert.

Tétel — Erdős, Szekeres

Ha \(k, \ell \in \mathbb{N}\), akkor:

\[ R(k,\ell) \le \binom{k+\ell-2}{k-1} \]

Bizonyítás — kettős indukció

\(k=1\): b.o. \(R(1,\ell) = 1\), j.o. \(\binom{\ell-1}{0} = 1\). \(\ell=1\): b.o. \(R(k,1) = 1\), j.o. \(\binom{k-1}{k-1} = 1\).

Tegyük fel \(k,\ell \ge 2\), és \(R(k-1,\ell)\)-re és \(R(k,\ell-1)\)-re igaz az állítás. Ekkor:

\[ R(k,\ell) \le R(k-1,\ell) + R(k,\ell-1) \le \binom{k+\ell-3}{k-2} + \binom{k+\ell-3}{k-1} = \binom{k+\ell-2}{k-1} \]

Tétel — Erdős

Ha \(k \in \mathbb{N}, k \ge 2\), akkor \(R(k,k) \ge 2^{k/2}\).

Bizonyítás

\(k=2\): b.o. \(R(2,2) = 2\), j.o. \(2^{2/2} = 2\). \(k=3\): b.o. \(R(3,3) = 6\), j.o. \(2^{3/2} = \sqrt{8} \approx 2{,}82\).

\(k \ge 4\): legyen \(k \le n < 2^{k/2}\). Azt fogjuk belátni, hogy egy \(n\) csúcsú teljes gráf éleinek van olyan színezése zölddel és pirossal, hogy nem keletkezik \(k\) csúcsú klikk sem zöld, sem piros élekkel (a \(k \le n\) kikötés azért tehető fel, mert \(k > n\) esetén biztosan nincs \(k\) csúcsú klikk).

• Az összes színezések száma \(= 2^{\binom{n}{2}}\), hiszen \(\binom{n}{2}\) él van, mindegyik kétféle színt kaphat.
• Ha rögzítünk \(k\) db csúcsot, az olyan színezések száma, hogy a \(k\) csúcs által feszített klikk minden éle zöld, \(= 2^{\binom{n}{2} - \binom{k}{2}}\).
• Olyan színezések száma, ahol van \(k\) csúcsú klikk zöld élekkel: \(\le \binom{n}{k} \cdot 2^{\binom{n}{2} - \binom{k}{2}}\) (ennyiféleképpen választhatjuk ki a \(k\) db csúcsot; egy színezés több \(k\) csúcsú klikkhez is lehet számolva). Ugyanez zöld helyett piros színnel is fennáll \(\implies\) olyan színezések száma, ahol van \(k\) csúcsú klikk zöld vagy piros élekkel: \(\le 2 \cdot \binom{n}{k} \cdot 2^{\binom{n}{2} - \binom{k}{2}}\).

Azt kell belátnunk, hogy ez a szám szigorúan kisebb, mint az összes színezések száma:

\[ 2 \cdot \binom{n}{k} \cdot 2^{\binom{n}{2} - \binom{k}{2}} < 2^{\binom{n}{2}} \]

Feltesszük, hogy \(n < 2^{k/2}\). Felhasználva a \(\binom{n}{k} < \frac{n^k}{k!}\) becslést (mivel \(k \ge 4 \implies k! > 2^{k-1}\)):

\[ \binom{n}{k} < \frac{(2^{k/2})^k}{2^{k-1}} = \frac{2^{k^2/2}}{2^{k-1}} = 2^{\frac{k^2}{2} - k + 1} \]

Behelyettesítve:

\[ 2 \cdot \binom{n}{k} \cdot 2^{\binom{n}{2} - \binom{k}{2}} < 2 \cdot 2^{\frac{k^2}{2} - k + 1} \cdot 2^{\frac{n(n-1)}{2} - \frac{k(k-1)}{2}} = 2^{\frac{n(n-1)}{2}} \cdot 2^{2 - \frac{k}{2}} \]

Mivel \(k \ge 4 \implies 2 - \frac{k}{2} \le 0 \implies 2^{2 - \frac{k}{2}} \le 1\). Így a kedvezőtlen színezések száma szigorúan kisebb, mint az összes színezés száma \(\implies\) van olyan színezés, amikor nem keletkezik \(k\) csúcsú klikk sem zöld, sem piros élekkel.

Definíció — \(r\)-színes Ramsey-szám

Legyen \(r \ge 2\) egész és \(k_1, \dots, k_r \in \mathbb{N}\). Jelölje \(R(k_1, \dots, k_r)\) a legkisebb olyan számot, hogy: egy ennyi csúcsú teljes gráf éleit akárhogyan színezzük \(r\) db színnel, valamelyik \(i\)-re (\(1 \le i \le r\)) keletkezik \(k_i\) csúcsú klikk \(i\)-edik színű élekkel.

Tétel — Ramsey

Ha \(r \ge 2\) és \(k_1, \dots, k_r \in \mathbb{N}\), akkor \(\exists R(k_1, \dots, k_r)\).

Bizonyítás — 1. módszer, teljes indukcióval \(r\) szerint

Ha \(k_i = 1\) valamelyik \(1 \le i \le r\)-re \(\implies R(k_1, \dots, k_{i-1}, 1, k_{i+1}, \dots, k_r) = 1\) nyilvánvaló. Ha \(k_1, \dots, k_r \ge 2\) és \(\exists R(k_1, \dots, k_{i-1}, k_i - 1, k_{i+1}, \dots, k_r)\) minden \(1 \le i \le r\)-re: vegyünk egy \(\sum_{i=1}^r R(k_1, \dots, k_{i-1}, k_i - 1, k_{i+1}, \dots, k_r)\) csúcsú teljes gráfot, színezzük éleit \(r\) db színnel. Legyen \(v\) egy csúcs. Erre \(\sum_{i=1}^r R(\dots) - 1\) db él illeszkedik. Ezek közt valamelyik \(i\)-re igaz, hogy van \(R(k_1, \dots, k_i - 1, \dots, k_r)\) db \(i\)-edik színű él. Innen a kétszíneshez hasonlóan adódik az állítás.

Emlékeztető

\(k_1, \dots, k_r \ge 2\) esetén:

\[ R(k_1, \dots, k_r) \le \sum_{i=1}^r R(k_1, \dots, k_{i-1}, k_i - 1, k_{i+1}, \dots, k_r) \]

Bizonyítás — 2. módszer, \(r\) szerinti teljes indukció

\(r=2\): kétszínes Ramsey-számok létezése (előzőleg bizonyítva). Így \(r \ge 3\), és \((r-1)\)-színes R-számok léteznek. Vegyünk egy \(R(k_1, \dots, k_{r-2}, R(k_{r-1}, k_r))\) csúcsú teljes gráfot (az első rész egy \((r-1)\)-színes R-szám, a belső pedig egy 2-színes R-szám). Színezzük ennek éleit \(r\) db színnel úgy, hogy az \((r-1)\)-edik szín világoskék, az \(r\)-edik szín sötétkék. Ha az utolsó két színt nem tudjuk megkülönböztetni, azok egyszerűen "kékek" — így \(r-1\) színt használunk.

\(\implies\) valamelyik \(1 \le i \le r-2\)-re keletkezik \(k_i\) csúcsú klikk \(i\)-edik színű élekkel, vagy \(R(k_{r-1}, k_r)\) csúcsú klikk kék élekkel. Utóbbi esetben, ha újra meg tudjuk különböztetni a kétféle kéket: keletkezik \(k_{r-1}\) csúcsú klikk világoskék élekkel, vagy \(k_r\) csúcsú klikk sötétkék élekkel.

Tétel

Legyen \(r \ge 2\), \(k_1, \dots, k_r \in \mathbb{N}\) és \((k_{i_1}, \dots, k_{i_r})\) ezek egy permutációja. Ekkor \(R(k_{i_1}, \dots, k_{i_r}) = R(k_1, \dots, k_r)\) (a színek szerepének felcserélése).

Tétel

1. Ha \(r \ge 2\), akkor \(R(k_1, \dots, k_{r-1}, 1) = 1\)
2. Ha \(r \ge 2\), akkor \(R(k_1, \dots, k_r, 2) = R(k_1, \dots, k_r)\) (\((r+1)\) színről \(r\) színre)
3. \(R(3,3,3) = 17\)

Bizonyítás

(1) Lásd korábban.

(2) Vegyünk egy \(R(k_1, \dots, k_r)\) csúcsú teljes gráfot és színezzük éleit \(r+1\) db színnel: ha van \((r+1)\)-edik színű él, az megad egy 2 csúcsú klikket ilyen színű élekkel; ha nincs, tulajdonképpen \(r\) db színnel színeztünk, ami garantálja valamelyik \(k_i\) csúcsú klikk létezését. Egy \((R(k_1, \dots, k_r)-1)\) csúcsú teljes gráf viszont kiszínezhető \(r\) db színnel úgy, hogy egyik \(i\)-re se keletkezzen \(k_i\) csúcsú klikk — ekkor nyilván 2 csúcsú klikk sincs az \((r+1)\)-edik színű élekkel.

(3) I. Vegyünk egy 17 csúcsú teljes gráfot, színezzük éleit 3 színnel: zöld, piros, kék. Legyen \(v\) egy csúcs, ebből 16 él indul. A skatulyaelv szerint (3 szín van) ezek között lesz 6 db azonos színű él, pl. kék. Ha ezek másik végpontjai közt van kék él, akkor \(v\)-vel együtt ott keletkezik 3 csúcsú klikk kék élekkel. Ha nincs köztük kék él, akkor azon 6 csúcs közt minden él zöld vagy piros, és mivel \(R(3,3)=6\), ott keletkezik 3 csúcsú klikk zöld vagy piros élekkel.

II. A 16 csúcsú teljes gráf éleit ki lehet színezni 3 színnel úgy, hogy ne keletkezzen 3 csúcsú klikk egyik színű élekkel sem (lásd: Clebsch-gráf / Greenwood–Gleason konstrukció).

Emlékeztető

Ha \(r \ge 3\), \(k_1, \dots, k_r \ge 3\), akkor ezeken kívül csak egyetlen további érték ismert pontosan.

Tétel — Erdős, Szekeres

Ha \(r \ge 2, k_1, \dots, k_r \in \mathbb{N}\), akkor:

\[ R(k_1, \dots, k_r) \le \frac{(k_1 + \dots + k_r - r)!}{(k_1 - 1)! \dots (k_r - 1)!} \]

Bizonyítás — \(r\)-szeres indukcióval

\(k_i = 1\) esetén b.o. \(= 1\), j.o. \(= P_{k_1+\dots+k_r-r}^{k_1-1,\dots,k_r-1} \ge 1\). Így \(k_1, \dots, k_r \ge 2\) és az állítás igaz \(R(k_1, \dots, k_{i-1}, k_i - 1, k_{i+1}, \dots, k_r)\)-re (\(1 \le i \le r\)). Ekkor a Ramsey-tétel és az indukciós feltétel alapján:

\[ R(k_1, \dots, k_r) \le \sum_{i=1}^r R(k_1, \dots, k_i - 1, \dots, k_r) \le \sum_{i=1}^r \frac{(k_1 + \dots + k_r - 1 - r)!}{(k_1 - 1)! \dots (k_i - 2)! \dots (k_r - 1)!} \]

A számláló és nevező kiemelésével:

\[ = (k_1 + \dots + k_r - r - 1)! \cdot \sum_{i=1}^r \frac{k_i - 1}{(k_1 - 1)! \dots (k_r - 1)!} = \frac{(k_1 + \dots + k_r - r - 1)!}{(k_1 - 1)! \dots (k_r - 1)!} \cdot \underbrace{\sum_{i=1}^r (k_i - 1)}_{k_1 + \dots + k_r - r} = \frac{(k_1 + \dots + k_r - r)!}{(k_1 - 1)! \dots (k_r - 1)!} \]