# DHJ(2.6)

DHJ(2.6) is the statement that if $A \subset ^n$ has density $\delta$, and n is sufficiently large depending on $\delta$, then there exists r such that for each ij=01,12,20, there exists a combinatorial line $w^0, w^1, w^2$ 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 $(B_w)_{w \in ^n}$ of probability at least $\delta$, and we will find a combinatorial line $w^0,w^1,w^2$ such that any two of the events $B_{w^0}, B_{w^1}, B_{w^2}$ jointly hold with positive probability.

We can color each line $w^0,w^1,w^2$ in one of eight colours depending on whether $B_{w^i} \wedge B_{w^j}$ 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), $B_{w^i} \wedge B_{w^j}$ 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 $^n$ 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. $[n^{0.1}]$). 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 $^m$ in $^n$, 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 $\delta$, 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 $^n$ and condition on the location of x’s 2’s. There must be some set of locations such that A has density at least $\delta$ 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 ${0,1}^{n'}$ of density then the set of Hamming distances where has Sperner pairs is large/structured, where $n' \approx 2n/3$.

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

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

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

Now whenever we have, say, $3/\delta$ 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 $V \subset [\sqrt{n}]$ (the “marked i’s”) has density at least $\delta/2$ and the edge set has the following density property: For every collection $V' \subset V$ with $|V'| \geq 3\delta/2$, there is at least one edge among the vertices in $V'$.

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.