# Difference between revisions of "Main Page"

(→The Problem) |
|||

Line 1: | Line 1: | ||

== The Problem == | == 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> | + | 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>. |

− | + | ||

− | \{ 11211113\ldots, 11221223\ldots, 11231333\ldots \} | + | '''Density Hales-Jewett theorem:''' <math>lim_{n \rightarrow \infty} c_n/3^n = 0</math> |

− | + | ||

− | + | ||

− | + | ||

− | + | ||

== Other resources == | == Other resources == |

## Revision as of 17:44, 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]