Grahams Zahl (nach Ronald L. Graham) ist eine obere Grenze für ein Problem der Ramsey-Theorie.

Grahams Problemstellung

---

In einem n-dimensionalen Hyperwürfel seien alle Punkte (Ecken, Knoten) je paarweise durch eine Kante verbunden, so dass ein vollständiger Graph auf 2ⁿ Knoten entsteht.

Diese Kanten werden nun mit jeweils einer von zwei Farben eingefärbt. Es ergibt sich die Frage, wie groß n sein muss, damit es notwendigerweise immer mindestens einen gleichfarbigen vollständigen Untergraphen gibt, der aus 4 Knoten besteht, die in einer Ebene liegen. Anders ausgedrückt: Ab welcher Dimension tritt notgedrungen die genannte Form von Ordnung auf?

Das Problem wurde noch nicht gelöst. Graham und Rothschild (1971) haben gezeigt, dass n mindestens 6 ist, Exoo (2003) zeigte, dass n ≥ 11. Grahams Zahl ist andererseits eine obere Grenze für dieses Problem, d.h. n < G₆₄.

Definition von Grahams Zahl

---

Grahams Zahl ist so groß, dass sie am besten mit Knuths Pfeil-Schreibweise ausgedrückt werden kann. Diese wird am besten anhand einiger Beispiele verdeutlicht (statt ^ wird oft auch $\backslash uparrow$ verwendet):

$$

m\hat{\ }n=\underbrace{m\cdot m\cdot m\cdot \ldots \cdot m\cdot m}_{n-\mathrm{mal}}

$$

m\hat{\ }\hat{\ }n=\underbrace{m\hat{\ } m\hat{\ } m\hat{\ }\ldots\hat{\ } m\hat{\ } m}_{n-\mathrm{mal}}

$$

m\hat{\ }\hat{\ }\hat{\ }n=\underbrace{m\hat{\ }\hat{\ } m\hat{\ }\hat{\ } m\hat{\ }\hat{\ }\ldots\hat{\ }\hat{\ } m\hat{\ }\hat{\ } m}_{n-\mathrm{mal}}

$$

\vdots

Hierbei ist zu beachten, dass der Potenzoperator $\backslash hat\{\backslash \; \}$ nicht assoziativ ist. Der klammerfrei notierte Ausdruck $m\backslash hat\{\backslash \; \}\; m\backslash hat\{\backslash \; \}\; \backslash ldots\; m\backslash hat\{\backslash \; \}\; m$ ist deshalb mehrdeutig; in diesem Fall ist er von rechts nach links abzuarbeiten, d. h. beispielsweise ist $m\backslash hat\{\backslash \; \}m\backslash hat\{\backslash \; \}m\; =\; m\backslash hat\{\backslash \; \}(m\backslash hat\{\backslash \; \}m)$ zu lesen. Diese Abarbeitungsreihenfolge ist auch gerade diejenige, bei der die größten Endergebnisse hervorgebracht werden.

Ausgestattet mit dieser Notation kann man eine Folge bilden, die durch die folgenden Regeln rekursiv definiert ist:

$$

G_0=4

$$

G_n=3\ \underbrace{\hat{\ }\hat{\ }\hat{\ }\cdots\hat{\ }}_{G_{(n-1)}\mathrm{-mal}}\ 3

Grahams Zahl ist nun definiert als $G=G\_\{64\}$.

Zur besseren Veranschaulichung, wie extrem groß Grahams Zahl ist, werden hier die ersten Schritte zur Berechnung von $G\_\{1\}=3\backslash hat\{\backslash \; \}\backslash hat\{\backslash \; \}\backslash hat\{\backslash \; \}\backslash hat\{\backslash \; \}3$ angegeben:

$$

3\hat{\ }3 = 3\cdot3\cdot3 = 27

$$

3\hat{\ }\hat{\ }3 = 3\hat{\ }(3\hat{\ }3) = 3\hat{\ }27 = 7.625.597.484.987

$$

3\hat{\ }\hat{\ }\hat{\ }3 = 3\hat{\ }\hat{\ }(3\hat{\ }\hat{\ }3) = 3\hat{\ }\hat{\ }7.625.597.484.987 = \underbrace{3\hat{\ }(3\hat{\ }(3\hat{\ }\ldots\hat{\ }(3\hat{\ }3)\ldots)}_{7.625.597.484.987-\mathrm{mal}}

Bereits $G\_\{1\}$ lässt sich nicht mehr vernünftig in der üblichen Exponentialdarstellung ausdrücken. Nichts desto weniger kann man die letzten Stellen von Grahams Zahl $G\_\{64\}$ mit elementarer Zahlentheorie bestimmen. Die letzten 10 Stellen sind 2464195387.

Laut Guinness-Buch der Rekorde ist sie die größte jemals in einem mathematischen Beweis verwendete Zahl. Genauer müsste es „in einem sinnvollen mathematischen Beweis“ lauten, denn ansonsten könnte jemand den mathematischen Satz „Es gilt $G\_\{65\}>G\_\{64\}$“ formulieren und einen einfachen Beweis dafür liefern.

Weblinks

---

• Beitrag bei MathWorld
• Ronald Grahams Homepage
• Grahams Zahl auf Susan Stepneys Homepage
• A Ramsey Problem on Hypercubes von Geoff Exoo

Zahlen | Graphentheorie

Graham's number | Nombre de Graham | Graham-szám | グラハム数 | Getal van Graham | 葛立恆數