Twierdzenie Ramseya — porządek w chaosie

Co się właśnie stało?

Każdą parę osób połączyliśmy linią i pokolorowaliśmy ją na dwa kolory: niebieski = „znają się", czerwony = „nie znają się". Dla 6 osób — bez względu na to, jak rozłożymy znajomości — zawsze powstaje jednokolorowy trójkąt: albo trzy osoby, które wzajemnie się znają, albo trzy, które wzajemnie się nie znają. Dla 5 osób tego można uniknąć (układ „pięciokąt + gwiazda" wyżej).

Twierdzenie Ramseya (problem przyjęcia)

To jeden z najpiękniejszych wyników kombinatoryki, udowodniony przez brytyjskiego matematyka Franka Ramseya w 1930 r. (w pracy „On a problem of formal logic"). Jego najsłynniejszy przypadek: w każdej grupie co najmniej 6 osób zawsze znajdą się albo 3 osoby, które wzajemnie się znają, albo 3, które wzajemnie się nie znają — bez względu na to, kto kogo zna. Matematycznie: kolorując wszystkie krawędzie grafu pełnego $K_6$ dwoma kolorami, zawsze powstanie jednokolorowy trójkąt ($K_3$).

Ta wartość „6" to liczba Ramseya $R(3,3)$ — najmniejsza liczba osób gwarantująca jednokolorowy trójkąt. Zasadę zapisujemy krótko:

Dlaczego akurat 6, a nie 5?

Dla 5 osób nie jest to gwarantowane: krawędzie grafu $K_5$ można pokolorować tak, by uniknąć jednokolorowego trójkąta. Słynny przykład to „pięciokąt + gwiazda": znajomości ustawiamy wzdłuż pięciokąta (5-cykl), a brak znajomości wzdłuż wpisanej gwiazdy (pentagram) — żaden z tych 5-cykli nie zawiera trójkąta. Dokładnie taki układ widzisz na scenie dla $n=5$. Dopiero szósta osoba psuje tę symetrię: ma 5 połączeń, więc co najmniej 3 z nich są tego samego koloru — i wśród tych trzech osób zawsze domyka się jednokolorowy trójkąt.

Głębsza idea: chaos jest niemożliwy

Cała teoria Ramseya mówi coś zdumiewającego: całkowity chaos nie istnieje. W dostatecznie dużej strukturze zawsze pojawia się jakiś uporządkowany wzorzec, choćbyśmy najbardziej starali się go uniknąć. Ujął to Theodore Motzkin: „pełny nieporządek jest niemożliwy". Teoria Ramseya ma zastosowania w informatyce, teorii liczb i logice.

Ciekawostka

Obliczanie większych liczb Ramseya jest tak trudne, że matematyk Paul Erdős żartował: gdyby kosmici zażądali podania $R(5,5)$ pod groźbą zniszczenia Ziemi, powinniśmy rzucić do obliczeń wszystkie zasoby planety — ale gdyby chcieli $R(6,6)$, lepiej od razu spróbować ich zniszczyć.

Po co Ci to na maturze:

Sama liczba Ramseya to ciekawostka spoza programu, ale przejście „osoby → wierzchołki, znajomości → kolorowanie krawędzi grafu pełnego $K_n$" to wzorcowy przykład modelowania w teorii grafów. Rozumowanie o niezmienniku (tu: nieuniknionym jednokolorowym trójkącie) i argument z zasady szufladkowej Dirichleta przy „szóstej osobie" przydają się w zadaniach kombinatorycznych z rozszerzenia.

Zapamiętaj: w każdej grupie co najmniej 6 osób zawsze są 3 osoby wzajemnie znajome albo 3 wzajemnie obce — $R(3,3)=6$. Porządku nie da się całkowicie wyeliminować: dość dużej strukturze zawsze towarzyszy jakiś wzorzec.