1

I had a few questions regarding Graham's number and Ramsey theory. I understand what Graham's number is and what it is attempting to solve. My question is, is a hypercube with dimension equal to Graham's number a mathematical necessity? In other words, can the problem proposed to Graham actually have a lower bound, and if it can, does that mean our hypothetical Graham-Dimensional hypercube gets thrown away into the mathematical dustbin as if it never existed?

Another question. Graham's problem was aimed at solving a problem involving just 4 points on a plane. Could the question be rephrased such that we're looking at more points -- thereby increasing the difficulty? Moreover, could one pose a question involving more colors -- say, the addition of green or yellow? And also, could one pose a question involving, say, 8 points that lie in 3D space (a cube) as opposed to just four points that lie in 2D space. All that is to say, can we pose a question such that there MUST exist a hypercube with dimension = Graham's number (or above)?

Alex
  • 31
  • While I think both questions on their own are sensible, I think it might be better if you split the second one off as its own question: "What are some interesting generalizations of Graham's problem?" – Semiclassical Sep 21 '14 at 01:51

1 Answers1

0

Graham's number $G$ is an upper bound on some quantity $n$ which is the minimal dimension of a hypercube such that every 2-coloring of which induces some monochromatic complete graph on four coplanar vertices. In fact, it is known (according to the Wikipedia page) that $n < G$. The problem has a lower bound: by definition, if you take a hypercube of dimension less than $n$ then there will be some 2-coloring without any monochromatic complete graph on four coplanar vertices. In Ramsey theory lower bounds are often harder to obtain than upper bounds, and I don't know if any non-trivial lower bound exists in this case.

The problem can be generalized in many ways, for example by increasing the number of colors or the size of the monochromatic graph, and the corresponding quantity $n$ will naturally increase, without bound. Choosing the parameters large enough, we will have $n>G$. In fact, there is a trivial choice which guarantees $n>G$: for example, if the number of colors is $2^G$, then necessarily $n > G$ (why?).

In Ramsey theory we are often interested in the rate of growth of a quantity like $n$ in terms of another parameter such as the number of colors. Even for the simplest case, the Ramsey numbers, the asymptotic rate of growth in terms of the size of the monochromatic clique is not known.

Yuval Filmus
  • 57,157
  • this helps me very much. So a hypercube with dimension Graham's number (i'm assuming your "G" is what that means) or greater, is a mathematical inevibility? – Alex Sep 21 '14 at 01:40
  • Yes, if the parameters are large enough, you will need dimension $G$, or any other dimension you have in mind. – Yuval Filmus Sep 21 '14 at 01:42
  • awesome. Thank you very much. I learned that the popular notion of Graham's number (G_64) was Ron Graham's simplifying the actual number in his proof to Martin Gardner. This made me sad, but after what you've told me, I am no longer sad :) – Alex Sep 21 '14 at 01:44
  • also, could you postulate on the notion of asking Graham's question, but instead of a 4 point coplanar culprit, we're talking about an 8 point 3D cube? is that a viable question to ask in Ramsey theory? I'm comforted to know about the many different colors outcome, but I'm also curious about my 3D cube hypothesis. And of course, one could postulate a 4D or 5D cube with the same restraints – Alex Sep 21 '14 at 01:48
  • You can ask whatever question you want. It's a free world. – Yuval Filmus Sep 21 '14 at 01:49