# Difference between revisions of "Main Page"

From Polymath1Wiki

Line 1: | Line 1: | ||

− | + | == The Problem == | |

− | <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 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: |

− | + | $$ | |

+ | \{ 11211113\ldots, 11221223\ldots, 11231333\ldots \} | ||

+ | $$ | ||

+ | 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 == |

− | * [http:// | + | |

− | * [http:// | + | * [http://blogsearch.google.com/blogsearch?hl=en&ie=UTF-8&q=polymath1&btnG=Search+Blogs Blog posts related to the Polymath1 project] |

− | + | * [http://meta.wikimedia.org/wiki/Help:Contents Wiki user's guide] |

## Revision as of 16:40, 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 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:
$$
\{ 11211113\ldots, 11221223\ldots, 11231333\ldots \}
$$
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,