What exactly is the function of Graham’s Number? What was R. L. Graham proving?
Well, it’s used in a very difficult and relatively new region of combinatorial mathematics known as Ramsey Theory. There’s a mathematical problem in Ramsey Theory, a fairly difficult one to explain and an extremely difficult one to solve. But here’s the explanation anyway.
Before you can understand the question, you need to understand a bit of Ramsey Theory. Firstly, let’s find out what a complete graph is. A complete graph order N (which is written KN) consists of N points, all of them joined to all the others. For example, K1 is just one lone point all on its own. K2 is two points, joined by a line. K3 is three points joined to make a triangle. K4 is a four points joined to make a square, with a cross in the middle to join the diagonally opposite points. K5 is a pentagon with a five-pointed star inscribed in it. you know what I'm talking about. A pentagram.
Now, imagine taking two pens, say, red or blue, and randomly colouring all the lines. Sure, you get a pretty pattern, but if you look at the pattern, there might be smaller patterns. For instance, you might find three points which are all joined by red lines to make a red triangle. That’s a red K3! Now, you understand that if you colour the lines randomly, you might not get a triangle. That’s true. However, if you make the complete graph big enough, and then colour all the lines, then even if you colour them randomly, you are guaranteed to get either a red or a blue triangle. All you need is a big enough graph.
How big is big enough?
Good question.
Now, there are variations on this question. Suppose, for instance, that you use three colours instead of two. Or suppose you wanted to find not a triangle, but a square? Or a snake of eight lines?
As long as the complete graph is big enough, you will find that you get all of these things, no matter how randomly you colour them. But finding out “how big is big enough” is very difficult mathematically speaking as the numbers get insanely huge. As big as Graham’s Number, in fact.
So here’s the ultra-tough question that Graham was trying to solve.
“Two-colour the diagonals of an N-dimensional hypercube. What is the smallest N such that there must exist a K4 of one colour whose vertices are coplanar?"
Don’t waste time trying to crack it yourself... you’ll fail. Honest.
The answer to this question is yet to be found, but the man studying it, R. L. Graham, did the next best thing and came up with an upper limit. That upper limit is Graham’s Number.
According to the most recent set of studies, the solution for N is probably 6.
Now there’s a nice number that the human mind can comprehend without melting. That’s nearly all from me, folks, I just want to round it off by saying that I hope that, when you go home and see your miserable little millions, billions, and googolplexes, you laugh, think of Graham’s Number, and realise that infinity is much, much bigger than most people imagine. Thank you, and goodnight.
A correction to Seqram's writings.
(Brackets are a total pain at this point, so please know that stuff like 3^4^5^2 should be taken to mean 3^(4^(5^2)) and NOT ((3^4)^5)^2. Just warning you.)
3^^1 = 3
3^^2 = 3^3
3^^3 = 3^3^3
3^^4 = 3^3^3^3 etc.
Therefore
3^^^3 = 3^^3^^3 = 3^^7,625,597,484,987 which is NOT 3^(7,625,597,484,987^7,625,597,484,987), but actually,
= 3^3^3^3^...^3^3
where there are 7,625,597,484,987 threes in the sequence. This sequence is called a power tower, and is pronounced "A power tower of seven trillion, six hundred and twenty-five billion, five hundred and ninety-seven million, four hundred and eighty-four thousand, nine hundred and eighty-seven threes". If you wrote it out, you’d have a 3, then another three just above it and to the right, then another one… until you had 7,625,597,484,987 threes in the tower. That, alone, would take even a machine a couple of years to do.
3^^^3 is already a monumentally big number. This number has no real-world equivalent at all. We left them all behind a long time ago. It’s impossible for a human mind to conceive of this number, though its construction (you know, the power tower) is just conceivable. Plus it can be (technically) be written out in a proper mathematical form. Where was I?
3^^^^3
Now this is a seriously big number, very, very much larger than 3^^^3 or indeed any other number you probably know about. If it wasn't a single step in the construction of Graham's Number then I wouldn't be surprised to find it was the largest number in the world.
3^^^^3
= 3^^^3^^^3
= 3^^^(a power tower of 7,625,597,484,987 threes)
= 3^^3^^...^^3^^3^^3^^3 where there are 7,625,597,484,987 threes in the list.
= 3^^3^^...^^3^^3^^7,625,597,484,987
= 3^^3^^...^^3^^(a power tower of 7,625,597,484,987 threes)
... If you keep expanding it you get
A power tower of (a power tower of (a power tower of… (a power tower of 7,625,597,484,987 threes) … threes) threes) threes
where there are 7,625,597,484,987 power towers. See arrow notation.
The remainder of the construction is as Seqram said.
Thanks to krimson for setting me straight on some of this.