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 are in A. This is weaker than DHJ(2.7) and DHJ(3), but implies DHJ(2.5).

First proof

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

Second proof

One can tone the Ramsey theory in the above proof down a notch, by replacing the Graham-Rothschild theorem by the simpler Folkman's theorem (this is basically because of the permutation symmetry of the random subcube ensemble). Indeed, given a dense set A in [math]\displaystyle{ [3]^n }[/math] we can colour [n] in eight colours, colouring a shift r depending on whether there exists a combinatorial line with r wildcards whose first two (or last two, or first and last) vertices lie in A. By Folkman's theorem, we can find a monochromatic m-dimensional pinned cube Q in [n] (actually it is convenient to place this cube in a much smaller set, e.g. [math]\displaystyle{ [n^{0.1}] }[/math]). If the monochromatic colour is such that all three pairs of a combinatorial line with r wildcards can occur in A, we are done, so suppose that there is no line with r wildcards with r in Q with (say) the first two elements lying in A.

Now consider a random copy of [math]\displaystyle{ [3]^m }[/math] in [math]\displaystyle{ [3]^n }[/math], using the m generators of Q to determine how many times each of the m wildcards that define this copy will get. The expected density of A in this cube is about [math]\displaystyle{ \delta }[/math], so by DHJ(2.5) at least one of the copies is going to get a line whose first two elements lie in A, which gives the contradiction.

A Ramsey-free proof?

Here is a potential angle for a Ramsey-free proof of DHJ(2.6). The idea would be to soup up the Sperner-based proof of DHJ(2.5) and show that the set D of (Hamming) distances where we can find a 01-half-line in A is “large” and “structured”.

So again, let be x a random string in [math]\displaystyle{ [3]^n }[/math] and condition on the location of x’s 2’s. There must be some set of locations such that A has density at least [math]\displaystyle{ \delta }[/math] on the induced 01 hypercube (which will likely have dimension around 2n/3). So fix 2’s into these locations and pass to the 01 hypercube. Our goal is now to show that if A is a subset of [math]\displaystyle{ {0,1}^{n'} }[/math] of density then the set of Hamming distances where has Sperner pairs is large/structured, where [math]\displaystyle{ n' \approx 2n/3 }[/math].

Almost all the action in [math]\displaystyle{ \{0,1\}^{n'} }[/math] is around the [math]\displaystyle{ \Theta(\sqrt{n}) }[/math] middle slices. Let’s simplify slightly (although this is not much of a cheat) by pretending that has A density [math]\displaystyle{ \delta }[/math] on the union of the middle slices *and* that these slices have “equal weight”. Index the slices by [math]\displaystyle{ i \in [\sqrt{n}] }[/math], with the [math]\displaystyle{ i^{th} }[/math] slice actually being the [math]\displaystyle{ (n'/2-\sqrt{n'}/2+i)^{th} }[/math] slice.

Let [math]\displaystyle{ A_i }[/math] denote the intersection of A with the [math]\displaystyle{ i^{th} }[/math] slice, and let [math]\displaystyle{ \mu_i }[/math] denote the relative density of [math]\displaystyle{ A_i }[/math] within its slice.

Here is a slightly wasteful but simplifying step: Since the average of the [math]\displaystyle{ \mu_i }[/math]’s is [math]\displaystyle{ \delta }[/math], a simple Markov-type argument shows that [math]\displaystyle{ \mu_i \geq \delta/2 }[/math] for at least a [math]\displaystyle{ \geq \delta/2 }[/math] fraction of the i’s. Call such an i “marked”.

Now whenever we have, say, [math]\displaystyle{ 3/\delta }[/math] marked i’s, it means we have a portion of A with a number of points at least times the number of points in a single middle slice. Hence Sperner's theorem tells us we get two comparable points from among these slices.

Thus we have reduced to the following setup:

There is a graph G=(V,E), where [math]\displaystyle{ V \subset [\sqrt{n}] }[/math] (the “marked i’s”) has density at least [math]\displaystyle{ \delta/2 }[/math] and the edge set has the following density property: For every collection [math]\displaystyle{ V' \subset V }[/math] with [math]\displaystyle{ |V'| \geq 3\delta/2 }[/math], there is at least one edge among the vertices in [math]\displaystyle{ V' }[/math].

Let D be the set of “distances” in this graph, where an edge (i,j) has “distance” |i-j|. Show that this set of distances must be large and/or have some useful arithmetic structure.