6
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ arxiv.org/pdf/1209.4986.pdf $\endgroup$ Oct 27, 2012 at 7:35
  • $\begingroup$ @Kristal, it is exactly the paper I mean. Now I asked its authors directly and got a satisfactory answer with references. $\endgroup$ Oct 29, 2012 at 12:36
  • 2
    $\begingroup$ Fedor: Could you share the answer you got? I am struggling with the same exact problem. $\endgroup$ Feb 15, 2013 at 20:14
  • $\begingroup$ "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" $\endgroup$ Feb 22, 2013 at 21:33

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks! Probably, linear algebra is used for linear algebraic version of Graham-Rothschild, while we need a combinatorial one? $\endgroup$ Oct 15, 2012 at 5:59
  • $\begingroup$ 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. $\endgroup$ Oct 15, 2012 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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