Main Page

From Polymath Wiki
Revision as of 01:45, 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 [math]x[/math] in it, e.g., [math]112x1xx3\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: [math]\{ 11211113\ldots, 11221223\ldots, 11231333\ldots \}[/math]. A subset of [math][3]^n[/math] is said to be line-free if it contains no lines. Let [math]c_n[/math] be the size of the largest line-free subset of [math][3]^n[/math].

Density Hales-Jewett theorem: [math]lim_{n \rightarrow \infty} c_n/3^n = 0[/math]

The original proof of Density Hales-Jewett used arguments from ergodic theory.

Other resources