Main Page
The Problem
Let [math]\displaystyle{ [3]^n }[/math] be the set of all length [math]\displaystyle{ n }[/math] strings over the alphabet [math]\displaystyle{ 1, 2, 3 }[/math]. A combinatorial line is a set of three points in [math]\displaystyle{ [3]^n }[/math], formed by taking a string with one or more wildcards in it, e.g., [math]\displaystyle{ 112*1**3\ldots }[/math], and replacing those wildcards by [math]\displaystyle{ 1, 2 }[/math] and [math]\displaystyle{ 3 }[/math], respectively. In the example given, the resulting combinatorial line is: $$ \{ 11211113\ldots, 11221223\ldots, 11231333\ldots \} $$ The Density Hales-Jewett theorem asserts that for any $\delta > 0$, for sufficiently large $n = n(\delta)$, all subsets of $[3]^n$ of size at least $\delta 3^n$ contain a combinatorial line,
