Przeskocz do treści

Delta mi!

Największa liczba na świecie

Tomasz Bartnicki

o artykule ...

  • Publikacja w Delcie: marzec 2008
  • Publikacja elektroniczna: 18 grudnia 2010
  • Autor: Tomasz Bartnicki
    Afiliacja: Instytut Matematyki, Uniwersytet Zielonogórski
  • Artykuł otrzymał Nagrodę Dziekanów 2007/2008

Grafy Ramseya w przestrzeni

W dotychczasowych rozważaniach grafy traktowaliśmy w sposób abstrakcyjny, czyli jako parę złożoną z pewnego skończonego zbioru V (wierzchołki) i z kolekcji jego dwuelementowych podzbiorów E (krawędzie), natomiast tradycyjny rysunek grafu na płaszczyźnie (punkty połączone liniami) służył nam jedynie do lepszej wizualizacji prezentowanych problemów, ale w żaden sposób nie wykorzystywaliśmy jego geometrycznych własności.

Ostatnim krokiem do poznania największej liczby na świecie będzie spojrzenie na twierdzenie Ramseya w sposób geometryczny. Będziemy rozważać grafy pełne, których wierzchołki będą umieszczone we wszystkich wierzchołkach wielowymiarowej kostki jednostkowej w przestrzeni euklidesowej dowolnego wymiaru (na prostej będą to końce odcinka, na płaszczyźnie wierzchołki kwadratu, w przestrzeni trójwymiarowej wierzchołki sześcianu itd.). Ogólnie w przestrzeni Rn będzie 2n wierzchołków (a więc powstanie graf |K2n ) i będą nimi wszystkie punkty, których współrzędne tworzą ciąg zerojedynkowy.

Była już mowa, że R(4) | = 18 , a więc, jeśli krawędzie grafu pełnego, który ma co najmniej 18 wierzchołków, pomalujemy dwoma kolorami, to musi się pojawić jednokolorowa klika |K4 . Jeżeli rozważać będziemy tylko kolorowania grafów pełnych związanych z kostkami jednostkowymi, to zauważymy, że w przestrzeni  4 R graf taki ma tylko 16 wierzchołków, a więc możemy jego krawędzie tak pokolorować, by uniknąć jednokolorowej kliki |K4 , natomiast już w przestrzeni R5 | w grafie na 32 wierzchołkach klika taka pojawi się w każdym dwukolorowaniu.

Zażądajmy dodatkowej własności: aby klika K4 była nie tylko jednokolorowa, ale na dodatek, aby wszystkie jej wierzchołki leżały w jednej płaszczyźnie (nazywamy ją płaską). Możemy teraz postawić pytanie: jakiego wymiaru musi być kostka jednostkowa, aby w dowolnym dwukolorowaniu krawędzi grafu pełnego z nią powiązanego zawsze pojawiła się płaska i monochromatyczna kopia kliki K4 ? Zauważmy, że klasyczne twierdzenie Ramseya nie mówi nam nic o jakichkolwiek geometrycznych własnościach, a więc nie mamy żadnej pewności, iż powyższe pytanie ma w ogóle odpowiedź wyrażającą się skończoną liczbą.

W 1971 roku Ronald Graham i Bruce Rothschild opublikowali pracę, w której udowodnili twierdzenie bardzo głęboko uogólniające wiele dotychczasowych rezultatów typu ramseyowskiego. Twierdzenie Ramseya było tylko drobnym wnioskiem płynącym z ich ogólnych rozważań. Twierdzenie Grahama-Rothschilda dawało również pozytywną odpowiedź na postawione wcześniej pytanie. Mianowicie, istnieje taka liczba naturalna n |, że w dowolnym dwukolorowaniu krawędzi grafu pełnego powiązanego z |n-wymiarową kostką jednostkową zawsze pojawi się płaska i jednokolorowa klika |K4 . Oznaczmy najmniejsze n | o tej własności przez (1,2,2) RG . Nadmiar parametrów w |RG ma na celu pokazanie, że jest to w istocie szczególny (najmniejszy nietrywialny) przypadek ogólnego twierdzenia. Oznaczają one kolejno: 1 - kolorujemy obiekty jednowymiarowe (krawędzie), 2 - obiekt, który musi się pojawić, jest dwuwymiarowy (płaska klika K4 ), 2 - używamy dwóch kolorów.

Nasuwa się naturalne pytanie, czy znana jest dokładna wartość (1,2,2)RG , a jeśli nie, to czy można ją jakoś sensownie oszacować. Ronald Graham pokusił się o wyliczenie konkretnej wartości jej górnego oszacowania, które wynikało bezpośrednio z dowodu ich głównego twierdzenia i zamieścił ten wynik w opublikowanej wspólnie z Rothschildem pracy. Jednak szerzej stał się on znany dopiero w 1977 roku, kiedy został opisany przez Martina Gardnera na łamach jego popularnej rubryki w Scientific American. Wiadomo więc, że (1,2,2)⩽LG, RG gdzie LG nazywana jest liczbą Grahama, lecz zanim poznamy jej wartość, konieczne będzie zapoznanie się ze specjalną notacją.

Notacja strzałkowa Knutha

Gdy na początku swojej edukacji poznajemy nowe działanie arytmetyczne, staramy się je zdefiniować za pomocą działań poznanych wcześniej. Mnożenie dwóch liczb naturalnych m definiuje się jako |n -krotne dodawanie składnika m , z kolei potęgowanie mn | , jako n | -krotne mnożenie czynnika m . Donald Knuth wpadł na pomysł, aby procedurę tę uogólnić, definiując kolejne działania jako wielokrotne złożenia poprzednich. Punktem wyjścia niech będzie zwykłe potęgowanie:

m

które zapisujemy za pomocą pojedynczej strzałki (tak jak tradycyjny zapis używany w informatyce). Kolejne działania notować będziemy podobnie (zwiększając tylko liczbę strzałek) i definiować rekurencyjnie:

m

m

a w ogólności

m

Ponieważ działania strzałkowe nie są łączne, to ustalamy dodatkowo, że w przypadku braku nawiasów wykonujemy je w kolejności od prawej do lewej (analogicznie jak przy wielokrotnym potęgowaniu). Aby nieco oswoić się z taką notacją, wykonajmy kilka prostych obliczeń. Łatwo zauważyć, że

2 ⋯ 2

jest zawsze równe 4, niezależnie od liczby strzałek, nietrudno też obliczyć, że

3 3 = 33 = 27.

Nieco dłuższe rachunki musimy wykonać, aby obliczyć

3 3 = 3 3 3 = 3 27 = 327 = 7625597484987.

Jeśli liczba rzędu siedmiu bilionów nas nie przeraża, to spróbujmy obliczyć

3 3 = 3 3 3 = 3 7625597484987

i tu, niestety, nasza moc obliczeniowa staje się niewystarczająca, gdyż w kolejnym kroku musielibyśmy napisać przeszło siedem i pół biliona trójek przedzielonych pojedynczymi strzałkami, co w tradycyjnym zapisie oznacza wieżę potęgową o wysokości 7625597484987 zbudowaną z trójek. Oczywiście, trudna jest jakakolwiek próba wyobrażenia sobie wielkości tej liczby. Możemy chyba tylko czuć ją intuicyjnie, widząc jej zapis w postaci wieży potęgowej.

Liczba Grahama

Jeśli chcesz, Czytelniku, poznać wielkość liczby Grahama, musisz pójść krok dalej i spróbować ogarnąć (choć jest to prawdopodobnie niewykonalne) wielkość liczby =3 3 G 0 , a następnie wykonać krok drugi (który jest już chyba krokiem w otchłań nieskończoności) i poznać liczbę zdefiniowaną następująco:

1=3 ⋯ 3. G G0strzałek

Jeśli wykonaliśmy 2 kroki, to kolejne nie powinny już sprawić trudności. Niech

2=3 ⋯ 3, G G1strzałek

3=3 ⋯ 3, G G2strzałek

i tak dalej, aż po 64 krokach zatrzymamy się wreszcie, bo oto poznamy największą liczbę na świecie, czyli Liczbę Grahama:

(1,2,2)⩽LG=G63=3 ⋯ 3. RG G62strzałek

Na zakończenie warto odnotować pewną ciekawostkę. Liczba Grahama została zauważona również przez ludzi, którzy zawodowo zajmują się wszelkimi rekordowymi osiągnięciami, trafiła bowiem w 1997 roku do Księgi Rekordów Guinnessa i, prawdopodobnie, pozostanie tam jeszcze przez długie lata. Należy jeszcze dodać, że najlepszym znanym dziś dolnym oszacowaniem liczby (1,2,2)RG jest 10 , więc pierwszą możliwą jej dokładną wartością jest liczba 11.