= Alphabet insensitivity lemma
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\geq2$, 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.
Back to article page
