Difference between revisions of "DHJ(3)"

From Polymath Wiki
Jump to: navigation, search
(Variants: begun description of DHJ(j,k))
m (DHJ(1,3))
Line 25: Line 25:
 
Call <math>\mathcal{A}</math> a ''set of rank 1'' if it is of the form <math>\mathcal{A}(\mathcal{U},\mathcal{V},\mathcal{W}).</math> DHJ(1,3) is the assertion that every dense set of rank 1 contains a combinatorial line. Here is a proof of this assertion if we assume that <math>\mathcal{W}=[2]^n</math> and we interpret "dense" to mean "dense in the [[equal-slices measure]].
 
Call <math>\mathcal{A}</math> a ''set of rank 1'' if it is of the form <math>\mathcal{A}(\mathcal{U},\mathcal{V},\mathcal{W}).</math> DHJ(1,3) is the assertion that every dense set of rank 1 contains a combinatorial line. Here is a proof of this assertion if we assume that <math>\mathcal{W}=[2]^n</math> and we interpret "dense" to mean "dense in the [[equal-slices measure]].
  
First, choose a random permutation <math>\pi</math> of <math>[n]</math>. Without loss of generality it is the identity. Then the expected number of disjoint quadruples <math>(U,V,W)</math> such that U is an initial segment, W is a final segment, and U, V and W are elements of <math>\mathcal{U},\mathcal{V}</math> and <math>\mathcal{W}</math> that partition <math>[n]</math> is approximately <math>\delta n^2/2</math>, where <math>\delta<\math> is the equal-slices density of <math>\mathcal{A}</math>. (The total number of such triples if U, V and W don't have to belong to <math>\mathcal{U},\mathcal{V}</math> and <math>\mathcal{W}</math> is roughly <math>n^2/2.)</math> Therefore, there must exist some fixed set <math>W\in\mathcal{W}</math> such that the number of such triples <math>(U,V,W)</math> is at least <math>\delta n/2.</math> In particular, we can find two such triples <math>(U_1,V_1,W)</math> and <math>(U_2,V_2,W).</math> If <math>U_1\subset U_2,</math> then this gives us the combinatorial line <math>(U_1,V_1,W),(U_2,V_2,W),(U_1,V_2,W\cup(U_2\cap V_1)).<\math>
+
First, choose a random permutation <math>\pi</math> of <math>[n]</math>. Without loss of generality it is the identity. Then the expected number of disjoint quadruples <math>(U,V,W)</math> such that U is an initial segment, W is a final segment, and U, V and W are elements of <math>\mathcal{U},\mathcal{V}</math> and <math>\mathcal{W}</math> that partition <math>[n]</math> is approximately <math>\delta n^2/2</math>, where <math>\delta</math> is the equal-slices density of <math>\mathcal{A}</math>. (The total number of such triples if U, V and W don't have to belong to <math>\mathcal{U},\mathcal{V}</math> and <math>\mathcal{W}</math> is roughly <math>n^2/2.)</math> Therefore, there must exist some fixed set <math>W\in\mathcal{W}</math> such that the number of such triples <math>(U,V,W)</math> is at least <math>\delta n/2.</math> In particular, we can find two such triples <math>(U_1,V_1,W)</math> and <math>(U_2,V_2,W).</math> If <math>U_1\subset U_2,</math> then this gives us the combinatorial line <math>(U_1,V_1,W),(U_2,V_2,W),(U_1,V_2,W\cup(U_2\cap V_1)).</math>
  
 
Quite possibly a proof of this kind can be devised that proves the full statement DHJ(1,3).
 
Quite possibly a proof of this kind can be devised that proves the full statement DHJ(1,3).

Revision as of 19:43, 15 February 2009

The k=3 Density Hales-Jewett theorem (DHJ(3)) has many equivalent forms.

Versions of DHJ(3)

Let [math][3]^n[/math] be the set of all length [math]n[/math] strings over the alphabet [math]1, 2, 3[/math]. A subset of [math][3]^n[/math] is said to be line-free if it contains no combinatorial lines. Let [math]c_n[/math] be the size of the largest line-free subset of [math][3]^n[/math].

DHJ(3), Version 1. For every [math]\delta \gt 0[/math] there exists n such that every subset [math]A \subset [3]^n[/math] of density at least [math]\delta[/math] contains a combinatorial line.

DHJ(3), Version 2. [math]\lim_{n \rightarrow \infty} c_n/3^n = 0[/math].

(The equivalence of Version 1 and Version 2 is clear.)

DHJ(3), Version 3. For every [math]\delta \gt 0[/math] there exists n such that every subset [math]A \subset [3]^n[/math] of equal-slices density at least [math]\delta[/math] contains a combinatorial line.

(For the proof that Version 3 and Version 1, see this page.)

Variants

One can of course define DHJ(k) for any positive integer k by a similar method. DHJ(1) is trivial, and DHJ(2) follows quickly from Sperner's theorem.

DHJ(1,3)

The following variant of DHJ(3) is motivated by the proof of Sperner's theorem. Let [math]\mathcal{U},\mathcal{V}[/math] and [math]\mathcal{W}[/math] be collections of subsets of [math][n].[/math] Define [math]\mathcal{A}(\mathcal{U},\mathcal{V},\mathcal{W})[/math] to be the set of all triples [math](U,V,W),[/math] where [math]U,V,W[/math] are disjoint, and [math]U\in\mathcal{U},V\in\mathcal{V},W\in\mathcal{W}.[/math] These triples are in an obvious one-to-one correspondence with elements of [math][3]^n.[/math]

Call [math]\mathcal{A}[/math] a set of rank 1 if it is of the form [math]\mathcal{A}(\mathcal{U},\mathcal{V},\mathcal{W}).[/math] DHJ(1,3) is the assertion that every dense set of rank 1 contains a combinatorial line. Here is a proof of this assertion if we assume that [math]\mathcal{W}=[2]^n[/math] and we interpret "dense" to mean "dense in the equal-slices measure.

First, choose a random permutation [math]\pi[/math] of [math][n][/math]. Without loss of generality it is the identity. Then the expected number of disjoint quadruples [math](U,V,W)[/math] such that U is an initial segment, W is a final segment, and U, V and W are elements of [math]\mathcal{U},\mathcal{V}[/math] and [math]\mathcal{W}[/math] that partition [math][n][/math] is approximately [math]\delta n^2/2[/math], where [math]\delta[/math] is the equal-slices density of [math]\mathcal{A}[/math]. (The total number of such triples if U, V and W don't have to belong to [math]\mathcal{U},\mathcal{V}[/math] and [math]\mathcal{W}[/math] is roughly [math]n^2/2.)[/math] Therefore, there must exist some fixed set [math]W\in\mathcal{W}[/math] such that the number of such triples [math](U,V,W)[/math] is at least [math]\delta n/2.[/math] In particular, we can find two such triples [math](U_1,V_1,W)[/math] and [math](U_2,V_2,W).[/math] If [math]U_1\subset U_2,[/math] then this gives us the combinatorial line [math](U_1,V_1,W),(U_2,V_2,W),(U_1,V_2,W\cup(U_2\cap V_1)).[/math]

Quite possibly a proof of this kind can be devised that proves the full statement DHJ(1,3).

DHJ(j,k)

The statement DHJ(j,k) is motivated by concepts connected with hypergraphs. A k-uniform hypergraph could be said to have complexity j if ...

(To be continued.)

[Discuss DHJ(2.5), DHJ(j,k) here]

Consequences

DHJ(3) implies the IP-Szemerédi theorem, which implies the corners theorem (in both [math]{\Bbb Z}/N{\Bbb Z}[/math] and [math][3]^n[/math]), which in turn implies Roth's theorem (in both [math]{\Bbb Z}/N{\Bbb Z}[/math] and [math][3]^n[/math]).

DHJ(3) also implies the k=3 version of the coloring Hales-Jewett theorem.