Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can someone give me an idea of how R.Graham reached Graham's Number as an upper bound on the solution of the related problem ? Thanks !

share|improve this question
3  
Because it was what he needed for his proof to work? Is there something more than that which you wanted? –  Thomas Andrews Jun 26 '12 at 18:25
1  
I would think the way to answer this question would be to read Graham's paper. Have you tried this? –  Gerry Myerson Jun 27 '12 at 1:09
1  
I guess nobody knows: mathoverflow.net/questions/117006/… –  Andres Caicedo Jan 3 '13 at 6:54
    
John Baez has posted an update on the link above. –  Andres Caicedo Jan 11 '13 at 17:37

1 Answer 1

up vote 17 down vote accepted

This post appears long and frightening, but I hope you will not be put off, because the topic is not actually hard to understand. It is long because I explained a lot of things from first principles. I did this because I thought the answer would be of interest to a general audience and because the branch of mathematics is not that well-known. So there is a lot of explanation, but not much is difficult.


First, a disclaimer. Graham's Number is usually cited as the largest number ever to appear in a mathematical proof. There is no evidence for this, and in fact the claim is false on its face, because Graham's Number does not actually appear in the proof that it is claimed to appear in. (It can't be the largest number ever to appear in a mathematical proof if it doesn't actually appear in a mathematical proof.) According to these posts by John Baez [1] [2]:

I asked Graham. And the answer was interesting. He said he made up Graham's number when talking to Martin Gardner! Why? Because it was simpler to explain than his actual upper bound - and bigger, so it's still an upper bound!

Martin Gardner then wrote about the number that Graham described, which is not the number from the proof, and the rest is history.

Now what is the number from the proof? Here there is some interesting mathematics.


The question addressed by Graham's Number belongs to the branch of mathematics known as Ramsey theory, which is not at all hard to understand. It can roughly be described as the study of whether a sufficiently large structure, chopped into pieces, must still contain smaller structures. This is a rather vague explanation, so I will give two of the canonical examples.

  1. Ramsey's theorem. Let $n$ and $k$ be given. Then there exists a number $R(n;k)$ such that, if you take a complete graph of at least $R(n;k)$ vertices, and color its edges in $k$ different colors, then there must be a complete subgraph of $n$ vertices whose edges are all the same color.

    A frequently-cited special case of this theorem says that $R(3;2) = 6$: if you have a party with at least 6 guests, then there must be 3 guests who have all met one another before, or 3 people who have never met; it is impossible that every subset of three guests has both a pair of people who have met and a pair of people who have not. (With only five guests, this is possible.) Here the two “colors” are “have met before” and “have not met before”.

  2. Van der Waerden's theorem. Let $n$ and $k$ be given. Then there exists a number $W(n;k)$ such that, if you take an arithmetic progression of length $W(n;k)$, and color its elements in $k$ different colors, it must contain an arithmetic progression of $n$ elements that are all the same color.

In both these examples you can see the general pattern: we have some large structure (a graph of $R(n;k)$ vertices in one case, an arithmetic progression of $W(n;k)$ elements in the other) and we divide the structure into $k$ parts and ask if one of the parts still contains a sub-structure of size $n$.

The proofs of these theorems are constructive. For example, the proof of van der Waerden's theorem allows one to calculate that for $n=3, k=2$, $W(3;2) = 325$ suffices: if you color the integers $\{1, \ldots, 325\}$ with two colors, then there must be a 3-term arithmetic progression whose elements are all one color.

The $\{1, \ldots, 325\}$ is rather silly, because in fact the same is true of $\{1, \ldots, 9\}$, as is easily shown. So the proof gives an upper bound of $325$ when the correct answer is $9$. This is typical of theorems in Ramsey theorem: the proof tells you that the number exists and is at most some large number, but then closer investigation reveals that it is really some considerably smaller number. The corresponding overestimate for $W(3;3)$ is that the proof tells you that $$W(3;3) \le 7\cdot\left(2\cdot3^7+1\right)\left(2\cdot3^{\left(2\cdot3^7+1\right)}+1\right),$$

a number with $2095$ digits, but exhaustive computer search quickly reveals that actually $W(3;3)=27$.

The reason for these rapidly-growing bounds is that typically the proofs proceed by induction, and one shows that if there are sufficiently many size-$n-1$ structures, then two of them must have their subcomponents colored exactly the same, and this allows one to find sub-parts of those size-$n-1$ structures that work together to form a size-$n$ structure of all one color. But a size-$n-1$ structure with $S(n-1)$ subcomponents will have something like $k^{S(n-1)}$ ways its components can be colored, so “sufficiently many” means something like $k^{S(n-1)}$, and the number required looks something like an exponential tower of $k$'s of height $n$. When the structures one is forming are more complicated, then instead of needing only two size-$n-1$ structures colored the same, one might need an increasingly large number of such structures, and so perhaps you can imagine how the number required increases even faster than an exponential tower.

(That was the crucial paragraph that really answers your question, so I apologize for being so vague; please let me know if you want me to elaborate or provide a specific example.)

Enormous numbers are quite commonplace in Ramsey theory, and so the Graham's Number might have some competition even in its own field.


The particular problem discussed in the Graham's Number paper, “Ramsey's theorem for $n$-parameter sets” is rather general, but the enormous number (not the one described by Gardner) is an upper bound for a problem very similar to the ones I described above:

We recall that by definition $N(1, 2, 2)$ is an integer such that if $n\ge N(1, 2, 2)$ and the $\binom{2n}{2}$ straight line segments joining all possible pairs of vertices of a unit $n$-cube are arbitrarily 2-colored, then there always exists a set of four coplanar vertices which determines six line segments of the same color.

That is, Graham and Rothschild are investigating a problem that, in this special case, involves taking a certain $n$-dimensional object, coloring its 1-dimensional subobjects with 2 colors, and looking for a single-colored 2-dimensional subobject; $N(1,2,2)$ is the smallest number of dimensions that such an object must have in order to guarantee a single-colored 2-dimensional subobject.

Let $N^*$ denote the least possible value $N(1,2,2)$ can assume. We introduce a calibration function $F(m,n)$ with which me may compare our estimate of $N^*$. This is defined recursively as follows: $$\begin{align} F(1,n)=2^n \qquad F(m,2)=4 &\qquad m\ge 1, n\ge 2, \\ F(m,n) = F(m-1, F(m,n-1)) & \qquad m\ge2, n\ge 3. \end{align} $$ It is recommended that the reader calculate a few small values of $F$ to get a feeling for its rate of growth, e.g. $F(5,5)$ or $F(10,3)$.

Finally, the bound:

The best estimate we obtain this way is roughly $$N^* \le F(F(F(F(F(F(F(12,3),3),3),3),3),3),3).$$

The authors continue with an understatement that I imagine made them chuckle:

On the other hand, it is known only that $N^*\ge 6$. Clearly, there is some room for improvement here.

A remark a little later says

in fact, the exact bound is probably $<10$.

but Sbiis Saibian's excellent discussion of this claims, unfortunately without citation:

It was recently proved that the solution could not be smaller than $11$.

I will be glad to elaborate on any part of this that is not clear.

share|improve this answer
    
Unbelievable answer. Thank you so much for the effort :) I think that your answer could not be better. Thank you again :) –  thetruth Dec 8 at 18:39
    
I'm glad I could help. –  MJD Dec 8 at 18:43
    
"There is room for improvement here" reminds me of Whitehead and Russell's "The above proposition is occasionally useful", referring to $1+1=2$. –  KSmarts Dec 17 at 22:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.