Bardzo duży mały skok naprzód w teorii grafów

15 marca intrygujące ogłoszenia o seminariach wywołały poruszenie w dziedzinie kombinatoryki, matematycznej nauki liczenia. Trzech współpracowników planowało wygłosić skoordynowane przemówienia następnego dnia. Juliana Sahasrabudhe zwróci się do matematyków w Cambridge w Anglii, podczas gdy Simona Griffithsa podzieliłby się wiadomościami w Rio de Janeiro i Marcelo Camposa w Sao Paulo. Wszystkie trzy rozmowy miały identyczne tytuły i tajemnicze, dwuzdaniowe streszczenia odnoszące się do „ostatniego postępu w starym problemie Erdősa”. Podczas gdy Paul Erdős, węgierski matematyk, który zmarł w 1996 roku, pozował setki problemów w trakcie jego kariery kombinatorzy szybko odgadli konkretny problem, o którym trio zamierzało rozmawiać. Krążyły pogłoski o czymś, co nazywa się liczbą Ramseya, jedną z najtrudniejszych do obliczenia wielkości w całej matematyce.

Liczby Ramseya dały początek całej dyscyplinie zwanej teorią Ramseya, która szuka nieuniknionych wzorców w ogromnej gamie systemów.

Załóżmy na przykład, że próbujesz rozłożyć wszystkie liczby całkowite na kilka segmentów i chcesz uniknąć umieszczania sekwencji równomiernie rozmieszczonych liczb w dowolnym z segmentów. Teoria Ramseya pokazuje, że poniesiesz porażkę (chyba że masz nieskończenie wiele wiader). Teorię można zastosować do prawie wszystkiego, co można policzyć. Jego główną lekcją jest to, że „nie można stworzyć całkowicie chaotycznego systemu” – powiedział Benny Sudakov, matematyk ze Szwajcarskiego Federalnego Instytutu Technologii w Zurychu.

Liczba Ramseya określa ilościowo, jak duży musi być paradygmatyczny przykład, zanim nieuchronnie pojawią się określone wzorce. Ale pomimo jego centralnej pozycji nikt nie był w stanie obliczyć liczby Ramseya dla wszystkich oprócz najprostsze okazy. Najlepsze, co udało im się zrobić, to znaleźć ograniczenia (lub granice) tego, co to może być. Nawet wtedy górna granica ustalona przez Erdősa i jego współpracownika prawie sto lat temu ledwo się poruszyła.

Następnie, na seminariach 15 marca iw artykule opublikowanym później tego wieczoru, naukowcy ogłosili, że poprawili górną granicę liczby Ramseya o wartość wykładniczą.

„Byłem wniebowzięty” — powiedział Yuvala Wigdersona, matematyk z Uniwersytetu w Tel Awiwie, na wieść o nowym wyniku. „Dosłownie trząsłem się przez pół godziny do godziny”.

Linie partyjne

Teoria Ramseya najczęściej zadaje pytania dotyczące liczb całkowitych lub wykresów. Graf w tym kontekście odnosi się do zbioru punktów zwanych węzłami, połączonych liniami zwanymi krawędziami, które mogą mieć właściwości takie jak długość lub — jak w przypadku liczb Ramseya — kolor.

Kompletny graf jest zarówno skomplikowany, jak i prosty — każdy węzeł jest połączony z każdym innym węzłem. Liczba Ramseya opisuje, ile węzłów musi zawierać kompletny graf, aby zmusić go do posiadania określonej struktury. Powiedzmy, że krawędziom pełnego wykresu przypisano jeden z dwóch kolorów: czerwony lub niebieski. I powiedzmy, że próbujesz pokolorować krawędzie w sposób, który pozwala uniknąć łączenia grupy węzłów z krawędziami tego samego koloru. W 1930 roku Frank Ramsey udowodnił, że jeśli graf jest wystarczająco duży, nie da się uniknąć tworzenia tego, co matematycy nazywają kliką monochromatyczną — grupą węzłów, których wspólne krawędzie są albo wszystkie czerwone, albo wszystkie niebieskie.

Jak duży dokładnie musi być graf, zanim zostanie zmuszona do wyłonienia się monochromatycznej kliki? Odpowiedź zależy od wielkości kliki. Ramsey wykazał, że istnieje liczba, zwana teraz liczbą Ramseya, reprezentująca minimalną liczbę węzłów, dla których musi istnieć monochromatyczna klika o danym rozmiarze, bez względu na kolor krawędzi.

Ale wielkość liczby Ramseya jest trudna do ustalenia. W 1935 roku, pięć lat po tym, jak Ramsey wykazał, że istnieje, Erdős i George Szekeres przedstawili nową, ściślejszą górną granicę tego, jak duża jest liczba Ramseya dla kliki o danej wielkości. Ale od tego czasu matematycy ledwo byli w stanie poprawić obliczenia Erdősa i Szekeresa.

Aby lepiej zrozumieć, co to oznacza, rozważmy klasyczny przykład, w którym węzły reprezentują gości na przyjęciu. Pokoloruj krawędź między dwoma dowolnymi gośćmi na czerwono, jeśli spotkali się już wcześniej, i na niebiesko, jeśli się nie spotkali. Możesz wybrać dowolną wielkość kliki — zaproś na przyjęcie wystarczającą liczbę osób i nie możesz uniknąć zaproszenia grupy osób, które się znają (klika w wielu znaczeniach tego słowa) lub grupy osób, które nigdy wcześniej się nie spotkali.

„Najprostszą rzeczą, jaką można mieć na wykresie, jest monochromatyczna klika” — powiedział Maria Czudnowska, matematyk z Uniwersytetu Princeton. „To niesamowite, że na każdym dużym wykresie można znaleźć taki duży. To zupełnie nie jest jasne”.

Kilka pierwszych liczb Ramseya jest stosunkowo prostych do obliczenia. Powiedzmy, że chcesz poznać rozmiar najmniejszego wykresu, który nieuchronnie musi zawierać klikę o rozmiarze dwa lub R(2) dla matematyków. Ponieważ pełny graf z dwoma węzłami to tylko dwa wierzchołki połączone krawędzią, a ta krawędź musi być albo czerwona, albo niebieska, R(2) wynosi 2. Mówiąc bardziej ogólnie, R(k) lub liczba Ramseya k, to minimalna liczba węzłów, poza którą wykres nie może uniknąć zawierania kliki rozmiaru k.

Nie jest trudno pokazać, że liczba Ramseya dla kliki wielkości 3, czyli R(3), wynosi 6 (patrz rysunek). Ale dopiero w 1955 r. R(4) ustalono na 18. R(5) pozostaje nieznane — wynosi co najmniej 43 i nie więcej niż 48. Chociaż liczby te są niewielkie, przesiewanie wszystkich możliwych kolorów jest niemożliwe odpowiedzi na pytanie, powiedział David Conlon z California Institute of Technology. Rozważ liczbę kolorów na pełnym grafie z 43 węzłami. „Masz 903 krawędzie; każdy z nich można pokolorować na dwa sposoby” – wyjaśnił. „Więc dostajesz 2⁹⁰³, który jest po prostu astronomicznie duży”.

Wraz ze wzrostem wielkości kliki zadanie ustalenia liczby Ramseya staje się coraz trudniejsze. Erdős zażartował, że totalna wojna z matematycznie wymagającymi kosmitami byłaby łatwiejsza niż próba oblicz R(6), czyli gdzieś pomiędzy 102 a 165. Przedział niepewności szybko rośnie: wg szacunki opracowane przez Stanisława Radziszowskiego, R(10) może być tak małe jak 798 i tak duże jak 23,556 10. Ale cele matematyków wykraczają daleko poza liczbę Ramseya równą XNUMX. Chcą formuły, która da dobre oszacowanie R(k), nawet — lub zwłaszcza — kiedy k jest niezwykle duży.

„Nie znam osoby zajmującej się kombinatoryką, która choć trochę nie myślała o tym problemie” — powiedział Wigderson. „Myślę, że ten problem jest naprawdę wyjątkowy”.

Porządek w sądzie

Frank Ramsey był eklektyczną, błyskotliwą postacią, która zmarła w wieku 26 lat. Zaledwie kilka tygodni przed śmiercią, w Proceedings of London Mathematical Society opublikowany papier w którym wprowadził liczby Ramseya. Ta praca nie dotyczyła nawet wykresów, ale problemu z logiki matematycznej. Ramsey udowodnił, że stwierdzenie, które spełnia określone warunki, musi być prawdziwe przynajmniej przez pewien czas. Jednym z tych warunków było istnienie dużego „wszechświata” scenariuszy, w których można przetestować to stwierdzenie. Jako odskocznię do tego wyniku Ramsey wykazał, że liczba Ramseya jest skończona.

Pięć lat później Erdős i Szekeres wykazali, że liczba Ramseya k jest mniejsza niż 4^k. A 12 lat później Erdős pokazał że jest większy niż około $latex sqrt{2}^k$. Aby to zrobić, obliczył prawdopodobieństwo, że wykres z losowo kolorowymi krawędziami zawiera monochromatyczną klikę. Ta „probabilistyczna” technika wywarła ogromny wpływ na teorię grafów. Uwięził również R (k) między dwoma rosnącymi wykładniczo słupkami bramkowymi: $latex sqrt{2}^k$ i $latex 4^k$.

W miarę upływu dziesięcioleci wielu matematyków próbowało zmniejszyć różnicę między możliwymi wartościami liczby Ramseya. Niektórym się udało: w 1975 roku Joel Spencer podwoił dolną granicę. I seria artykułów ks Konon, Andrzej Tomaszon i Ashwin Saha obniżył górną granicę o współczynnik około $latex 4^{log(k)^2}$ do roku 2020. Jednak w porównaniu z rozmiarami granic liczby Ramseya te korekty były niewielkie. Z kolei jakakolwiek redukcja do 4 we wzorze Erdősa i Szekeresa R (k) < 4^k byłaby wykładniczą poprawą, rosnącą szybko jako k powiększa się.

„Wygląda na to, że to tylko urocze, małe pytanie” — powiedział Roba Morrisa, matematyk z IMPA, brazylijskiego Instytutu Matematyki Czystej i Stosowanej w Rio de Janeiro, który wraz z Camposem, Griffithsem i Sahasrabudhe jest współautorem nowego wyniku. „Docenianie jest trochę subtelne. Ale ludziom naprawdę na tym zależy”. Jest to prawdopodobnie niedopowiedzenie. „Gdyby udowodnili to w 1936 roku, ludzie powiedzieliby: OK, więc o co chodzi?” powiedział Béla Bollobás, który był doradcą doktoranckim Morrisa i Sahasrabudhe na Uniwersytecie w Memphis. „Od tego czasu udowodniono, że jest to bardzo duży problem, ponieważ na przestrzeni lat napisano kilka tysięcy artykułów na temat różnych wariantów problemu Ramseya”. Jak Liana Yepremyan, matematyk z Emory University, powiedział: „Liczby Ramseya tworzą pomost między kombinatoryką a prawdopodobieństwem i geometrią”.

Teoria gry

 W sierpniu 2018 Sahasrabudhe był stypendystą podoktoranckim pod kierunkiem Morrisa w IMPA. Obaj mieli nadzieję rozpocząć nowy projekt z Griffithsem, który wykłada na pobliskim Papieskim Uniwersytecie Katolickim, kiedy artykuł Conlona zwrócił ich uwagę. W artykule nakreślono możliwą strategię uzyskania wykładniczej poprawy liczby Ramseya. Griffiths, Morris i Sahasrabudhe zaczęli bawić się tym pomysłem.

„Na początku było naprawdę ekscytująco” — wspomina Sahasrabudhe. Zajęło im tylko około miesiąca, powiedział, przedstawienie szkicu ich argumentacji.

Ich plan polegał na wykorzystaniu pomysłów wykorzystanych w oryginalnym dowodzie Erdősa i Szekeresa, że ​​$latex R(k) < 4^k$. Aby udowodnić, że liczba Ramseya wynosi co najwyżej $latex 4^k$, wyobraź sobie grę na pełnym grafie z węzłami $latex 4^k$. Gra ma dwóch graczy. Najpierw twój przeciwnik koloruje każdą krawędź na czerwono lub niebiesko, mając nadzieję, że pokoloruje krawędzie w sposób, który pozwoli uniknąć tworzenia monochromatycznej kliki k węzły

Gdy twój przeciwnik skończy kolorować, twoim zadaniem jest wyszukanie monochromatycznej kliki. Jeśli go znajdziesz, wygrywasz.

Aby wygrać tę grę, możesz zastosować prostą strategię. Pomaga myśleć (metaforycznie) o sortowaniu węzłów na dwa segmenty. Węzły w jednym wiadrze utworzą niebieską klikę, a węzły w drugim – czerwoną. Niektóre węzły zostaną usunięte i nigdy więcej o nich nie będzie słychać. Na początku oba zasobniki są puste, a każdy węzeł jest kandydatem do przejścia do jednego z nich.

Zacznij od dowolnego węzła, który Ci się spodoba. Następnie spójrz na krawędzie łączące. Jeśli połowa lub więcej krawędzi jest czerwona, usuń wszystkie niebieskie krawędzie i węzły, z którymi są połączone. Następnie umieść swój pierwotny wybór w „czerwonym” wiaderku. Wszystkie czerwone krawędzie tego węzła wciąż żyją i mają się dobrze, przylegając do reszty wykresu z wnętrza wiadra. Jeśli więcej niż połowa krawędzi jest niebieska, analogicznie usuwasz czerwone krawędzie i węzły i umieszczasz je w niebieskim wiadrze.

Powtarzaj, aż nie będziesz mieć żadnych węzłów. (Ponieważ wykres jest gotowy, każdy pozostały węzeł w dowolnym punkcie jest podłączony do obu zasobników, dopóki nie zostanie umieszczony w jednym z nich).

Kiedy skończysz, zajrzyj do wiader. Ponieważ węzeł trafił do czerwonego pojemnika dopiero po wyeliminowaniu jego niebieskich sąsiadów, wszystkie węzły w czerwonym pojemniku są połączone czerwonymi krawędziami — tworzą czerwoną klikę. Podobnie niebieskie wiadro tworzy niebieską klikę. Jeśli Twój oryginalny graf ma co najmniej $latex 4^k$ węzłów, można udowodnić, że jeden z tych segmentów musi zawierać co najmniej k węzłów, gwarantując monochromatyczną klikę na oryginalnym wykresie.

Ten argument jest sprytny i elegancki, ale zmusza cię do zbudowania dwóch klik – jednej niebieskiej i jednej czerwonej – mimo że tak naprawdę potrzebujesz tylko jednej. Bardziej efektywne byłoby, gdyby zawsze był czerwony, wyjaśnił Conlon. Zgodnie z tą strategią wybierałbyś węzeł na każdym kroku, usuwał jego niebieskie krawędzie i wrzucał go do czerwonego wiadra. Czerwone wiadro szybko by się zapełniło, a ty zgromadziłbyś czerwoną klikę k węzłów w czasie o połowę krótszym.

Ale twoja strategia musi działać dla dowolnego czerwono-niebieskiego koloru i trudno jest stwierdzić, czy zawsze możesz znaleźć węzeł z dużą ilością czerwonych krawędzi. Tak więc podążanie za sugestią Conlona wiąże się z ryzykiem wpadnięcia na węzeł, który nie ma prawie żadnych czerwonych krawędzi. To zmusiłoby cię do usunięcia ogromnej części wykresu naraz, pozostawiając cię do budowania swojej kliki, zanim zabraknie węzłów. Aby wykonać sugestię Conlona, ​​Griffiths, Morris i Sahasrabudhe musieli udowodnić, że tego ryzyka można było uniknąć.

Egzamin z otwartej książki

Aktualizując swoją rozgrywkę, Griffiths, Morris i Sahasrabudhe poszli nieco bardziej okrężną drogą. Zamiast budować monochromatyczną klikę bezpośrednio, wrzucając węzły do ​​ich czerwonych i niebieskich wiader, najpierw skupili się na zbudowaniu struktury zwanej czerwoną księgą.

Książka, w teorii grafów, składa się z dwóch części: jest monochromatyczna klika, zwana „kręgosłupem” i druga, odrębna grupa węzłów zwana „stronami”. W czerwonej księdze wszystkie krawędzie łączące węzły w grzbiecie są czerwone, podobnie jak krawędzie łączące grzbiet ze stronami. Krawędzie łączące węzły na stronach mogą mieć jednak dowolną kombinację kolorów. Conlon zauważył w swoim artykule z 2018 roku, że jeśli znajdziesz czerwoną klikę na stronach książki, możesz połączyć ją z grzbietem, aby uzyskać większą czerwoną klikę. Pozwala to rozłożyć wyszukiwanie dużej czerwonej kliki na dwa łatwiejsze wyszukiwania. Najpierw poszukaj czerwonej książki. Następnie poszukaj kliki na stronach książki.

Griffiths, Morris i Sahasrabudhe chcieli dostosować zwycięski algorytm tak, aby tworzył czerwoną księgę zamiast czerwonej kliki. Chociaż zdecydowali się na ten plan zaledwie kilka tygodni po rozpoczęciu projektu, zajęłoby to lata. Nadal musieli oddalić groźbę utraty wszystkich czerwonych krawędzi.

„Utknęliśmy na bardzo długi czas” – powiedział Campos, który dołączył do projektu w 2021 roku.

W styczniu tego roku czterej matematycy zgodzili się przejść do innej wersji problemu. Ta wersja brzmi bardziej skomplikowanie, ale okazała się prostsza.

Cały czas zespół koncentrował się na liczbie Ramseya R (k), znany również jako „przekątna” liczba Ramseya. Wykres o rozmiarze R (k) musi zawierać k węzły, wszystkie połączone krawędziami tego samego koloru, ale nie ma znaczenia, czy ten kolor jest czerwony czy niebieski. Z drugiej strony „poza przekątną” liczba Ramseya R(k, l) mierzy, jak duży musi być wykres, zanim będzie zawierał czerwoną klikę z k węzły lub niebieska klika z l węzły. Zamiast kontynuować rozwiązywanie problemu z przekątną, grupa postanowiła wypróbować wersję poza przekątną. To okazało się odkrywcze.

„Przez długi czas wydawało się, że każde drzwi, które naciskałeś, były albo zaryglowane, albo przynajmniej dość trudne do przejścia” – powiedział Griffiths. „A po tej zmianie po prostu czułeś, że wszystkie drzwi są otwarte. W jakiś sposób wszystko wydawało się działać”. W wersji poza przekątną znaleźli sposób na jednoczesne usunięcie kilku niebieskich krawędzi zgodnie z określonym protokołem, co zwiększyło gęstość czerwonych krawędzi i doprowadziło do lepszego ograniczenia liczby Ramseya poza przekątną. Ta metoda, zwana argumentem „przyrostu gęstości”, była wcześniej używana do rozwiązywania inne ważne problemy kombinatoryki, ale nie został użyty w problemie liczbowym Ramseya.

Czterej matematycy wykorzystali następnie nowe ograniczenie liczby Ramseya poza przekątną, aby utorować drogę do wyniku ukośnego. Na początku lutego ostatecznie obniżyli granicę liczby Ramseya o współczynnik wykładniczy, osiągnięcie, którego matematycy szukali od prawie wieku. I zrobili to poprzez unowocześnienie tej samej argumentacji, którą przedstawili Erdős i Szekeres w 1935 roku.

Epsilon, Epsilon

Po rozmowach 16 marca uczestnicy zaczęli potwierdzać plotki. Zdjęcia z przemówienia Sahasrabudhe krążyły w rozmowach telefonicznych i prywatnych wiadomościach — nawet w niejasny, ale sugestywny post na blogu matematyka Gila Kalai. Campos, Griffiths, Sahasrabudhe i Morris twierdzili, że wykazali, że $lateks R(k) <3.993^k$. Tej nocy czterech autorów zamieścili swój artykuł w Internecie, pozwalając matematykom zobaczyć nowy dowód na własne oczy.

„Myślę, że wielu z nas nie spodziewało się takiej poprawy w swoim życiu” – powiedział Matija Bucić, matematyk z Princeton University i Institute for Advanced Study. „Myślę, że to absolutnie niesamowity wynik”.

Wielu ekspertów ma nadzieję, że wraz ze zniesieniem wykładniczej bariery szybko nastąpi dalszy postęp. Autorzy nowego artykułu celowo nie przekroczyli granic swojej metody, aby uniknąć zmętnienia argumentacji niepotrzebnymi szczegółami. „Jestem bardzo zainteresowany tym, jak daleko może zajść ta metoda, ponieważ nie mam pojęcia” – powiedział Campos.

„To całkowicie genialny, absolutnie wspaniały dowód i prawdziwy przełom. Więc teraz oczekuję, że śluzy zostaną otwarte” – powiedział Bollobás. „Jestem przekonany, że za trzy lata debata będzie dotyczyła możliwych usprawnień. Czy możemy poprawić 3.993 do 3.9? Może do 3.4? A co z 3?

Nowy dowód ma 56 stron, a pełna weryfikacja każdego szczegółu przez społeczność kombinatoryków zajmie tygodnie. Ale koledzy są optymistami. „Ta grupa autorów to bardzo poważni ludzie. I są to ludzie, którzy są naprawdę dobrzy w bardzo technicznych rzeczach” – powiedział Wigderson.

Jeśli chodzi o jego współpracowników, Griffiths zgadza się. „Praca z genialnymi ludźmi to przywilej, prawda? I myślę, że właśnie za to jestem bardzo wdzięczny” – powiedział. „Gdyby zostawili to mnie, dopracowanie szczegółów zajęłoby mi kolejne pięć lat”.