DHJ(2.6)

From Polymath1Wiki
Revision as of 22:29, 23 February 2009 by Teorth (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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

We can color each line [math]w^0,w^1,w^2[/math] in one of eight colours depending on whether [math]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]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][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][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][3]^m[/math] in [math][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]\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][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]\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]{0,1}^{n'}[/math] of density then the set of Hamming distances where has Sperner pairs is large/structured, where [math]n' \approx 2n/3[/math].

Almost all the action in [math]\{0,1\}^{n'}[/math] is around the [math]\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]\delta[/math] on the union of the middle slices *and* that these slices have “equal weight”. Index the slices by [math]i \in [\sqrt{n}][/math], with the [math]i^{th}[/math] slice actually being the [math](n'/2-\sqrt{n'}/2+i)^{th}[/math] slice.

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

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

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