You are currently browsing the tag archive for the ‘density Hales-Jewett’ tag.

This is a continuation of the 700-799 thread of the polymath1 project, which is now full.  During the course of that thread, we have made significant progress on the three problems being focused on:

1.  Upper and lower bounds for $c_n$ for small n.

Let $c_n$ be the largest size of a set in $[3]^n$ without a combinatorial line.   We now have both human and computer-assisted proofs of the first few values of this sequence:

$c_0=1; c_1=2; c_2=6; c_3=18; c_4=52; c_5 = 150; c_6 = 450$.

The current best-known bounds for $c_7$ are $1302 \leq c_7 \leq 1348$.  Given the gap involved here, and the rate at which the complexity of the problem has increased with n, it seems unlikely that we will be able to compute $c_7$ exactly any time soon, but it is possible that some improvement can still be made here.

2. A hyper-optimistic conjecture

Consider a variant of the above problem in which each element of $[3]^n$ with a 1s, b 2s, and c 3s is weighted by the factor $\frac{a! b! c!}{n!}$; this gives $[3]^n$ a total weight of $\frac{(n+1)(n+2)}{2}$. Let $c^\mu_n$ be the largest weight of a line-free set of $[3]^n$, and let $\overline{c}^\mu_n$ be the largest size of a subset of

$\Delta_n := \{ (a,b,c) \in {\Bbb Z}_+^3: a+b+c=n \}$

which contains no upward-pointing equilateral triangles $(a+r,b,c), (a,b+r,c), (a,b,c+r)$ with r>0. It is known that $c^\mu_n \geq \overline{c}^\mu_n$; the “hyper-optimistic conjecture” is that one in fact has $c^\mu_n = \overline{c}^\mu_n$. This would imply density Hales-Jewett for k=3.

Currently, the conjecture is verified for $n \leq 5$, where the values of $c^\mu_n = \overline{c}^\mu_n$ for $n=0,1,2,3,4,5$ are 1,2,4,6,9,12 respectively; see this page and this page for details.  It seems feasible to handle $n=6$.  Currently we know that $15 \leq \overline{c}^\mu_6 \leq 17$ and $\overline{c}^\mu_6 \leq c^\mu_6 \leq 28$.

3.  Asymptotics for Moser’s cube problem

Moser’s cube problem asks to compute the largest size $c'_n$ of a subset of the cube $[3]^n$ without geometric lines.  The first few values of $c'_n$ are known:

$c'_0=1; c'_1 = 2; c'_2 = 6; c'_3 = 16; c'_4 = 43$.

The best asymptotic lower bound known is still of the order of $3^n/\sqrt{n}$.  Improving this bound seems related to the well-known problem of improving the bounds in Behrend’s construction of an AP-3 free set of integers.

We are quite close now to pinning down $c'_5$; we know that it is equal to either 124 or 125, and it is looking increasingly unlikely that it is 125.