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

DHJ(3), Version 5. For every [math]\displaystyle{ \delta \gt 0 }[/math] there exists n such that if [math]\displaystyle{ (B_w)_{w \in [3]^n} }[/math] are a collection of Bernoulli (i.e. 01-valued) random variables [math]\displaystyle{ B_w }[/math] (not necessarily independent), each with probability at least [math]\displaystyle{ \delta }[/math], then there exists a combinatorial line [math]\displaystyle{ w^1,w^2,w^3 }[/math] such that [math]\displaystyle{ B_{w^0} \wedge B_{w^1} \wedge B_{w^2} }[/math] has positive probability.

(The implication of Version 5 from Version 1 follows from the first moment method, observing that the set [math]\displaystyle{ A := \{ w \in [3]^n: B_w \hbox{ holds} \} }[/math] has expected density at least [math]\displaystyle{ \delta }[/math]. The reverse implication comes from a random sampling method, taking a random m-dimensional combinatorial subspace of [math]\displaystyle{ [3]^n }[/math] and letting [math]\displaystyle{ B_w }[/math] be the event that the image of [math]\displaystyle{ w\in [3]^m }[/math] under the subspace embedding map lies in A.)

Variants

DHJ(k)

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 complexity 1 if it is of the form [math]\displaystyle{ \mathcal{A}(\mathcal{U},\mathcal{V},\mathcal{W}) }[/math]. For instance, a slice [math]\displaystyle{ \Gamma_{a,b,c} }[/math] is of complexity 1. </math> DHJ(1,3) is the assertion that every dense set of complexity 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 [math]\displaystyle{ H }[/math] could be said to have complexity j if there exists a j-uniform hypergraph [math]\displaystyle{ J }[/math] such that [math]\displaystyle{ H }[/math] consists of all sets A of size k with the property that every subset [math]\displaystyle{ B\subset A }[/math] of size j belongs to [math]\displaystyle{ J. }[/math]

There is also a k-partite version of this definition. If the k vertex sets are all copies of [math]\displaystyle{ [n] }[/math], then we say that K has complexity j if for every [math]\displaystyle{ E\subset\{1,2,\dots,k\} }[/math] there is a j-uniform hypergraph [math]\displaystyle{ J_E }[/math] such that [math]\displaystyle{ K }[/math] consists of all k-tuples [math]\displaystyle{ (i_1,\dots,i_k) }[/math] such that for every [math]\displaystyle{ E\subset\{1,2,\dots,k\} }[/math] of size j the j-tuple [math]\displaystyle{ (i_s:s\in E) }[/math] belongs to [math]\displaystyle{ J_E. }[/math]

We can make a similar definition for sequences in [math]\displaystyle{ [k]^n }[/math], or equivalently ordered partitions [math]\displaystyle{ (U_1,\dots,U_k) }[/math] of [math]\displaystyle{ [n]. }[/math] This time we say that [math]\displaystyle{ \mathcal{A} }[/math] has complexity j if there are collections of sets [math]\displaystyle{ \mathcal{U}_E }[/math] such that [math]\displaystyle{ \mathcal{A} }[/math] consists of all ordered partitions [math]\displaystyle{ (U_1,\dots,U_k) }[/math] such that for every [math]\displaystyle{ E\subset\{1,2,\dots,k\} }[/math] of size j the ordered sequence of disjoint sets [math]\displaystyle{ (U_s:s\in E) }[/math] belongs to [math]\displaystyle{ \mathcal{U}_E. }[/math] For instance, the slice [math]\displaystyle{ \Gamma_{a,b,c} }[/math] has complexity 1.

DHJ(j,k) is the assertion that a subset of [math]\displaystyle{ [k]^n }[/math] of complexity j and density at least [math]\displaystyle{ \delta }[/math] contains a combinatorial line, if n is sufficiently large depending on [math]\displaystyle{ j,k,\delta }[/math]. It is not hard to check that DHJ(k-1,k) is the same as DHJ(j,k). In other words, every subset of [math]\displaystyle{ [k]^n }[/math] has complexity at most k-1.

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,20, 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).

To prove DHJ(2.6), we use the Version 5 formulation, thus we now have Bernoulli variables [math]\displaystyle{ (B_w)_{w \in [3]^n} }[/math] of probability at least [math]\displaystyle{ \delta }[/math], and we will find a combinatorial line [math]\displaystyle{ w^0,w^1,w^2 }[/math] such that any two of the events [math]\displaystyle{ B_{w^0}, B_{w^1}, B_{w^2} }[/math] jointly hold with positive probability.

We can colour each line [math]\displaystyle{ w^0,w^1,w^2 }[/math] in one of eight colours depending on whether [math]\displaystyle{ B_{w^i} \wedge B_{w^j} }[/math] intersect with positive probability for ij=01,12,20. Applying the Graham-Rothschild theorem, we can pass to a large subspace on which all lines have the same colour. But by (the Version 5 formulation of) DHJ(2.5), [math]\displaystyle{ B_{w^i} \wedge B_{w^j} }[/math] has to have positive probability for at least one line, hence for all lines. The claim follows.

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.