Hales-Jewett Theorem

The Hales-Jewett theorem is one of the deepest results in Ramsey theory. It implies many other Ramsey-type results, including van der Waerden's theorem, and operates in the purely combinatorial setting of combinatorial cubes without reference to arithmetic structure.

Statement

Theorem5.3Hales-Jewett Theorem

For all positive integers $k$ and $r$ , there exists a positive integer $\mathrm{HJ}(k, r)$ such that for every $n \geq \mathrm{HJ}(k, r)$ , every $r$ -coloring of $[k]^n$ contains a monochromatic combinatorial line.

Recall that a combinatorial line in $[k]^n$ is a set $\{w(0), w(1), \ldots, w(k-1)\}$ where $w$ is a word with at least one "wildcard" coordinate that ranges over all of $[k]$ .

Connection to Van der Waerden's Theorem

Theorem5.4Van der Waerden's Theorem (Corollary)

For all positive integers $k$ and $r$ , there exists $W(k, r)$ such that every $r$ -coloring of $[W(k, r)]$ contains a monochromatic arithmetic progression of length $k$ .

Proof

Van der Waerden follows from Hales-Jewett. Define a map $\phi: [k]^n \to \mathbb{N}$ by $\phi(x_1, \ldots, x_n) = x_1 + x_2 + \cdots + x_n$ . The image of a combinatorial line under $\phi$ is an arithmetic progression of length $k$ in $\{0, 1, \ldots, (k-1)n\}$ . Given an $r$ -coloring of $[N]$ where $N = (k-1) \cdot \mathrm{HJ}(k, r) + 1$ , we can define a coloring of $[k]^{\mathrm{HJ}(k,r)}$ by coloring each word by the color of its image under $\phi$ . The monochromatic combinatorial line guaranteed by Hales-Jewett maps to a monochromatic arithmetic progression. $\square$

■

Density Version

Definition5.5Density Hales-Jewett

The Density Hales-Jewett theorem (proved by Furstenberg-Katznelson in 1991 using ergodic theory, and combinatorially by the Polymath project in 2012) states: for every $\delta > 0$ and integer $k \geq 2$ , there exists $N$ such that every subset $A \subseteq [k]^N$ with $|A| \geq \delta k^N$ contains a combinatorial line.

ExampleDeriving Szemerédi's Theorem

Just as the Hales-Jewett theorem implies van der Waerden's theorem, the density Hales-Jewett theorem implies Szemerédi's theorem: every subset of the integers with positive upper density contains arbitrarily long arithmetic progressions.

RemarkBounds on HJ Numbers

The Hales-Jewett numbers $\mathrm{HJ}(k, r)$ grow extremely rapidly. Even $\mathrm{HJ}(2, r) = R(3, 3, \ldots, 3)$ (with $r$ colors) has tower-type behavior. The Shelah proof (1988) gave primitive recursive bounds, a major improvement over the original Hales-Jewett proof which used no explicit bound.