* Kopenhaga
Redaktor Delty w latach 2006–2007.
W 1976 roku, na drugie urodziny Delty, Kenneth Appel i Wolfgang Hakken ogłosili dowód twierdzenia o czterech barwach. W nieco nieformalnej wersji głosi ono, że każdą mapę polityczną, na której wszystkie kraje mają spójne terytorium, można pokolorować czterema lub mniej kolorami tak, aby osiągnąć znany nam z kartografii efekt, w którym każde dwa graniczące ze sobą kraje mają różne kolory. Wynik ten był przełomowy z dwóch powodów. Po pierwsze, rozwiązywał znaną w teorii grafów hipotezę o bardzo długiej i (nota bene) barwnej historii. Po drugie, był to pierwszy, a przez to kontrowersyjny, poważny wynik, w którego dowodzie użyto komputera (po sprowadzeniu problemu do pewnej skończonej, lecz dużej liczby przypadków do sprawdzenia). O tej historii można przeczytać w \(\Delta^{6}_{04}\).
Wynik Appela i Hakkena można przeformułować na stwierdzenie, że dla dowolnego planarnego grafu \(G\) mamy \(\chi(G)\leq 4\). Tutaj \(\chi(G)\) jest liczbą chromatyczną grafu \(G\), czyli najmniejszą liczbą kolorów potrzebną do pokolorowania wierzchołków \(G\) tak, żeby żadne dwa wierzchołki połączone krawędzią grafu nie miały tego samego koloru. Problemy związane z kolorowaniem grafów i obliczaniem liczby chromatycznej są algorytmicznie trudne i, poza walorami estetycznymi, znajdują zastosowanie na przykład w problemach planowania i przydziału zadań. O tych zagadnieniach była już w Delcie nie raz mowa, patrz na przykład \(\Delta^{11}_{14}\).
Wrzeciono Mosera: 7 wierzchołków, wszystkie krawędzie długości 1
Pojęcie liczby chromatycznej grafu można też odnieść do innych zagadnień kolorowania. W \(\Delta^7_{08}\) pytałem, jak wykazać, że jeśli każdy punkt płaszczyzny \(\mathbb{R}^2\) pokolorujemy jednym z trzech kolorów, to znajdą się dwa punkty tego samego koloru odległe o dokładnie \(1\). Dowód znajduje się na rysunku, gdzie widzimy konfigurację 7 punktów z zaznaczonymi odcinkami długości 1, zwaną wrzecionem Mosera. Liczba chromatyczna tego grafu wynosi \(4\) (faktycznie: próba kolorowania 3 kolorami prowadzi do wniosku, że \(A\) i \(A'\) muszą mieć ten sam kolor; analogicznie \(A\) i \(A''\); a więc punkty \(A'\) i \(A''\) odległe o \(1\) mają ten sam kolor; sprzeczność). Jeżeli więc oznaczymy przez \(\chi(\mathbb{R}^2)\) najmniejszą liczbę kolorów potrzebną do uniknięcia pary punktów tego samego koloru w odległości \(1\) przy kolorowaniu płaszczyzny, to mamy lewą z nierówności \[4\leq \chi(\mathbb{R}^2) \leq 7.\] Prawa jest również łatwa – zachęcam do znalezienia odpowiedniego kolorowania płaszczyzny 7 kolorami.
W 2008 roku pisałem, że nic bardziej konkretnego nie wiadomo (pytanie o dokładną wartość \(\chi(\mathbb{R}^2)\) jest znane jako problem Hadwigera–Nelsona) i zanosiło się na to, że tak już zostanie. Ale w 2018 roku Aubrey de Grey zaskoczył świat, publikując dowód nierówności \[5\leq \chi(\mathbb{R}^2).\] Zamiast 7-wierzchołkowego gadżetu Mosera, który nie daje się pokolorować 3 kolorami, de Grey musiał skonstruować analogiczny gadżet, złożony z punktów płaszczyzny i krawędzi jednostkowych między niektórymi z nich, którego nie da się pokolorować 4 kolorami. Okazało się, że ma on 1581 wierzchołków (od tego czasu znaleziono przykłady o około 500 wierzchołkach) i z oczywistych przyczyn nie możemy go wydrukować. Można go znaleźć, wraz z systematyczną konstrukcją, w pracy [1]. Podobnie jak w przypadku gadżetu Mosera, towarzyszy mu dowód oraz wyjaśnienie, jak do tego przykładu dojść (kilka początkowych wskazówek można znaleźć w Deltoidzie z \(\Delta^{12}_{18}\)). Niektóre sprawdzenia wymagały jednak obliczeń komputerowych, a więc jest to już dowód wspomagany komputerowo.
O analogicznej liczbie chromatycznej \(\chi(\mathbb{R}^{n})\) wyżej wymiarowych przestrzeni wiemy jeszcze mniej (na przykład w trzech wymiarach wiemy, że \({6\leq \chi(\mathbb{R}^3)\leq 15}\)), a znane rezultaty wciąż opierają się na dość elementarnych pomysłach. Popatrzmy na przykład na następujący prosty dowód z pracy [2] najlepszego znanego dziś dolnego oszacowania dla \(\mathbb{R}^{10}\), mianowicie: \(\chi(\mathbb{R}^{10})\geq 26\). Musimy znaleźć odpowiedni gadżet, tzn. zbiór punktów w \(\mathbb{R}^{10}\) i odcinków długości \(1\) pomiędzy nimi, którego nie da się pokolorować 25 kolorami. Jako punkty weźmiemy wierzchołki 10-wymiarowej kostki o krawędzi \(\frac12\), to znaczy 1024-elementowy zbiór złożony z wszystkich ciągów: \[(x_1,x_2,\ldots,x_{10}),\ \ \ x_i\in\left\{0,\frac12\right\}.\] Dwa takie punkty są odległe o \(1\) wtedy i tylko wtedy, gdy różnią się na dokładnie \(4\) z \(10\) pozycji (bo te pozycje wnoszą do wzoru na odległość euklidesową \((0-\frac12)^2=\frac14,\) podczas gdy pozostałe pozycje, gdzie oba ciągi są równe, wnoszą \(0\)). Możemy więc skonstruować graf odcinków jednostkowych pomiędzy tymi punktami czysto kombinatorycznie. Ma on dwie spójne składowe (dlaczego?), każda o 512 wierzchołkach, bierzemy więc jedną z nich. Dokładne obliczenie jej liczby chromatycznej przekracza nasze możliwości, ale da się obliczyć inny parametr, mianowicie liczność największego zbioru niezależnego, tzn. największego zbioru wierzchołków, między którymi nie ma żadnej krawędzi. Oto kompletna komenda w popularnym systemie algebry komputerowej Sage konstruująca nasz graf i obliczająca poszukiwaną wartość:
Graph([[x,y] for x in [0..2^10-1] for y in [x+1..2^10-1]
if sum((x^^y).bits())==4])
.connected_components_subgraphs()[0].complement().clique_number()Jak wiadomo, każdy program można zmieścić w jednym wierszu, jeśli tylko będzie on odpowiednio długi.
Po kilkunastu minutach w wyniku otrzymujemy 20, co oznacza, że jeden kolor może być użyty dla co najwyżej 20 wierzchołków, a więc używając 25 kolorów, pomalowalibyśmy ich co najwyżej \(20\cdot 25=500\), a to za mało na cały
Na zakończenie kluczowa notka biograficzna. Aubrey de Grey, autor pracy [1], nie jest zawodowym matematykiem. Jest bioinformatykiem i biogerontologiem, badaczem procesów starzenia, a kolorowaniem zajmował się amatorsko po godzinach. Z kolei publikacja [2] jest efektem pracy licencjackiej. W starciu z ciekawymi problemami otwartymi ma więc szansę każdy pomysłowy eksperymentator, a takich, jak sądzę, wśród Czytelników Delty nie brakuje.
Literatura
de Grey, Aubrey D. N. J., ,,The chromatic number of the plane is at least 5”. Geombinatorics 28 (2018), także: arxiv.org/abs/1804.02385
Matthew Kahle, Birra Taha, ,,New lower bounds on \(\chi(\mathbb{R}^d)\) for \(d=8,\dots,12\)”, Geombinatorics 24 (2015), także: arxiv.org/abs/1409.1278