DHJ(2.6) - Revision history

Teorth at 05:29, 24 February 2009

2009-02-24T05:29:56Z

← Older revision		Revision as of 22:29, 23 February 2009
Line 1:		Line 1:
	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 ~~of course~~ weaker than [[DHJ(3)]], but implies [[DHJ(2.5)]].		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 ==		== First proof ==

Teorth at 05:10, 24 February 2009

2009-02-24T05:10:27Z

← Older revision		Revision as of 22:10, 23 February 2009
Line 1:		Line 1:
	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 in A. This is of course weaker than [[DHJ(3)]], but implies [[DHJ(2.5)]].		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 of course weaker than [[DHJ(3)]], but implies [[DHJ(2.5)]].

	== First proof ==		== First proof ==

Teorth at 18:07, 16 February 2009

2009-02-16T18:07:16Z

← Older revision		Revision as of 11:07, 16 February 2009
Line 1:		Line 1:
	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 in A. This is of course weaker than [[DHJ(3)]], but implies DHJ(2.5).		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 in A. This is of course weaker than [[DHJ(3)]], but implies [[DHJ(2.5)]].

	== First proof ==		== First proof ==
Line 5:		Line 5:
	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.		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.		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 ==		== 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.		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.		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.

Teorth at 18:06, 16 February 2009

2009-02-16T18:06:48Z

← Older revision		Revision as of 11:06, 16 February 2009
Line 1:		Line 1:
	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 in A. This is of course weaker than DHJ(3), but implies DHJ(2.5).		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 in A. This is of course weaker than [[DHJ(3)]], but implies DHJ(2.5).

	== First proof ==		== First proof ==

Teorth: New page: DHJ(2.6) is the statement that if $A \subset [3]^n$ has density $\delta$ , and n is sufficiently large depending on $\delta$ , then there exists r such that ...

2009-02-16T18:04:14Z

New page: 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 ...

New page

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 in A. This is of course weaker than 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.

DHJ(2.6) - Revision history

Teorth at 05:29, 24 February 2009

Teorth at 05:10, 24 February 2009

Teorth at 18:07, 16 February 2009

Teorth at 18:06, 16 February 2009

Teorth: New page: DHJ(2.6) is the statement that if A \subset [3]^n has density \delta, and n is sufficiently large depending on \delta, then there exists r such that ...

Teorth: New page: DHJ(2.6) is the statement that if $A \subset [3]^n$ has density $\delta$ , and n is sufficiently large depending on $\delta$ , then there exists r such that ...