info prev up next book cdrom email home

Graham's Number

The smallest dimension of a Hypercube such that if the lines joining all pairs of corners are two-colored, a Planar Complete Graph $K_4$ of one color will be forced. That an answer exists was proved by R. L. Graham and B. L. Rothschild. The actual answer is believed to be 6, but the best bound proved is

\hfill\underbrace{3 \uparrow\uparrow\uparrow\uparr...
...3 }\vdots\phantom{3 }}\hfill\cr
\hfill 3 \uparrow 3,\hfill\cr}

where $\uparrow$ is stacked Arrow Notation. It is less than $3\to 3\to 3\to 3$, where Chained Arrow Notation has been used.

See also Arrow Notation, Chained Arrow Notation, Skewes Number


Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, pp. 61-62, 1996.

Gardner, M. ``Mathematical Games.'' Sci. Amer. 237, 18-28, Nov. 1977.

© 1996-9 Eric W. Weisstein