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.

Table of contents

1 Graham's problem 2 Definition of Graham's number 3 Miscellaneous 4 External link

Graham's problem

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

Consider a complete graph with 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?

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

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:

Conway chained arrow notation doesn't help to express Graham's number G succinctly, but:
3→3→64→2 < G < 3→3→65→2

Miscellaneous

The writer on recreational mathematics Martin Gardner wrote in his 1989 book Penrose Tiles to Trapdoor Ciphers (page 244), "Ramsey-theory experts believe the actual Ramsey number for this problem is probably 6." However, more recently, Geoff Exoo of Indiana State University has shown (2003) that it must be at least 11 and provides experimental evidence suggesting that it is actually even larger.

Graham's number is even bigger than Moser's number, which is another very large number.

External link

• "A Ramsey Problem on Hypercubes" by Geoff Exoo