Graham's Number Website Links For
Number 		 

Information About

Graham's Number
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...




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 2^n Vertices . Then colour each of the edges of this graph using only the colours red and black. 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 for it. This bound was found by Graham and B. L. Rothschild (see (GR) , corollary 12). They also provided the Lower Bound 6, adding the qualified understatement: "Clearly, there is some room for improvement here."

In '' Penrose Tiles To Trapdoor Ciphers '', 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 provided evidence that it is larger.


DEFINITION OF GRAHAM'S NUMBER


Using Knuth's Up-arrow Notation , Graham's number G is defined as


G = \left . \begin{matrix} 3 \underbrace{ \uparrow \ldots \uparrow } 3 \ \underbrace{ dots } \ 3 \uparrow\uparrow\uparrow\uparrow 3 \end{matrix} ight \} 64


Equivalently,

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

or

:G = f^{64}(4) where f(n) = ext{hyper}(3,n+2,3) and hyper() is the Hyper Operator .

Graham's number ''G'' itself cannot succinctly be expressed in Conway Chained Arrow Notation , but 3 ightarrow 3 ightarrow 64 ightarrow 2 < G < 3 ightarrow 3 ightarrow 65 ightarrow 2 , see Bounds On Graham's Number In Terms Of Conway Chained Arrow Notation .


Magnitude of Graham's number


Since appreciation of the true size of Graham's number can be difficult, it can be helpful to express the first term of the sequence in terms of exponentiation:

:
g_1
= 3 \uparrow \uparrow \uparrow \uparrow 3
= 3 \uparrow \uparrow \uparrow (3 \uparrow \uparrow \uparrow 3)
= 3 \uparrow \uparrow \uparrow
\left(
\begin{matrix}
\underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}} & \ \
3^{3^3} & ext{threes}
\end{matrix}
ight)
= \left.
\begin{matrix}
\underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}} & \ \
\underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}} & ext{threes} \
dots & dots \
\underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}} & ext{threes} \
3^{3^3} & ext{threes} \
\end{matrix}
ight \}
\begin{matrix}
\ & \ \
\underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}} & \mbox{ layers} \
3^{3^3} & ext{ threes}
\end{matrix}


Note that the arrows are ; e.g., 3 \uparrow 3 \uparrow 3 = 3 \uparrow (3 \uparrow 3) = 3 \uparrow 27 = 7,625,597,484,987.

This first term, ''g''1, is already inconceivably greater than the number of atoms in the observable universe, and grows at an enormous rate as it is iterated through the sequence ''g''.


SEE ALSO



REFERENCES



EXTERNAL LINKS