MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am currently reading the recent preprint of Dodos, Kanellopoulos, Tyros, where the ambitiously short proof of Density Hales Jewett theorem is provided. The important ingredient is Graham-Rothschild theorem. The authors say that it follows from the HJ by some standard Ramsey arguments, but I can not find them myself, at least immediately. Is it written anywhere? Original paper of Graham and Rothschild looks too long for being used in "simple self-contained proof" of anything. Polymath's DHJ proof does not use GR at all, on first glance.

share|cite|improve this question
@Kristal, it is exactly the paper I mean. Now I asked its authors directly and got a satisfactory answer with references. – Fedor Petrov Oct 29 '12 at 12:36
Fedor: Could you share the answer you got? I am struggling with the same exact problem. – Joel Moreira Feb 15 '13 at 20:14
"The coloring result we use is indeed a special case of the Graham-Rothchild theorem. We do not say much about it in the paper, since this staff is considered to be part of the folklore. In any case,here are some references. 1) A simple and self-contained proof of the full Graham-Rothchild theorem can be found in: H. J. Promel and B. Voigt, Graham-Rothschild parameter sets, "Mathematics of Ramsey Theory", Springer-Verlag, Berlin (1990), 113-149.See in particular, Section 4, page 128. 2) Another excellent reference is: R. McCutcheon, Elemental Methods in Ergodic Ramsey Theory, Lect" – Fedor Petrov Feb 22 '13 at 21:33

In Randall - McCutcheon's book "Elemental methods in ergodic Ramsey theory" a stronger version of GR's theorem is prooved about block subspaces (theorem 2.4.1). The only theorems you need in order to proove it is Hales-Jewett and Folkman's theorem (about finite unions which you can proove using Hales - Jewett theorem again).

Another proof is given in Graham - Rothschild -Spencer book about Ramsey theory using HJ and linear algebra.

share|cite|improve this answer
Thanks! Probably, linear algebra is used for linear algebraic version of Graham-Rothschild, while we need a combinatorial one? – Fedor Petrov Oct 15 '12 at 5:59
You're wright. If you want a proof for the combinatorial version of the thorem it is the one a mentioned in the first place. – T.Karageorgos Oct 15 '12 at 15:45

Your Answer


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.