Difference between revisions of "DHJ(3)"

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

Versions of DHJ(3)

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

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

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

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

DHJ(3), Version 3. For every $\delta \gt 0$ there exists n such that every subset $A \subset [3]^n$ of equal-slices density at least $\delta$ 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 $\mathcal{U},\mathcal{V}$ and $\mathcal{W}$ be collections of subsets of $[n].$ Define $\mathcal{A}(\mathcal{U},\mathcal{V},\mathcal{W})$ to be the set of all triples $(U,V,W),$ where $U,V,W$ are disjoint, and $U\in\mathcal{U},V\in\mathcal{V},W\in\mathcal{W}.$ These triples are in an obvious one-to-one correspondence with elements of $[3]^n.$

Call $\mathcal{A}$ a set of rank 1 if it is of the form $\mathcal{A}(\mathcal{U},\mathcal{V},\mathcal{W}).$ 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 $\mathcal{W}=[2]^n$ and we interpret "dense" to mean "dense in the equal-slices measure.

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

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 ${\Bbb Z}/N{\Bbb Z}$ and $[3]^n$), which in turn implies Roth's theorem (in both ${\Bbb Z}/N{\Bbb Z}$ and $[3]^n$).

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