TOPICS
Search

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

 N^*<=g_(64),
(1)

where Graham's number g_(64) is recursively defined by

 g_1=3^^^^3
(2)

and

 g_n=3^...^_()_(g_(n-1))3.
(3)

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

 3->3->64->2<g_(64)<3->3->65->2.
(4)

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 Number

Explore with Wolfram|Alpha

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 Number

Cite this as:

Weisstein, Eric W. "Graham's Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GrahamsNumber.html

Subject classifications