Main Page: Difference between revisions
No edit summary |
|||
| 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 16:44, 8 February 2009
The Problem
Let [math]\displaystyle{ [3]^n }[/math] be the set of all length [math]\displaystyle{ n }[/math] strings over the alphabet [math]\displaystyle{ 1, 2, 3 }[/math]. A combinatorial line is a set of three points in [math]\displaystyle{ [3]^n }[/math], formed by taking a string with one or more wildcards [math]\displaystyle{ x }[/math] in it, e.g., [math]\displaystyle{ 112x1xx3\ldots }[/math], and replacing those wildcards by [math]\displaystyle{ 1, 2 }[/math] and [math]\displaystyle{ 3 }[/math], respectively. In the example given, the resulting combinatorial line is: [math]\displaystyle{ \{ 11211113\ldots, 11221223\ldots, 11231333\ldots \} }[/math]. A subset of [math]\displaystyle{ [3]^n }[/math] is said to be line-free if it contains no lines. Let [math]\displaystyle{ c_n }[/math] be the size of the largest line-free subset of [math]\displaystyle{ [3]^n }[/math].
Density Hales-Jewett theorem: [math]\displaystyle{ lim_{n \rightarrow \infty} c_n/3^n = 0 }[/math]
