Maths Bite: Graham’s Number

Graham’s number, named after Ronald Graham, is a large number that is the upper bound (just like Skewes’ Number) on the solution to a problem in Ramsey theory.

Expressing Graham’s Number

As Graham’s number is so large, it can’t be expressed using the conventional notation of powers, and powers of powers.

\left.
 \begin{matrix}
  G &=&3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots\cdots \uparrow}3 \\
    & &3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots \uparrow}3 \\
    & &\underbrace{\qquad\;\; \vdots \qquad\;\;} \\
    & &3\underbrace{\uparrow \uparrow \cdots\cdot\cdot \uparrow}3 \\
    & &3\uparrow \uparrow \uparrow \uparrow3
 \end{matrix}
\right \} \text{64 layers}

Source: Wikipedia

Grahams number is defined using Knuth’s up-arrow notation, introduced by Donal Knuth in 1976. The number of arrows in each layer, starting from the top layer, is specified by the value of the next layer below it. In cleaner notation:

G = g_{64},\text{ where }g_1=3\uparrow\uparrow\uparrow\uparrow 3,\  g_n = 3\uparrow^{g_{n-1}}3,

Equivalently,

G = f^{64}(4),\text{ where }f(n) = 3 \uparrow^n 3,

Not only does Graham’s number have an incomprehensibly large magnitude, it is also useful to mathematicians, and that is what makes this number so well known.

Ramsey Theory and Context

Ramsey theory is an area in mathematics which studies conditions under which order will appear. Graham’s number is concerned with the following problem in Ramsey theory:

“Connect each pair of geometric vertices of an n-dimensional hypercube to obtain a complete graph on 2n vertices. Colour each of the edges of this graph either red or blue. What is the smallest value of n for which every such colouring contains at least one single-coloured complete subgraph on four coplanar vertices?”


Terminology:

Hypercube – a generalisation of a 3-cube to n dimensions.

Complete Graph – a graph in which each pair of graph vertices is connected by an edge

CompleteGraphs

Source: Wolfram Math World


 

An answer – N* – was proved to exist by Graham and Rothschild in 1971. The weak upper bound for N* is given by Graham’s number, and was found in Graham’s unpublished work, eventually being published and named by Martin Gardner in Scientific American in November 1977.

Sources: 1 | 2

Hope you enjoyed the second instalment of ‘Maths Bite’. M x

Advertisements

One comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s