Combinatorial line

Let $X$ be a finite alphabet. A combinatorial line in $X^n$ is obtained by fixing some coordinates and replacing every coordinate in one nonempty active set by the same variable letter. It therefore contains one word for each letter of $X$.

For any proposed positive active size $d$, the displayed two-colour finite colouring of binary words gives opposite colours to the two points of every combinatorial line with exactly $d$ active coordinates. Their counts of the letter $2$ differ by $d$. Thus no dimension can guarantee a monochromatic line of one universally prescribed active size, even though the Hales-Jewett theorem guarantees some active size. The colouring is allowed to depend on $d$ because $d$ is chosen before the colouring.

For any $N\ge 1$, color $w\in [3{]}^N$ by its first letter together with its number of runs of a word modulo $3$. This finite coloring uses at most nine colors and has no monochromatic combinatorial line whose active coordinates form an interval. An active interval starting at the first coordinate changes the first letter. Otherwise, its left boundary and optional right boundary contribute $0$ versus $1$, $0$ versus $2$, or $1$ versus $2$ to the run count as the active letter varies. These differences remain nonzero modulo $3$. The first-letter component is essential for intervals that occupy the entire word.

Repeat every coordinate of a word $q$ times. A combinatorial line maps to a combinatorial line whose active-set size is multiplied by $q$. Pulling back a finite coloring along this map and using the Hales-Jewett theorem forces monochromatic lines with active-set size divisible by any prescribed positive integer $q$.

For a fixed alphabet size $m>1$, a family $\mathcal{F}\subseteq \mathcal{P}([n])$ is adequate if every two-color finite coloring of $[m{]}^n$ has a monochromatic combinatorial line whose nonempty active coordinate set belongs to $\mathcal{F}$.

An intersecting family is never adequate. Color a word red when the coordinates carrying letter $1$ contain a member of $\mathcal{F}$, and blue otherwise. For a line with active set $A\in \mathcal{F}$, its letter-$1$ word is red and its letter-$2$ word is blue, because no member of an intersecting family can lie wholly outside $A$.

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.

A $d$-dimensional combinatorial subspace, also called a $d$-parameter set, has $d$ pairwise disjoint nonempty active coordinate sets. Coordinates in the $j$th active set all receive one freely chosen alphabet letter, independently for each $j$, while the remaining coordinates stay fixed.

For every alphabet size $m$, number of colors $k$, and dimension $d$, some $n$ has the property that every $k$-coloring of $[m{]}^n$ contains a monochromatic $d$-dimensional combinatorial subspace. It follows from the Hales-Jewett theorem by identifying $[m{]}^{dN}$ with the word space over the alphabet $[m{]}^d$.