# Graham's number

Graham's number is a stupendously large number that found
its way in to the *Guinness Book of Records* as the biggest number
ever obtained as part of a mathematical proof; it is named after its discoverer,
Ronald Graham. Graham's number is the upper bound
solution to a very exotic problem in Ramsey
theory, namely: What is the smallest dimension *n* of a hypercube such that if the lines joining all pairs of corners are two-colored, a planar
complete graph K4 of one color will be forced?

This is exactly equivalent to a problem that can be stated in plain language: Take any number of people, list every possible committee that can be formed from them, and consider every possible pair of committees. How many people must be in the original group so that no matter how the assignments are made, there will be four committees in which all the pairs fall in the same group, and all the people belong to an even number of committees. Graham's number is the greatest value that the answer could take. It is so large that it can only be written using special big-number notation, such as Knuth's up-arrow notation. Even then, it must be built up in stages.

First, construct the number G_{1} = 3↑↑...↑↑3,
where there are 3↑↑↑↑3
up-arrows. This, in itself, is a number far, far beyond anyone's ability
to even remotely comprehend. Next, construct G_{2} = 3↑↑...↑↑3,
where there are G_{1} up-arrows; then construct G_{3} =
3↑↑...↑↑3,
where there are G_{2} up-arrows; then continue this pattern until
the number G_{62} has been made. Graham's number G = 3↑↑...↑↑3,
where there are G_{62} up-arrows. While the unthinkably large upper
boundary to the problem described earlier is given by Graham's number, nobody,
including Graham himself, believes the solution is nearly so large. In fact,
it is thought that the actual answer is probably 6!

## Reference

1. Gardner, M. "Mathematical Games." *Scientific American*, 237,
18-28, Nov. 1977.