Graham's Number
Let π N^*
be the smallest dimension π n
of a hypercube such that if
the lines joining all pairs of corners are two-colored
for any π n>=N^*
,
a complete graph π K_4
of one color with coplanar vertices will be forced. Stated
colloquially, this definition is equivalent to considering every possible committee
from some number of people π n
and enumerating every pair of committees. Now assign each
pair of committees to one of two groups, and find π N^*
the smallest π n
that will guarantee that there are four committees in which
all pairs fall in the same group and all the people belong to an even number of committees
(Hoffman 1998, p. 54).
An answer was proved to exist by Graham and Rothschild (1971), who also provided the best known upper bound, given by
where Graham's number π g_(64)
is recursively defined by
| π g_1=3^^^^3 |
(2)
|
and
Here, π ^
is the so-called Knuth up-arrow notation.
π g_(64)
is often cited as the largest number
that has ever been put to practical use (Exoo 2003).
In chained arrow notation, π g_(64)
satisfies the inequality
Graham and Rothschild (1971) also provided a lower limit by showing that π N^*
must be at least 6. More recently, Exoo (2003) has shown
that π N^*
must be at least 11 and provides experimental evidence suggesting that it is actually
even larger.
See also
Chained Arrow Notation, Extremal Graph Theory, Graph Two-Coloring, Hamming Distance, Hypercube, Knuth Up-Arrow Notation, Ramsey Theory, Skewes NumberExplore with Wolfram|Alpha
More things to try:
References
Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, pp. 61-62, 1996.Exoo, G. "A Euclidean Ramsey Problem." Disc. Comput. Geom. 29, 223-227, 2003.Exoo, G. "A Ramsay Problem on Hypercubes." http://isu.indstate.edu/ge/GEOMETRY/cubes.html.Gardner, M. "Mathematical Games." Sci. Amer. 237, 18-28, Nov. 1977.Graham, R. L. and Rothschild, B. L. "Ramsey's Theorem for π n
-Parameter Sets." Trans. Amer. Math. Soc. 159, 257-292, 1971.Havil, J. Gamma: Exploring Euler's Constant. Princeton, NJ: Princeton University Press, pp. 200 and 209, 2003.Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul ErdΕs and the Search for Mathematical Truth. New York: Hyperion, pp. 18 and 54, 1998.
Referenced on Wolfram|Alpha
Graham's NumberCite this as:
Weisstein, Eric W. "Graham's Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GrahamsNumber.html