Hales Jewett Theorem

Question

In the book Ramsey Theory by Graham, Rothschild and Spencer the authors state:

The Hales Jewett Theorem strips van der Waerden's theorem of its unessential elements and reveals the heart of Ramsey theory. It provides a focal point from which many of the results can be derived and acts as a cornerstone of much of the more advanced work. Without this result Ramsey theory would more properly be called Ramseyian theorems.

I am interested in knowing as to what further advanced results flow from the Hales Jewett theorem and why is the theorem so crucial.

Thanks for your time.

Answer 1

The Hales-Jewett Theorem works in a context that is more abstract than that of the semi-group $\mathbb N$. This is what makes it more applicable than earlier theorems. This paper by Sabine Koppelberg points out some easy implications as well as a more general form of the Hales Jewett Theorem: [The Hales-Jewett theorem via retractions. Proceedings of the 18th Summer Conference on Topology and its Applications. Topology Proc. 28 (2004), no. 2, 595–601]

I think some of the developments around Hindman's theorem, speaking about semi-groups more abstract (i.e., with fewer relations) than $(\mathbb N,+)$, for example the finite subsets of $\omega$ with union, are motivated by the abstractness of Hales Jewett. Furstenberg and Katznelson used topological dynamics to prove a density version of the Hales Jewett Theorem. Blass gave a proof of the Hales Jewett Theorem using ultrafilters. The main result in Koppelberg's paper mentioned above is also proved using algebra in the Stone-Czech compactification of a semi-group. Here the Hales Jewett Theorem and variants seem to be interesting test questions for a method of proof.

---

Edit: It just occurred to me that a combinatorial proof of the density Hales Jewett Theorem was the outcome of a massive collaboration called the "Polymath Project" initiated by Timothy Gowers. The abstract of the corresponding paper, which can be found here, says "The Hales-Jewett theorem has a density version as well, proved by Furstenberg and Katznelson in 1991 by means of a significant extension of the ergodic techniques that had been pioneered by Furstenberg in his proof of Szemeredi's theorem". The "significant extension of the ergodic techniques" and the fact that no combinatorial proof was known before the 2009 Polymath paper indicates some of the subtleties of Hales Jewett.

Answer 2

A simple application of the Hales-Jewett theorem give the following result: if $r$, $k$ are natural numbers, then there is a finite set $S$ of natural numbers which does not contain a $(k+1)$-AP, yet every coloring with $r$ colors gives a monochromatic $k$-AP.

Let $N$ be sufficiently large. The HJ theorem says that if we color all sequences of length $N$, consisting of numbers between 0 and $k-1$, with $r$ colors, there is a monocolored combinatorial line, that is, a configuration of the form $f_0,\dots,f_{k-1}$, such that for a nonempty subset $T\subseteq \{0,\dots,N-1\}$ $f_i$ is $i$ in $T$, and the same outside it. Now the set $S$ above consists of the sums $x_0+x_1M+x_2M^2+\cdots+x_{N-1}M^{N-1}$, ($0\leq x_j\leq k-1$), where $M$ is very large. That is, we map the HJ-hypercube via the mapping $(x_0,x_1,\dots,x_{N-1})\mapsto x_0+x_1M+x_2M^2+\cdots+x_{N-1}M^{N-1}$. If $M$ is large enough, then no linear combination with small ($\lt k$) coefficients that gives 0, unless the same linear combination gives 0 in the left hand side, i.e., in the hypercube, in which there is no $(k+1)$-AP.

Answer 3

Here is an example of an easy corollary of the Hales-Jewett theorem:

Theorem: For every finite topological space $X$ and $r \in \mathbb{N}$, there is a finite topological space $Y$ such that if $Y$ is $r$-colored, then we can find a monochromatic copy of $X$.

Proof: Using the Hales-Jewett theorem, pick $n$ large enough so that any $r$-coloring of $X^n$ provides a monochromatic combinatorial line. Then set $Y = X^n$ (with the usual product topology), and observe that every combinatorial line in $X^n$ is homeomorphic to $X$.

This type of result fits into the area called induced Ramsey theory. The Hales-Jewett theorem gives us many such results: the same proof works for finite metric spaces (use the sup metric on the product), graphs (use the strong product), digraphs (use a suitable generalization of the strong product), and more. It works for finite groups too, provided you are willing to weaken the conclusion a bit:

Theorem: For every finite group $G$ and $r \in \mathbb{N}$, there is a finite group $H$ such that if $H$ is $r$-colored, then we can find a subgroup $G'$ of $H$ isomorphic to $G$ and an element $h \in H$ such that $hG$ is monochromatic.

Proof: Essentially the same: just observe that in $G^n$, combinatorial lines are shifted copies of $G$.

Of course, many results from induced Ramsey theory involve coloring not points, but pairs of points, triples of points, etc. These kinds of results do not seem to follow easily from the Hales-Jewett theorem.

In addition to these kinds of results, the Hales-Jewett theorem is used in the proof of the Graham-Leeb-Rothschild theorem, the edge-induced graph theorem, and its bipartite version (these are in sections 2.4, 5.2, and 5.3 of the Graham-Rothschild-Spencer book). It also gives quick proofs for van der Waerden's theorem and its higher-dimensional analogue, Gallai's theorem. See also Exercise 15 of this blog post of Terry Tao for further examples of what you can do using the Hales Jewett theorem.