DHJ(2.6)

From Polymath1Wiki

DHJ(2.6) is the statement that if $A \subset [3]^n$ has density $δ$ , and n is sufficiently large depending on $δ$ , 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 [3]^n}$ of probability at least $δ$ , 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 $[3] 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 $[3] m$ in $[3] 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 $δ$ , 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 $[3] 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 $δ$ 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 $δ$ 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 t h$ slice actually being the $(n'/2-\sqrt{n'}/2+i)^{th}$ slice.

Let $A i$ denote the intersection of A with the $i t h$ slice, and let $μ i$ denote the relative density of $A i$ within its slice.

Here is a slightly wasteful but simplifying step: Since the average of the $μ i$ ’s is $δ$ , 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 / δ$ 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 $δ / 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.

DHJ(2.6)

From Polymath1Wiki

First proof

Second proof

A Ramsey-free proof?

Views

Personal tools

Navigation

Search

Toolbox