Difference between revisions of "Main Page"

From Polymath1Wiki
Jump to: navigation, search
(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>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:
+
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>
$$
+
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 ==
 
== 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]

Other resources