This thread is a continuation of the previous thread here on the polymath1 project.  Currently, activity is focusing on the following problems:

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.  Thanks to efforts from previous threads, we have the first five values of c_n:

c_0=1; c_1=2; c_2=6; c_3=18; c_4=52.

We also know that 150 \leq c_5 \leq 154, and are working to narrow this further.  The arguments justifying these bounds can be found here.  The latest bounds for the next few values of c_n can be found 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, we know the following values for these sequences:

c^\mu_0 = 1; c^\mu_1 = 2; c^\mu_2 = 4


\overline{c}^\mu_0 = 1; \overline{c}^\mu_1 = 2; \overline{c}^\mu_2 = 4; \overline{c}^\mu_3 = 6; \overline{c}^\mu_4 = 9; \overline{c}^\mu_5 = 12.

There are also some further upper and lower bounds known; see this spreadsheet for the latest bounds, and this page for proofs of the bounds.  The data so far is consistent with the conjecture, but more work would be needed to obtain a more convincing case for it.

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 = 14; c'_4 = 43.

The best asymptotic lower bound known is c'_n \gg 3^n/\sqrt{n}.  Given that we have a significantly superior lower bound of c_n \geq 3^{n-O(\sqrt{\log n})} for c_n, one might hope to similarly improve the lower bound for Moser’s problem.  But there seems to be a technical snag, based on the observation that between two slices \Gamma_{a,b,c} and \Gamma_{a',b',c'} with the c-a=c'-a', there are in fact quite a few combinatorial lines connecting them, and so it is not obvious how to create a geometric line-free set that involves more than one slice per value of c-a.

It is also of interest to work out what asymptotic lower bound for c_n one can get for larger values of k than 3.

Comments on this thread should start at 700.  We will also try to record progress made at the polymath1 wiki and at the polymath1 spreadsheet, as appropriate.