Liczby Ramseya

Klasyczne Liczby Ramseya związane są z kolorowaniem krawędzi grafu pełnego:

Definicja

Liczbą Ramseya \[ R (q_1, q_2, q_3, ..., q_n ) \] nazywamy najmniejszą liczbę \[n \] taką, że dla dowolnego pokolorowania krawędziowego n-wierzchołkowego grafu pełnego istnieje takie \[i \], że istnieje w pokolorowanym grafie klika rozmiaru \[q_i \] w kolorze \[i \].

Przykład

Aby znaleźć np. wartość 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 R(3,3)=6. Ma to bardzo wygodną interpretację, mianowicie, w zbiorze 6 osób zawsze znajdziemy 3 osoby znające się wzajemnie albo 3 osoby które się nie znają.

Wyznaczanie wartości Liczb Ramseya

Okazuje się, że wyznaczenie wartości liczb Ramsaya jest bardzo trudnym obliczeniowo zadaniem. Często mamy do dyspozycji bardzo dokładne ich oszacowania, a nie jesteśmy w stanie dokładnie 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
R(3,3)	6	Greenwood i Gleason, 1955
R(3,4)	9	Greenwood i Gleason, 1955
R(3,5)	14	Greenwood i Gleason, 1955
R(4,4)	18	Greenwood i Gleason, 1955
R(3,6)	18	Kery, 1964
R(3,7)	23	Kalbfleich, 1966
R(3,8)	28	Graver i Yachel, 1968
R(3,9)	36	McKay i Zhang Ke Min, 1992
R(4,5)	25	McKay i Radziszowski, 1995
R(3,3,3)	17
\[30 \leq R(3,3,4) \leq 31 \]		(nie wyznaczono dokładnej wartości)
\[51 \leq R(3,3,3,3) \leq 62 \]		j.w.
\[43 \leq R(5,5) \leq 49 \]		j.w.
\[109 \leq R(6,6) \leq 165 \]		j.w.
\[205 \leq R(7,7) \leq 540 \]		j.w.
\[282 \leq R(8,8) \leq 1870 \]		j.w.
\[565 \leq R(9,9) \leq 6588 \]		j.w.
\[798 \leq R(10,10) \leq 23581 \]		j.w.

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

Nieklasyczne liczby Ramseya

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.