 |
| Home > Combinatorics > Ramsey theory |
Graham's number
There is a problem in Ramsey theory which Ronald Graham was studying.
He managed to solve it, but only by giving an enormous upper bound. This
is a number so mind-bogglingly vast that it even got an entry in the Guinness
Book of World Records for the largest number ever used in a serious mathematical
paper. The problem requires a lot of explanation.
First, consider a hypercube of arbitrarily many dimensions. This must be explained. To get a hypercube of 4 dimensions, consider a cube being "pulled" along a 4th dimension to get another cube. Trace out the path to get a 4-D cube. This is very hard to visualise at first, but an analogy makes it much easier. Consider a square lying flat on a plane. Pull it upwards (perpendicular to the plane) to a parallel plane. If you trace out the path, you should get a cube.
The next step is this: For each pair of vertices, join them with a line. Colour that line red or blue arbitrarily. The question is how many dimensions are required such that there are always four points such that every line between four points is the same colour and the four points are on the same plane. Some lower dimensions can be ruled out instantly: with 4 dimensions, there are 16 points. However, you need 18 points to force four points to have only lines of one colour between them, regardless of whether points are in the same plane or not. Thus the solution is greater than 4. In fact, Graham proved the solution was at least 6. The current lower bound is 13. In my personal opinion, it is probably less than 20, but that has not been proved.
To fully explain Graham's upper bound, up-arrow notation is needed. Essentially, ^ is exponentiation. ^^ is repeated exponentiation or tetration. ^^^ is repeated tetration or pentation, and so on. Each additional arrow results in a truly massive increase in the power of the operation. Call 3^^^^3 G1. This is mind-blowingly huge. The next step G2 is 3^^^...^^^3 with G1 3s. Then G3 is 3^^^...^^^3 with G2 3s. Graham's number is G64. This is incredible. However, it also shows how hard it is to place bounds on problems in Ramsey theory. The bound has currently been reduced to under 9^^^4. This is almost certainly a massive overestimate, especially as the lower bound is currently 13.
The last few digits of Graham's Number are known to be ...2464195387. This is as Graham's Number is simply an enormous power tower of 3s. However, it is so big that we will never know how many digits it has or even the first digit. It is simply too big to fit in the observable universe.