# Difference between revisions of "Main Page"

(→The Problem) |
(→The Problem) |
||

Line 4: | Line 4: | ||

'''Density Hales-Jewett theorem:''' <math>lim_{n \rightarrow \infty} c_n/3^n = 0</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 == | == Other resources == |

## Revision as of 18:45, 8 February 2009

## 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.