DHJ(3)

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].

(The equivalence of Version 1 and Version 2 is clear.)

DHJ(3), Version 3. For every [math]\displaystyle{ \delta \gt 0 }[/math] there exists n such that every subset [math]\displaystyle{ A \subset [3]^n }[/math] of equal-slices density at least [math]\displaystyle{ \delta }[/math] contains a combinatorial line.

(For the proof that Version 3 and Version 1, see this page.)

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.

DHJ(1,3)

The following variant of DHJ(3) is motivated by the proof of Sperner's theorem. Let [math]\displaystyle{ \mathcal{U},\mathcal{V} }[/math] and [math]\displaystyle{ \mathcal{W} }[/math] be collections of subsets of [math]\displaystyle{ [n]. }[/math] Define [math]\displaystyle{ \mathcal{A}(\mathcal{U},\mathcal{V},\mathcal{W}) }[/math] to be the set of all triples [math]\displaystyle{ (U,V,W), }[/math] where [math]\displaystyle{ U,V,W }[/math] are disjoint, and [math]\displaystyle{ U\in\mathcal{U},V\in\mathcal{V},W\in\mathcal{W}. }[/math] These triples are in an obvious one-to-one correspondence with elements of [math]\displaystyle{ [3]^n. }[/math]

Call [math]\displaystyle{ \mathcal{A} }[/math] a set of rank 1 if it is of the form [math]\displaystyle{ \mathcal{A}(\mathcal{U},\mathcal{V},\mathcal{W}). }[/math] DHJ(1,3) is the assertion that every dense set of rank 1 contains a combinatorial line. Here is a proof of this assertion if we assume that [math]\displaystyle{ \mathcal{W}=[2]^n }[/math] and we interpret "dense" to mean "dense in the equal-slices measure.

First, choose a random permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ [n] }[/math]. Without loss of generality it is the identity. Then the expected number of disjoint quadruples [math]\displaystyle{ (U,V,W) }[/math] such that U is an initial segment, W is a final segment, and U, V and W are elements of [math]\displaystyle{ \mathcal{U},\mathcal{V} }[/math] and [math]\displaystyle{ \mathcal{W} }[/math] that partition [math]\displaystyle{ [n] }[/math] is approximately [math]\displaystyle{ \delta n^2/2 }[/math], where [math]\displaystyle{ \delta\lt \math\gt is the equal-slices density of \lt math\gt \mathcal{A} }[/math]. (The total number of such triples if U, V and W don't have to belong to [math]\displaystyle{ \mathcal{U},\mathcal{V} }[/math] and [math]\displaystyle{ \mathcal{W} }[/math] is roughly [math]\displaystyle{ n^2/2.) }[/math] Therefore, there must exist some fixed set [math]\displaystyle{ W\in\mathcal{W} }[/math] such that the number of such triples [math]\displaystyle{ (U,V,W) }[/math] is at least [math]\displaystyle{ \delta n/2. }[/math] In particular, we can find two such triples [math]\displaystyle{ (U_1,V_1,W) }[/math] and [math]\displaystyle{ (U_2,V_2,W). }[/math] If [math]\displaystyle{ U_1\subset U_2, }[/math] then this gives us the combinatorial line [math]\displaystyle{ (U_1,V_1,W),(U_2,V_2,W),(U_1,V_2,W\cup(U_2\cap V_1)).\lt \math\gt Quite possibly a proof of this kind can be devised that proves the full statement DHJ(1,3). ==== DHJ(j,k) ==== The statement DHJ(j,k) is motivated by concepts connected with [http://en.wikipedia.org/wiki/Hypergraph/ hypergraphs]. A k-uniform hypergraph could be said to have complexity j if ... (To be continued.) [Discuss DHJ(2.5), DHJ(j,k) here] == Consequences == DHJ(3) implies the [[IP-Szemerédi theorem]], which implies the [[corners theorem]] (in both \lt math\gt {\Bbb Z}/N{\Bbb Z} }[/math] and [math]\displaystyle{ [3]^n }[/math]), which in turn implies Roth's theorem (in both [math]\displaystyle{ {\Bbb Z}/N{\Bbb Z} }[/math] and [math]\displaystyle{ [3]^n }[/math]).

DHJ(3) also implies the k=3 version of the coloring Hales-Jewett theorem.