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 are equivalent, see this page.)

DHJ(3), Version 4. For every [math]\displaystyle{ \delta \gt 0 }[/math] there exists n such that every collection of pairs (U,V) of disjoint subsets of [n] of cardinality at least [math]\displaystyle{ \delta 3^n }[/math] contains a "corner" [math]\displaystyle{ (U,V), (U \cup D, V), (U, V \cup D) }[/math], where U, V, D are disjoint subsets of [math]\displaystyle{ [n] }[/math] (compare with the corners theorem).

(The equivalence of Version 1 and Version 2 follows by identifying a string [math]\displaystyle{ x \in [3]^n }[/math] with the pair (U,V) consisting of the 1-set and 2-set of x.)

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 }[/math] is the equal-slices density of [math]\displaystyle{ \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)). }[/math]

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 hypergraphs. A k-uniform hypergraph could be said to have complexity j if ...

(To be continued.)

DHJ(2.5)

DHJ(2.5) is the statement that if [math]\displaystyle{ A \subset [3]^n }[/math] has density [math]\displaystyle{ \delta }[/math], and n is sufficiently large depending on [math]\displaystyle{ \delta }[/math], then there exists a combinatorial line [math]\displaystyle{ w^0, w^1, w^2 }[/math] whose first two elements lie in A. This is of course weaker than DHJ(3), which requires that all three elements of the combinatorial line lie in A.

DHJ(2.5) can be deduced from DHJ(2) by partitioning [math]\displaystyle{ [3]^n }[/math] into disjoint copies of [math]\displaystyle{ [2]^m }[/math] for various values of m; indeed, for each set [math]\displaystyle{ C \subset [n] }[/math] of cardinality n-m, we have a copy of [math]\displaystyle{ [2]^m }[/math] inside [math]\displaystyle{ [3]^n }[/math] formed by considering all the strings which equal 2 at C and equal 0 or 1 elsewhere. By Sperner's theorem or DHJ(2), any of the copies of [math]\displaystyle{ [2]^m }[/math] at which A has density at least [math]\displaystyle{ \delta/2 }[/math] (say) will contain the first two points of a combinatorial line, if m is sufficiently large depending on [math]\displaystyle{ \delta }[/math]. The remaining values of m only fill up a negligible portion of the cube [math]\displaystyle{ [3]^n }[/math], and the claim follows.

DHJ(2.6)

DHJ(2.6) is the statement that if [math]\displaystyle{ A \subset [3]^n }[/math] has density [math]\displaystyle{ \delta }[/math], and n is sufficiently large depending on [math]\displaystyle{ \delta }[/math], then there exists r such that for each ij=01,12,23, there exists a combinatorial line [math]\displaystyle{ w^0, w^1, w^2 }[/math] with r wildcards whose i and j elements in A. This is of course weaker than DHJ(3), but implies DHJ(2.5).

Consequences

DHJ(3) implies the IP-Szemerédi theorem, which implies the corners theorem (in both [math]\displaystyle{ {\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.