Worlds of David Darling
Encyclopedia of Science
   
Home > Encyclopedia of Science

Graham's number





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 G1 = 3up-arrowup-arrow...up-arrowup-arrow3, where there are 3up-arrowup-arrowup-arrowup-arrow3 up-arrows. This, in itself, is a number far, far beyond anyone's ability to even remotely comprehend. Next, construct G2 = 3up-arrowup-arrow...up-arrowup-arrow3, where there are G1 up-arrows; then construct G3 = 3up-arrowup-arrow...up-arrowup-arrow3, where there are G2 up-arrows; then continue this pattern until the number G62 has been made. Graham's number G = 3up-arrowup-arrow...up-arrowup-arrow3, where there are G62 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.

Related category

   • NOTABLE NUMBERS