Graham's number

Graham's number ( by Ronald L. Graham) is a special natural number. It is an upper limit to a problem of Ramsey Theory.

According to the Guinness Book of Records, it is the largest ever used in a mathematical proof number. In the meantime, however, were in some serious mathematical proofs still much larger numbers before, for example in connection with Kruskal's tree theorem.

Graham's problem

In an n-dimensional hypercube ( unit cube in n-dimensional Euclidean space ) all the vertices are (node ​​) each connected in pairs by a line (edge ​​), so that a complete graph is created on nodes with edges.

These edges are then stained with one of two colors. The question then is whether there is a complete subgraph of four, lying in a plane of Euclidean space node whose six edges all have the same color.

In low dimensions, there are edge-colorings, where this is not true. In the overall graph consists of only one level with four nodes. Colors to varying degrees of colors, so the only subgraph, namely the total graph itself, not from the six edges of the same color. Is there other hand, a dimension in which for each possible edge coloring of the hypercube a subgraph with these properties exist, then this also applies to any higher dimension, as the hypercube a higher dimension contains a hypercube of dimension subgraph in which the subgraph with six same color edges can be found.

Hence the real problem: how big is this, with the potential for all for each edge coloring exists such a subgraph, while there is an edge coloring for all that prevents this?

The problem is not yet solved. Graham and Rothschild 1971 have shown that there is such a value, and that is. The number is defined in the next chapter. The mathematician Geoffrey Exoo from Indiana State University in 2003 showed that it is still in the dimension is an edge coloring that does not allow planar subgraph with six equally colored edges. The best known estimate is that.

Based on unpublished material by Graham, from which a proof of the weaker (larger) results in upper bound, Martin Gardner described the number as " Graham's number".

Definition

Graham's number, and also the much smaller, are so extremely high that not even aids such as the hyper- exponentiation operator are sufficient to specify these numbers directly. The definition of the number is possible, but a sequence which can be represented, for example, with Knuth arrow notation. For natural numbers are defined:

In the first row in this case, the usual power is explained. Note that the arrow operator is not associative. The staple- free expression is listed - so the convention - work through from right to left. Thus is. This sequence is that in which the final results are most produced.

In addition, we defined. Instead of the symbol ^ is used.

With this notation, one can define the consequences and by the following rules recursively:

From the first episode is Graham's number, and from the second is the best known upper bound for.

In other words:

To better illustrate how extremely tall is Graham's number, the first steps for calculating shown:

Already can not be more reasonable in the usual exponential () or as a power tower to express. For this purpose, a power tower with 7,625,597,484,986 exponent would already be necessary. Nevertheless, one can determine the last digits of Graham's number with elementary number theory. The last 15 digits are 627,262,464,195,387. Himself had then about 343,000,000,000,000,000,000,000,000,000,000,000,000 exponent.