Twierdzenie Ramseya

Liczbą Ramseya ozn. ${\displaystyle R(q_{1},q_{2},q_{3},\dots ,q_{k})}$, dla ${\displaystyle k,q_{1},q_{2},\dots ,q_{k}\in \mathbb {N} }$ i ${\displaystyle k\geqslant 2}$, nazywamy najmniejszą liczbę ${\displaystyle n}$, taką (jednocześnie) że: dla dowolnego ${\displaystyle k}$-pokolorowania krawędziowego dla ${\displaystyle n}$-wierzchołkowego grafu pełnego; istnieje ${\displaystyle i}$, spełniające nierówność: ${\displaystyle 1\leqslant i\leqslant k}$, oraz takie, że w pokolorowanym grafie jest klika rozmiaru ${\displaystyle q_{i}}$, której wszystkie krawędzie są w kolorze ${\displaystyle i}$.

Aby znaleźć na przykład wartość liczby Ramseya ${\displaystyle R(3,3)}$, kolorujemy krawędzie grafów pełnych dwoma kolorami (np. czerwonym i niebieskim), szukając najmniejszego grafu pełnego, dla którego przy dowolnym kolorowaniu znajdziemy albo trójkąt czerwony, albo trójkąt niebieski. Okazuje się, że prawdziwa jest w istocie równość: ${\displaystyle R(3,3)=6}$.

Dowód powyższej równości:

Dowód równości ${\displaystyle R(3,3)=6}$ przeprowadzimy przez pokazanie poszczególnie, zachodzenia dwóch nierówności:

• ${\displaystyle R(3,3)\leqslant 6}$
• ${\displaystyle R(3,3)\geqslant 6}$

Dowód koniunkcji zachodzenia dwóch powyższych nierówności, w naturalny sposób pozwoli nam wnioskować o tym, że musi być nawet, dokładnie: ${\displaystyle R(3,3)=6}$.

Najpierw, przedstawimy dowód dla pierwszej z tych nierówności. Wybierzmy dowolny punkt grafu pełnego o sześciu wierzchołkach. Wychodzi z niego pięć krawędzi, więc przynajmniej trzy mają wspólny kolor. Załóżmy bez utraty ogólności, że są to trzy czerwone krawędzie (sytuacje te charakteryzują się pełną symetrią). Krawędzie te prowadzą do trzech różnych punktów; te trzy nowe punkty są połączone między sobą trzema krawędziami. Jeżeli choć jedna z nowych krawędzi jest czerwona, powstaje czerwony trójkąt, w przeciwnym przypadku powstaje niebieski trójkąt. Wobec tego wartość liczby Ramseya ${\displaystyle R(3,3)}$, nie może być większa od liczby 6.

Rysunek po lewej dowodzi, że nie może być równe 5 ani mniejsze, więc istotnie jest równe 6. Ma to bardzo wygodną interpretację, mianowicie w zbiorze 6 osób zawsze znajdziemy 3 osoby znające się wzajemnie lub 3 osoby, które się nie znają.

Okazuje się, że wyznaczanie kolejnych wartości liczb Ramseya, jest w istocie bardzo trudnym obliczeniowo zadaniem. Często mamy do dyspozycji bardzo dokładne ich oszacowania, a nie jesteśmy w stanie określić ich wartości, mimo że nie są to wielkie liczby. Poniżej dotychczasowe osiągnięcia w tej dziedzinie:

Liczba	Wartość	Odkrywca, rok
${\displaystyle R(3,3)}$	${\displaystyle 6}$	Greenwood i Gleason, 1955
${\displaystyle R(3,4)}$	${\displaystyle 9}$	Greenwood i Gleason, 1955
${\displaystyle R(3,5)}$	${\displaystyle 14}$	Greenwood i Gleason, 1955
${\displaystyle R(4,4)}$	${\displaystyle 18}$	Greenwood i Gleason, 1955
${\displaystyle R(3,6)}$	${\displaystyle 18}$	Kery, 1964
${\displaystyle R(3,7)}$	${\displaystyle 23}$	Kalbfleich, 1966
${\displaystyle R(3,8)}$	${\displaystyle 28}$	Graver i Yachel, 1968
${\displaystyle R(3,9)}$	${\displaystyle 36}$	McKay i Zhang Ke Min, 1992
${\displaystyle R(4,5)}$	${\displaystyle 25}$	McKay i Radziszowski, 1995
${\displaystyle R(3,3,3)}$	${\displaystyle 17}$	Greenwood i Gleason, 1955
${\displaystyle R(3,3,4)}$	${\displaystyle 30}$	Codish, Frank, Itzhakov i Miller[1], 2016
${\displaystyle 51\leqslant R(3,3,3,3)\leqslant 62}$		(nie wyznaczono dokładnej wartości)
${\displaystyle 43\leqslant R(5,5)\leqslant 49}$		(nie wyznaczono dokładnej wartości)
${\displaystyle 102\leqslant R(6,6)\leqslant 165}$		(nie wyznaczono dokładnej wartości)
${\displaystyle 205\leqslant R(7,7)\leqslant 540}$		(nie wyznaczono dokładnej wartości)
${\displaystyle 282\leqslant R(8,8)\leqslant 1870}$		(nie wyznaczono dokładnej wartości)
${\displaystyle 565\leqslant R(9,9)\leqslant 6588}$		(nie wyznaczono dokładnej wartości)
${\displaystyle 798\leqslant R(10,10)\leqslant 23556}$		(nie wyznaczono dokładnej wartości)

źródło: Optymalizacja dyskretna, modele i metody kolorowania grafów, pod redakcją Marka Kubale, WNT 2002.

Klasyczne liczby Ramseya zdefiniowane są za pomocą kolorowania grafów pełnych, w których poszukujemy monochromatycznych klik (czyli podgrafów pełnych). Pojęcie można jednak uogólnić na poszukiwania dowolnych podgrafów monochromatycznych.