DHJ(3): Difference between revisions
No edit summary |
|||
| Line 2: | Line 2: | ||
== Versions of DHJ(3) == | == Versions of DHJ(3) == | ||
Let <math>[3]^n</math> be the set of all length <math>n</math> strings over the alphabet <math>1, 2, 3</math>. A subset of <math>[3]^n</math> is said to be ''line-free'' if it contains no [[combinatorial line]]s. Let <math>c_n</math> be the size of the largest line-free subset of <math>[3]^n</math>. | |||
'''DHJ(3), Version 1'''. For every <math>\delta > 0</math> there exists n such that every subset <math>A \subset [3]^n</math> of density at least <math>\delta</math> contains a [[combinatorial line]]. | '''DHJ(3), Version 1'''. For every <math>\delta > 0</math> there exists n such that every subset <math>A \subset [3]^n</math> of density at least <math>\delta</math> contains a [[combinatorial line]]. | ||
'''DHJ(3), Version 2'''. <math>\lim_{n \rightarrow \infty} c_n/3^n = 0</math>. | '''DHJ(3), Version 2'''. <math>\lim_{n \rightarrow \infty} c_n/3^n = 0</math>. | ||
Revision as of 09:06, 14 February 2009
The k=3 Density Hales-Jewett theorem (DHJ(3)) has many equivalent forms.
Versions of DHJ(3)
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 subset of [math]\displaystyle{ [3]^n }[/math] is said to be line-free if it contains no combinatorial lines. Let [math]\displaystyle{ c_n }[/math] be the size of the largest line-free subset of [math]\displaystyle{ [3]^n }[/math].
DHJ(3), Version 1. For every [math]\displaystyle{ \delta \gt 0 }[/math] there exists n such that every subset [math]\displaystyle{ A \subset [3]^n }[/math] of density at least [math]\displaystyle{ \delta }[/math] contains a combinatorial line.
DHJ(3), Version 2. [math]\displaystyle{ \lim_{n \rightarrow \infty} c_n/3^n = 0 }[/math].
Variants
One can of course define DHJ(k) for any positive integer k by a similar method. DHJ(1) is trivial, and DHJ(2) follows quickly from Sperner's theorem.
[Discuss DHJ(2.5), DHJ(j,k) here]
