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

Liczby_Ramseya -
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:
LiczbaWartośćOdkrywca, rok
R(3,3)6Greenwood i Gleason, 1955
R(3,4)9Greenwood i Gleason, 1955
R(3,5)14Greenwood i Gleason, 1955
R(4,4)18Greenwood i Gleason, 1955
R(3,6)18Kery, 1964
R(3,7)23Kalbfleich, 1966
R(3,8)28Graver i Yachel, 1968
R(3,9)36McKay i Zhang Ke Min, 1992
R(4,5)25McKay 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.
Publikacja wraz ze zdjęciami jest udostępniona w Encyklopedii "Zgapedia" części portalu zgapa.pl. Treść objęta jest licencją GNU FDL Wolnej Dokumentacji w wersji 1.3 lub dowolnej pózniejszej opublikowanej przez Free Software Foundation i została ona opracowana na podstawie Wikipedii, tutaj możesz znaleźć artykuł źródłowy oraz autorów. Warunki użytkowania Encyklopedii znajdziesz na tej stronie.