Kategória:	Bizonyítás - Tétel	Évfolyam:	9.
Kulcsszó:	Ramsey-gráfok	Lektorálás:	Nem lektorált

A kétargumentumú Ramsey-számok felső becslése

Bizonyítás

Egy teljes gráfban színezzük be az éleket pirossal és kékkel! Ha egy csúcsból kiindul adott számú kékszínű él, akkor a "végpontok" által meghatározott gráfban biztosan lennie kell egy $(p-1)$ csúcsú teljes részgráfnak (a "kezdő" csúcs lesz a $p$ -edik), vagy egy $q$ csúcsú teljes részgráfnak (a saját színéből). Így ahhoz, hogy még adható legyen ellenpélda (hogy ne legyen biztosan vagy kék színű $p$ csúcsú teljes részgráf, vagy piros színű $q$ csúcsú teljes részgráf)a kék színű csúcsok száma $\le R(p-1), q)-1$ . Hasonlóan a piros fokok száma $\le R(p, q-1)-1$ .

Tehát hogy adható lehessen ellenpélda csúcsonkénti fokszám legfeljebb $R(p-1, q)-1+R(p, q-1)-1$ lehet; azaz a csúcsok száma legfeljebb $R(p-1, q)+R(p, q-1)-1$ . Ahhoz, hogy nem lehessen már ellenpélda, kell még egy él (még egy csúcs), így biztosan létrejön vagy kék színű $p$ csúcsú teljes részgráf, vagy piros színű $q$ csúcsú teljes részgráf. Így a $R(p, q) \le R(p-1, q)+R(p, q-1)$ rekurzív formula állapítható meg.

Vizsgáljuk meg az első néhány Ramsey-szám értékét!

$\begin{tabular}{ccccccccccc} & & & & & R(1, 1)\le 1 & & & & & \\ & & & & R(1, 2) \le 1 & & R(2, 1) \le 1 & & & & \\ & & & R(1, 3) \le 1 & & R(2, 2)\le 2 & & R(3, 1) \le 1 & & & \\ & & R(1, 4) \le 1 & & R(2, 3)\le 3 & & R(3, 2)\le 3 & & R(4, 1) \le 1 & & \\ & R(1, 5) \le 1 & & R(2, 4)\le 4 & & R(3, 3)\le 6 & & R(4, 2)\le 4 & & R(5, 1) \le 1 & \\ \end{tabular}$

Mivel az első néhány elem és a rekurzív formula is megegyezik a Pascal-háromszögével, így $R(p, q) \le {p+q-1 \choose p-1}.$

Ez csak felsőbecslés. A valódi táblázat a következő (az égész táblázat nem ismert):

$\begin{tabular}{ccccccccccccc} & & & & & & 1 & & & & & & \\ & & & & & 1 & & 1 & & & & & \\ & & & & 1 & & 2 & & 1 & & & & \\ & & & 1 & & 3 & & 3 & & 1 & & & \\ & & 1 & & 4 & & 6 & & 4 & & 1 & & \\ & 1 & & 5 & & 9 & & 9 & & 5 & & 1 & \\ 1 & & 6 & & 14 & & 18 & & 14 & & 6 & & 1 \\ & & & & & & \vdots & & & & & & \end{tabular}$

$R(p, q)$

Kezdés

Cikkek

Extrák

Egyéb

Keresés

Legújabb cikkek

Támogató

Szabványok

A kétargumentumú Ramsey-számok felső becslése

Bizonyítás