Graham's number

Graham's number, named after Ronald Graham, is a very large number which is often described as the largest number that has ever been seriously used in a mathematical proof. It is much too large to be written in scientific notation, and needs special notation to write down.

Graham's problem

Graham's number is connected to the following problem in the branch of mathematics known as Ramsey theory:

Consider an n-dimensional hypercube, and connect each pair of vertices to obtain a complete graph on <math>2^n<math> vertices. Then colour each of the edges of this graph using either one of two colours. What is the smallest value of n for which every possible such colouring must necessarily contain a single-coloured complete sub-graph with 4 vertices that lies in a plane?

Although the solution to this problem is not yet known, Graham's number is the smallest known upper bound.

In his 1989 book Penrose Tiles to Trapdoor Ciphers (ISBN 1234567890), Martin Gardner wrote "Ramsey-theory experts believe the actual Ramsey number for this problem is probably 6," making Graham's number perhaps the worst smallest-upper-bound ever discovered. More recently, Geoff Exoo of Indiana State University has shown (in 2003) that it must be at least 11 and provides experimental evidence suggesting that it is actually even larger.

Graham's number is said to be the largest number ever put to practical use. It is even bigger than Moser's number, which is another very large number.

Definition of Graham's number

Graham's number is the 65th in the following sequence, where each member is the number of Knuth arrows needed for the next member:

<math>4,\ 3\uparrow\uparrow\uparrow\uparrow3,\ 3\uparrow\cdots\uparrow3,\ 3\uparrow\cdots\uparrow3,\ \ldots<math>

Conway chained arrow notation doesn't help to express Graham's number G succinctly, but <math> 3\rightarrow 3\rightarrow 64\rightarrow 2 < G < 3\rightarrow 3\rightarrow 65\rightarrow 2 <math>.