Main Page

From Polymath Wiki
Revision as of 00:40, 9 February 2009 by (Talk)

Jump to: navigation, search

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,

Other resources