# Main Page

From Polymath Wiki

Revision as of 00:40, 9 February 2009 by 76.64.42.136 (Talk)

## The Problem

Let [math][3]^n[/math] be the set of all length [math]n[/math] strings over the alphabet [math]1, 2, 3[/math]. A *combinatorial line* is a set of three points in [math][3]^n[/math], formed by taking a string with one or more wildcards in it, e.g., [math]112*1**3\ldots[/math], and replacing those wildcards by [math]1, 2[/math] and [math]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,