Twierdzenie Ramseya

Q: Czy wśród sześciu osób zawsze są trzy, które się znają?

Nie - zawsze są trzy znające się albo trzy wzajemnie obce. Na przyjęciu samych nieznajomych nie ma żadnej trójki znajomych, ale każda trójka jest wzajemnie obca. Twierdzenie gwarantuje jedną z dwóch konfiguracji, nie konkretną.

Twierdzenie Ramseya (wersja towarzyska)

W każdej grupie sześciu osób istnieją trzy osoby, które znają się nawzajem, albo trzy osoby, z których żadna nie zna żadnej. Pięć osób to za mało: $R(3,3) = 6$ .

Wersja ogólna: dla każdych $m$ i $n$ istnieje liczba $R(m, n)$ taka, że wśród $R(m, n)$ osób zawsze znajdzie się $m$ wzajemnych znajomych albo $n$ wzajemnie obcych.

Co mówi twierdzenie

Weź dowolne przyjęcie na sześć osób - dobranych złośliwie, losowo, jakkolwiek. Twierdzenie gwarantuje, że znajdziesz w nim trójkę wzajemnych znajomych lub trójkę zupełnie obcych. Nie da się tak wymieszać relacji, żeby uniknąć obu konfiguracji naraz.

W języku grafów: pomaluj wszystkie krawędzie grafu pełnego $K_6$ (sześć wierzchołków, każdy połączony z każdym) na dwa kolory - zawsze powstanie jednokolorowy trójkąt. To ta sama sztuczka „z relacji do grafu”, która załatwiła mosty królewieckie i cztery barwy: osoby to wierzchołki, znajomość - kolor krawędzi.

Slogan całej teorii, którą to twierdzenie zapoczątkowało, brzmi: całkowity chaos jest niemożliwy. Dostatecznie duża struktura - jakkolwiek pokolorowana, poszatkowana czy losowa - zawsze zawiera uporządkowany fragment.

Dlaczego pięć osób nie wystarcza

Pięć osób: sąsiedzi w pięciokącie się znają (linia ciągła), pozostałe pary są sobie obce (linia przerywana). Nie powstaje ani trójka znajomych, ani trójka obcych - dlatego R(3,3) > 5.

Kontrprzykład jest zaskakująco symetryczny: znajomości tworzą pięciokąt, a „obcości” - pięcioramienną gwiazdę w środku. Pięciokąt nie zawiera trójkąta, gwiazda też nie (jest tym samym pięciokątem, tylko w innej kolejności wierzchołków). Sześcioro osób to więc najmniejsza liczba, dla której twierdzenie działa.

Dowód, że sześć osób wystarcza

Pokaż dowódUkryj dowód

Krok 1. Patrzymy na jedną osobę. Wybierzmy dowolnego uczestnika przyjęcia - nazwijmy go $A$ . Z pozostałymi pięcioma osobami łączy go pięć relacji, a każda jest jednego z dwóch typów: „znajomy” albo „obcy”.

Krok 2. Zasada szufladkowa. Pięć relacji w dwóch szufladach - w którejś szufladzie są co najmniej trzy (to zasada szufladkowa Dirichleta w wersji uogólnionej: $\lceil 5/2 \rceil = 3$ ). Powiedzmy, że $A$ zna co najmniej trzy osoby: $B$ , $C$ , $D$ (przypadek „nie zna trzech” jest lustrzany - wystarczy zamienić słowa „znajomy” i „obcy”).

Krok 3. Sprawdzamy relacje wewnątrz trójki $B$ , $C$ , $D$ . Są dwie możliwości:

któraś para spośród $B$ , $C$ , $D$ się zna - powiedzmy $B$ i $C$ . Wtedy $A$ , $B$ , $C$ to trzy osoby znające się nawzajem (obie pary $AB$ i $AC$ znają się z kroku 2);
żadna para się nie zna - wtedy $B$ , $C$ , $D$ to trzy osoby wzajemnie obce.

W obu przypadkach szukana trójka istnieje. $\blacksquare$

Cały dowód to jedno zastosowanie zasady szufladkowej i jedno rozróżnienie przypadków - a wynik jest ostry, bo pięciokąt z rysunku pokazuje, że z pięcioma osobami się nie uda.

Dowód twierdzenia ogólnego

Pokaż dowódUkryj dowód

Skąd wiadomo, że liczba $R(m, n)$ w ogóle istnieje dla większych $m$ i $n$ ? Z eleganckiej rekurencji.

Krok 1. Warunki brzegowe. $R(m, 2) = m$ (wśród $m$ osób albo wszyscy się znają, albo jakaś para jest obca - a para to dokładnie „2 wzajemnie obcych”). Symetrycznie $R(2, n) = n$ .

Krok 2. Rekurencja. Pokażemy, że

$R(m, n) \leq R(m-1, n) + R(m, n-1).$

Weźmy grupę o liczności $R(m-1, n) + R(m, n-1)$ i jedną osobę $A$ . Pozostałych jest $R(m-1, n) + R(m, n-1) - 1$ , a każdy jest dla $A$ znajomym albo obcym. Gdyby znajomych było mniej niż $R(m-1, n)$ i obcych mniej niż $R(m, n-1)$ , to razem byłoby ich co najwyżej $R(m-1,n) + R(m,n-1) - 2$ - za mało. Zatem:

albo $A$ zna co najmniej $R(m-1, n)$ osób - wśród nich (z założenia indukcyjnego) jest $m-1$ wzajemnych znajomych (dokładamy $A$ i mamy $m$ ) lub $n$ wzajemnie obcych;
albo $A$ nie zna co najmniej $R(m, n-1)$ osób - wśród nich jest $m$ znajomych lub $n-1$ obcych (dokładamy $A$ ).

Krok 3. Indukcja. Startując z warunków brzegowych i schodząc rekurencją, otrzymujemy skończoną wartość $R(m, n)$ dla każdych $m, n$ . $\blacksquare$

Dla $m = n = 3$ rekurencja daje $R(3,3) \leq R(2,3) + R(3,2) = 3 + 3 = 6$ - dokładnie nasz wynik z przyjęcia.

Dlaczego tych liczb prawie nie znamy

Twierdzenie gwarantuje, że liczby Ramseya istnieją - ale wyznaczyć je to zupełnie inna historia. Oto wszystkie znane wartości „przekątniowe”:

$R(3,3) = 6$ - dowód wyżej;
$R(4,4) = 18$ - udowodnione w 1955 roku;
$R(5,5)$ - nieznane do dziś; wiadomo tylko, że leży między $43$ a $46$ (jeszcze niedawno górną granicą było $48$ );
$R(6,6)$ - wiadomo jedynie, że leży między $102$ a $160$ .

Skąd ta bezradność? Z eksplozji kombinatorycznej: żeby sprawdzić, czy $R(5,5) = 43$ , trzeba by przejrzeć kolorowania grafu pełnego o $43$ wierzchołkach - a jest ich $2^{\binom{43}{2}} = 2^{903}$ , więcej niż kwadratów liczby atomów we wszechświecie. Komputery pomagają w cięciu przypadków, ale nie w brutalnym przeszukaniu.

Paul Erdős ujął to tak: jeśli kosmici zażądają wartości $R(5,5)$ pod groźbą zniszczenia Ziemi, powinniśmy zaprząc wszystkie komputery i wszystkich matematyków. Ale jeśli zażądają $R(6,6)$ - powinniśmy spróbować zniszczyć kosmitów.

O tempie wzrostu wiadomo, że $R(k,k)$ rośnie wykładniczo: między $\left(\sqrt{2}\right)^k$ a około $4^k$ . Dolne ograniczenie Erdős uzyskał w 1947 roku metodą losowego kolorowania - tak narodziła się metoda probabilistyczna, dziś jedno z głównych narzędzi kombinatoryki. Górne ograniczenie $4^k$ opierało się poprawie przez 88 lat - dopiero w 2023 roku zbito je do około $3{,}993^k$ , co uznano za przełom dekady.

Po co to komu

Porządek w każdym chaosie. Teoria Ramseya, która wyrosła z tego twierdzenia, dowodzi podobnych faktów wszędzie: dostatecznie długi ciąg liczb zawiera długi podciąg monotoniczny (Erdős-Szekeres), a przy dowolnym kolorowaniu liczb naturalnych znajdą się jednokolorowe postępy arytmetyczne (van der Waerden).
Przestroga dla analizy danych. Skoro każda dostatecznie duża struktura zawiera regularne wzorce, to znalezienie wzorca w wielkim zbiorze danych samo w sobie niczego nie dowodzi - wzorce muszą tam być z przyczyn czysto kombinatorycznych. Twierdzenie Ramseya to matematyczna podstawa sceptycyzmu wobec „odkryć” wyłowionych z big data bez hipotezy.
Informatyka teoretyczna. Liczby Ramseya wyznaczają granice w teorii złożoności komunikacyjnej i konstrukcjach odpornych sieci; metoda probabilistyczna z dowodu Erdősa stała się standardem projektowania algorytmów losowych.
Test pokory. Pytanie „ile wynosi $R(5,5)$ ?” da się wytłumaczyć dziecku, a nie potrafi na nie odpowiedzieć cała współczesna matematyka z komputerami włącznie - zdrowe przypomnienie, jak blisko granicy poznania leżą proste pytania.

Kto i kiedy

Frank Plumpton Ramsey (1903-1930) udowodnił swoje twierdzenie w pracy z logiki formalnej opublikowanej w 1930 roku - kombinatoryczna perła była tam tylko lematem pomocniczym. Ramsey był umysłem renesansowym: przed śmiercią w wieku 26 lat zdążył położyć fundamenty pod teorię optymalnego opodatkowania i oszczędzania (ekonomiści do dziś używają „modelu Ramseya”), przetłumaczyć Wittgensteina na angielski i zrewolucjonizować probabilistykę subiektywną.

Twierdzenie rozsławili w 1935 roku Paul Erdős i George Szekeres, odkrywając je na nowo przy „problemie o szczęśliwym zakończeniu”: każde dostatecznie duże ułożenie punktów zawiera wielokąt wypukły. Nazwa wzięła się stąd, że nad problemem pracowała z nimi Esther Klein - a praca skończyła się jej ślubem z Szekeresem. Slogan „całkowity chaos jest niemożliwy” ukuł Theodore Motzkin.

Najczęstsze pytania

Czy wśród sześciu osób zawsze są trzy, które się znają? Nie - zawsze są trzy znające się albo trzy wzajemnie obce. Na przyjęciu samych nieznajomych nie ma żadnej trójki znajomych, ale każda trójka jest wzajemnie obca. Twierdzenie gwarantuje jedną z dwóch konfiguracji, nie konkretną.

Dlaczego pięć osób to za mało? Bo istnieje kontrprzykład: znajomości ułożone w pięciokąt (każdy zna dokładnie dwóch sąsiadów). Wtedy ani żadna trójka nie zna się nawzajem, ani żadna nie jest wzajemnie obca - widać to na rysunku wyżej.

Dlaczego komputery nie wyznaczyły R(5,5)? Bo kandydatów jest za dużo: kolorowań krawędzi grafu o 43 wierzchołkach jest $2^{903}$ . Żadne przyspieszenie sprzętu nie pokona takiego wykładnika - potrzebny byłby pomysł matematyczny, nie większa moc obliczeniowa.

Co to jest teoria Ramseya? Cała gałąź kombinatoryki wyrosła z tego twierdzenia, badająca zjawisko „porządku nie do uniknięcia”: jak duża musi być struktura, by przy dowolnym podziale na części zawierała regularny fragment. Należą do niej twierdzenia van der Waerdena, Schura, Halesa-Jewetta.

Jaki jest związek z zasadą szufladkową? Bezpośredni - zasada szufladkowa jest silnikiem obu dowodów na tej stronie i bywa nazywana „twierdzeniem Ramseya dla jednego wymiaru”: tam porządek wymusza się wśród elementów, tu wśród relacji między nimi.

Podsumowanie

$R(3,3) = 6$ : wśród sześciu osób zawsze jest trójka wzajemnych znajomych albo trójka wzajemnie obcych; pięciokąt znajomości pokazuje, że pięć osób nie wystarcza.
Dowód górnego ograniczenia to zasada szufladkowa (trzy relacje tego samego typu u jednej osoby) plus rozróżnienie dwóch przypadków.
Wersja ogólna istnieje dla każdych $m, n$ dzięki rekurencji $R(m,n) \leq R(m-1,n) + R(m,n-1)$ .
Wartości prawie nie znamy: $R(4,4) = 18$ , ale $R(5,5)$ to wciąż tylko przedział $43$ - $46$ - eksplozja kombinatoryczna wygrywa z komputerami.
Morał teorii Ramseya: całkowity chaos jest niemożliwy - a wzorzec znaleziony w wielkich danych może być kombinatoryczną koniecznością, nie odkryciem.