Nombre de Graham

Le nombre de Graham entretient un lien avec une branche des mathématiques connue sous le nom de théorie de Ramsey :

Soit un hypercube de dimension n dont on relie tous les couples de sommets pour obtenir un graphe complet à 2ⁿ sommets. Si l'on colorie chacune des 2^n–1(2ⁿ – 1) arêtes du graphe en bleu ou en rouge, quelle est la plus petite valeur de n telle que, pour chaque façon de colorier le graphe, il existe un sous-graphe complet monochrome sur quatre sommets coplanaires ?

On ne connait pas encore la réponse à cette question, mais on sait depuis 2003[2] que ce plus petit n doit être supérieur ou égal à 11 et depuis 2008[3] qu'il vaut même au moins 13.

Quant aux majorants de ce plus petit n, le meilleur connu en 1971 était[4]

${\displaystyle \left.{\begin{matrix}\underbrace {2\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 3} \\\underbrace {2\uparrow \cdots \cdots \cdots \uparrow 3} \\{\vdots }\\\underbrace {\qquad \qquad \qquad } \\{2\uparrow \cdots \cdots \uparrow 3}\end{matrix}}\right\}{\text{7 niveaux}}}$

(il a été affiné depuis[5]).

Ce nombre est énorme, mais encore moins que le « nombre de Graham » G ci-dessous. Le nombre G doit sa célébrité et son nom à ce qu'il a été présenté en 1977 par Martin Gardner, dans le Scientific American, comme un majorant dû à Graham[6], au lieu[7] du majorant bien plus précis ci-dessus, trouvé par Graham et Rothschild.

Le nombre de Graham est le 64^e terme de la suite :

${\displaystyle 4,\ 3\uparrow \uparrow \uparrow \uparrow 3,\ 3\uparrow \cdots \uparrow 3,\ 3\uparrow \cdots \uparrow 3,\ \ldots }$

où chaque terme est le nombre de flèches du terme suivant, en utilisant la notation des flèches de Knuth.

De façon équivalente, soit f(n) = hyper(3, n + 2, 3) = 3 → 3 → n ; alors le nombre de Graham est la valeur de la 64^e itérée de la fonction f au point 4.

${\displaystyle \left.{\begin{matrix}G&=&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \cdots \uparrow } 3\\&&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow } 3\\&&\underbrace {\qquad \;\;\vdots \qquad \;\;} \\&&3\underbrace {\uparrow \uparrow \cdots \cdot \cdot \uparrow } 3\\&&3\uparrow \uparrow \uparrow \uparrow 3\end{matrix}}\right\}{\text{64 niveaux}}}$

Le nombre de Graham G lui-même ne s'exprime pas commodément avec la notation des flèches chaînées de Conway, mais on a l'encadrement

${\displaystyle 3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2.}$

De même, la hiérarchie de croissance rapide permet d'écrire l'encadrement

${\displaystyle f_{\omega +1}(63)<G<f_{\omega +1}(64).}$