Hales-Jewett theorem

For every finite alphabet $X$ and every positive integer $k$, there is $n$ such that every $k$-coloring of $X^n$ contains a monochromatic combinatorial line.

Induct on the alphabet size $k$. For an $r$-colouring, choose an $(k-1,k)$-insensitive combinatorial subspace whose dimension forces a monochromatic combinatorial line over the first $k-1$ letters. The inductive Hales-Jewett theorem supplies that line. Changing all of its active parameters from $k-1$ to $k$, one at a time, preserves the colour by the alphabet insensitivity lemma. Thus the line extends to all $k$ letters. The one-letter alphabet is the base case.

For a finite coloring of $[m{]}^N$, a combinatorial subspace is $(a,b)$-insensitive if replacing $a$ by $b$, or conversely, in any of its variable coordinates leaves the color unchanged. For every number of colors, alphabet size $m\ge 2$, and dimension $d$, sufficiently large $N$ guarantees such a $d$-dimensional combinatorial subspace for any specified distinct letters $a,b$.

A proof uses the pigeonhole principle on chains $a^j{b}^{L-j}$ in consecutive coordinate blocks. Choose block lengths from left to right, making each long enough to pigeonhole the vector of colors for every earlier word and every later variable assignment. Process the blocks from right to left. Two equal color vectors give a nonempty variable interval insensitive to $a,b$. Insensitivity already obtained in later blocks survives all restrictions of earlier coordinates. This lemma proves the Hales-Jewett theorem by induction on alphabet size.

For r colours, k letters and d variable blocks, set $P_i={\sum }_{j<i}{L}_j$ and $L_i=r^{k^{P_i+d-i}}$. Process blocks from right to left. In block i, the $L_i+1$ words $a^t{b}^{L_i-t}$ have colour profiles indexed by all $k^{P_i}$ earlier words and $k^{d-i}$ later variable assignments. Two profiles agree, giving a nonempty variable interval insensitive to exchanging a and b. Previously obtained insensitivity holds for all earlier words and survives their restriction. This constructs the combinatorial subspace required by the alphabet insensitivity lemma.