Upper and lower bounds for the density Hales-Jewett problem

5 February, 2009 in math.CO, polymath | Tags: polymath1

This is a continuation of several threads from Tim Gowers’ massively collaborative mathematics project, “A combinatorial approach to density Hales-Jewett“, which I discussed in my previous post.

For any positive integer n, let ${}[3]^n$ be the set of strings of length n consisting of 1s, 2s, and 3s, and define a combinatorial line to be a triple of such strings arising by taking a string in $\{1,2,3,x\}^n$ with at least one wildcard x, and substituting x=1, x=2, x=3 in that string (e.g. xx1x3 would give the combinatorial line $\{11113, 22123, 33133\}$ ). Call a set $A \subset [3]^n$ of strings line-free if it contains no combinatorial lines, and let $c_n$ be the size of the largest set A which is line-free. We then have

Density Hales-Jewett theorem (k=3): $c_n = o(3^n)$ , i.e. $\lim_{n \to \infty} c_n/3^n = 0$ .

This theorem implies several other important results, most notably Roth’s theorem on length three progressions (in an arbitrary abelian group!) and also the corners theorem of Ajtai and Szemeredi (again in an arbitrary abelian group).

Here are some of the questions we are initially exploring in this thread (and which I will comment further on below the fold):

What are the best upper and lower bounds for $c_n$ for small n? Currently we know $c_0=1, c_1=2, c_2=6, c_3=18, c_4=52$ , with some partial results for higher n. We also have some relationships between different $c_n$ .
What do extremal or near-extremal sets (i.e. line-free sets with cardinality close to $c_n$ ) look like?
What are some good constructions of line-free sets that lead to asymptotic lower bounds on $c_n$ ? The best asymptotic lower bound we have currently is $c_n \geq 3^{n - O( \sqrt{\log n} )}$ .
Can these methods extend to other related problems, such as the Moser cube problem or the capset problem?
How feasible is it to extend the existing combinatorial proofs of Roth’s theorem (or the corners theorem), in particular the arguments of Szemeredi, to the Density Hales-Jewett theorem?

But I imagine that further threads might develop in the course of the discussion.

As with the rest of the project, this is supposed to be an open collaboration: please feel free to pose a question or a comment, even if (or especially if) it is just barely non-trivial. (For more on the “rules of the game”, see this post.)

— I. $c_n$ for small n —

Because the Cartesian product of two line-free sets is line-free, we have a lower bound

$c_{n+m} \geq c_n c_m$ (1)

for all $n,m \geq 1$ , although this seems to be an inferior bound in practice.

There is a trivial bound

$c_{n+1} \leq 3 c_n$ (2)

which comes from the observation that any line-free subset of ${}[3]^{n+1}$ can be split into three slices, each of which is essentially a line-free subset of ${}[3]^n$ . In particular, since $c_1 = 2$ , we see that

$c_n \leq 2 \times 3^{n-1}$ (3)

for $n \geq 1$ .

If we identify ${}[3] = \{1,2,3\}$ with ${\Bbb Z}/3{\Bbb Z}$ and consider the set

$D_n := \{ (x_1,\ldots,x_n) \in {\Bbb Z}/3{\Bbb Z}: x_1+\ldots+x_n \neq 0 \hbox{ mod } 3 \}$ , (4)

thus $|D_n| = 2 \times 3^{n-1}$ . Observe that a combinatorial line with a,b,c,k 1s, 2s, 3s, and wildcards respectively lies in $D_n$ if and only if k is a multiple of 3, and a is not equal to b mod 3. In particular, $D_n$ is line-free for $n = 1,2,3$ , thus matching the upper bound (3) and concluding that

$c_1 = 2; c_2 = 6; c_3 = 18.$ (5)

For n=4, the only combinatorial lines remaining in $D_4$ are $1xxx, 2xxx$ and their permutations. Thus (as observed in Neylon.83) the set $D_4 \backslash \{1111, 2222\}$ is line-free, leading to the lower bound $c_4 \geq 52$ .

This bound was complemented with the lower bound $c_4 \leq 52$ in Jakobsen.90. Thus $c_4 = 52$ .

For $c_5$ , the best lower bound currently is $c_5 \geq 145$ (Neylon.83) and $c_5 \leq 3c_4 = 156$ .

No attempt at getting reasonable bounds for $c_6, c_7$ , etc. appears in the previous threads.

Question I.A: Can we improve the upper and lower bounds on $c_5, c_6, c_7$ ?

Question I.B: Is there some reasonably efficient way to automate this process?

Question I.C: What do the extremal line-free sets (sets of size close to $c_n$ ) look like?

At some point we should submit this sequence to the OEIS.

— II. Lower bounds on $c_n$ for large n —

For any integers a,b,c adding up to n, let $\Gamma_{a,b,c} \subset [3]^n$ be the set of all strings with a 1s, b 2s, and c 3s. Observe that if $B$ is any set of triples (a,b,c) that avoids equilateral triangles $(a+r,b,c), (a,b+r,c), (a,b,c+r)$ for $r > 0$ , then the set $\Gamma_B := \bigcup_{(a,b,c) \in B} \Gamma_{a,b,c}$ is line-free. In particular, if we choose B to be the set of all triples $(a,b,c)$ such that a+2b lies in a set free of length three arithmetic progressions (e.g. a Behrend set), then $\Gamma_B$ is line-free. This seems to give a lower bound

$c_n \geq 3^{n - O(\sqrt{\log n})}$ . (6)

Question II.A: Using the Elkin bound on Behrend sets, what is the precise lower bound one gets? (Solymosi.46.5 notes that we should restrict the Behrend set to scale $\sqrt{n}$ rather than n).

Question II.B: What does one get for higher k than 3? Presumably one would use the O’Bryant bound (O’Bryant.126).

Question II.C: Do the examples from Section I extend to give competitive lower bounds for large n?

Question II.D: Are there better ways to avoid triangles or corners in two dimensions than simply lifting up the Behrend example from one dimension?

— III. Miscellanous facts about $c_n$ —

Using the colouring Hales-Jewett theorem, one can show that for every m, one has $c_n < 3^{n-m} c_m$ for sufficiently large m, improving (2) very slightly; see (Tao.85).

Question III.A: Anything else we can say about the $c_n$ ? For instance, is there a relation to Hales-Jewett numbers HJ(3,r) (defined as the first n such that every r-colouring of ${}[3]^n$ contains a monochromatic combinatorial line?)

Note: as pointed out in Gasarch.45.5, Hindman and Tressler have recently established that $HJ(3,2)=4$ , $HJ(3,3) > 6$ , and $HJ(4,2) > 6$ .

— IV. Related problems —

Let $c'_n$ denote the largest subset of ${}[3]^n$ which does not contain any geometric line (which is the same as a combinatorial line, but has a second wildcard y which goes from 3 to 1 whilst x goes from 1 to 3, e.g. xx2yy gives the geometric line $11233, 22222, 33211$ ). The Moser cube problem is to understand the behaviour of $c'_n$ . The first few values are (see OEIS A003142):

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

It is clear that $c'_n \leq c_n$ .

Elsholtz.43 proposed modifying the construction of (6) to give a similar lower bound on $c'_n$ , but a difficulty was found in Solymosi.48. Currently, the best known asymptotic bounds for $c'_n$ are

$3^n / \sqrt{n} \ll c'_n \ll o(3^n)$ (8)

Question IV.A. Can we improve the lower bound in (8)?

Question IV.B. Can we get good bounds on $c'_5, c'_6$ ?

Define $c''_n$ to be the largest cardinality of a subset of ${}[3]^n$ which contains no algebraic lines, defined as a triple $\{ x, x+r, x+2r\}$ where $x, r \in ({\Bbb Z}/3{\Bbb Z})^n \equiv [3]^n$ ; such sets are known as capsets. Clearly $c''_n \leq c'_n \leq c_n$ . As noted my previous blog post, the best asymptotic bounds are

$(2.2174\ldots)^n \leq c''_n \ll 3^n/n$ (9)

Question IV.C. Can we improve on these bounds in any way?

Question IV.D. What are the first few values of $c''_n$ ? Brute force calculation reveals $c''_0 = 1, c''_1 = 2, c''_2 = 4$ . (Presumably this sequence is also in the OEIS.)

[Update, Feb 7: I will now maintain a running table of the current “world records” for $c_n, c'_n, c''_n$ for small n, formed by combining all the bounds already mentioned in this post and comments.]

[Update, Feb 8: A more complete (and up-to-date) spreadsheet can now be found here.]

n	$c_n$	$c'_n$	$c''_n$
0	1	1	1
1	2	2	2
2	6	6	4
3	18	16	9
4	52	43	20
5	[150,154]	[96,129]	45
6	[450,462]	[258,387]	112
7	[1302,1386]	[688,1161]	[236,292]
8	[3780,4158]	[1849,3483]	[472,773]
9	[11340,12474]	[4128,10449]	[1008,2075]
10	[32864,37422]	[11094,31347]	[2240,5632]
11	[95964,112266]	[29584,94041]	[5040,15425]
12	[287892,336798]	[79507,282123]	[12544,42569]
13	[837850,1010394]	[175504,846369]	[26432,118237]
14	[2458950,3031182]	[477042,2539107]	[52864,330222]
15	[7376850,9093946]	[1272112,7617321]	[112896,926687]
$\to \infty$	${}[3^{n-O(\sqrt{\log n})}, o(3^n)]$	${}[\Omega(\frac{3^n}{\sqrt{n}}), o(3^n)]$	${}[(2.21\ldots)^n, O(\frac{3^n}{n})]$

green – obtained via the inequality (1)
orange – obtained via the inequality (2)
lavender – uses the inequality $c''_n \leq (3c''_{n-1}+1)/(1 + c''_{n-1}/3^{n-1})$

— V. Szemeredi’s proof of Roth’s theorem —

Szemeredi provided a short proof of Roth’s theorem by purely combinatorial means, and also famously proved the full case of Szemeredi’s theorem by much more intricate combinatorial argument. Both arguments are based on the density increment method. In the setting of ${}[3]^n$ , the density increment method revolves around the critical density $\alpha = \lim_{n \to \infty} c_n / 3^n$ , which exists by (2); the density Hales-Jewett theorem is precisely the statement that $\alpha$ vanishes, so suppose for contradiction that $\alpha$ is positive.

Then one can find a line-free set $A \subset [3]^n$ of density $\alpha + o_{n \to \infty}(1)$ such that A has density at most $\alpha + o_{m \to \infty}(1)$ for every m-dimensional subspace of ${}[3]^n$ (and one can complement this lower bound with an upper bound for “most” subspaces, see Tao.100). One can also regularise the density on other sets than subspaces, see Tao.121). So, basically, the moment one gets a significant density increment on a non-trivial subspace, one is done (see Tao.120, O’Donnell.122, Tao.127).

Szemeredi’s proof of Roth’s theorem proceeds by first showing that a dense set A contains a large cube Q, and thus (if it is free of algebraic lines) must completely avoid the set $2.Q - A$ . This set contains (most of) lots of parallel subspaces and so squeezes A to have higher density on some other subspace, closing the argument. (See Tao.86, Tao.118, Tao.131)

Question V.A: Is there some way to adapt this argument to density Hales-Jewett, or at least to the corners problem? The sparsity of lines is a serious difficulty, see Tao.118, Solymosi.135.

One can at least generate lots of cubes inside A without difficulty (Tao.102, Solymosi.135), lots of combinatorial lines with two elements inside A (Tao.130, Bukh.132, O’Donnell.133, Solymosi.135), and many unorganised subspaces in the complement of A (Tao.118, Solymosi.135), but this does not seem to be enough as yet.

Question V.B: What about using the techniques from Szemeredi’s big paper on Szemeredi’s theorem? (The immediate issue is that there is a key point where one needs to regularise a graph, and the relevant graph in HJ or even for corners is far too sparse; I’ll try to clarify this at some point.)

— A note on comments —

As in the first thread, please number your comments (starting with 200, then 201, etc.) and provide a title, to assist with following the comments. (Presumably, in future projects of this type, we will use a platform that allows for comment threading; see this post for further discussion.)

100 comments

Comments feed for this article

5 February, 2009 at 6:43 pm

Lior

200. Bounds for $c''_n$

Regarding the capset problem, here is a review of known values up to $c''_5 = 45$ .

6 February, 2009 at 2:20 am

Tyler Neylon

201. Lower bounds for $c_n$

Following Jason Dyer’s suggestion, I empirically found a few more lower bounds for $c_n$ using a greedy algorithm on a bipartite graph representing combinatorial lines in ${[3]}^n$ . Starting with $n=3$ , they are: 18, 50, 140, 420, 1155, 3346, 11340, 32676.

The greedy algorithm fails to reach an optimal result beginning with $c_4$ , which has known value 52 (as noted above).

It was also interesting to observe that the resulting graph was in some sense very skewed – a few points are in many more lines than most of the points. More specifically, if $x\in \Gamma_{a,b,c}$ , then $x$ is in $2^a + 2^b + 2^c - 3$ combinatorial lines. Intuitively, most points are in the central $\Gamma$ slices, which are the least connected, and these slices “mostly” don’t share lines, hinting at why we need very dense sets to hit every line.

The source code – it’s in python – is available here:
http://thetangentspace.com/wiki/Hales-Jewett_Theorem

6 February, 2009 at 3:46 am

Tyler Neylon

202. Lower bounds for $c_n$

I made a mistake in my argument that $145 \le c_5$ in comment 83 on the original post. In that argument, if you remove the indicated points with $a=0, b=1$ to block the $0,1-$ lines in $D_n$ , the remaining set will still include the line $01\ast\ast\ast$ , for example. Sorry about the mistake.

We still know, at least, that $140 \le c_5 \le 156=3c_4$ , using the last post and $c_4=52$ .

6 February, 2009 at 7:30 am

Jason Dyer

203. Greedy algorithm

Tyler, my Python is rusty, but I am correct in assuming the code does not randomize the choice of a node to remove when there’s a tie? If that’s the case, that would be the next step.

Also, this brings up something related to Question I.B:

Question I.B.1 In what exact circumstances does the greedy algorithm fail; is there some larger structural concern besides corners and triangles?

Question I.B.2 Would it be possible to automate the program to avoid those circumstances?

6 February, 2009 at 4:16 pm

Tyler Neylon

204. Algorithms

Jason: Yes, that code is not randomized. I guess you might get better numbers by randomizing a bit, or by trying to improve on a first guess answer through some kind of residual graph technique.

Another thought is that we can find a blocking set of minimal size as a hypergraph transversal problem. I’m a little confused about how hard this problem is. In [Lund, Yannakakis], they apparently show the problem as being NP-hard to approximate:
http://portal.acm.org/citation.cfm?doid=185675.306789

On the other hand, a quick scholar.google search brings up several papers that claim to have efficient algorithms. It probably helps that we have a 3-uniform hypergraph.

If finding a minimal hypergraph transversal is feasible, that might help a lot toward question I.B. If the algorithm is simple enough, it might help generate more bounds for $c_n$ . Since it explicitly finds minimal blocking sets, it is also finding the sets considered in question I.C.

6 February, 2009 at 6:31 pm

Jason Dyer

205. Algorithms

The problem with any NP-complete results is they seem to be on general cases. Even when restricting to 3-uniform hypergraphs, our graph is a lot more symmetrical than an arbitrary one. Surely there’s something about that we can exploit?

Mathematically describing those symmetries might be an interesting exercise (although perhaps someone already has in the original 150+ comment thread).

6 February, 2009 at 7:17 pm

Terence Tao

206. Algorithms

One possible way to exploit symmetries is to work in (a,b,c) space rather than the cube ${}[3]^n$ . Indeed, note that the set of all $(a,b,c)$ with $a+b+c=n$ forms a triangular lattice of length $n+1$ , and that each triple (a,b,c) comes with a “weight” $\frac{n!}{a! b! c!}$ , which is the number of strings in ${}[3]^n$ with a 1s, b 2s, and c 3s.

Now pick some subset B of this lattice which contains no equilateral triangles $(a+r,b,c), (a,b+r,c), (a,b,c+r)$ . Then the set $\Gamma_B := \bigcup_{(a,b,c) \in B} \Gamma_{(a,b,c)}$ has no combinatorial lines, and has cardinality equal to the total weight of all the elements of B. So one now has a two-dimensional problem: maximise the total weight of a subset of the triangular lattice with no equilateral triangles.

The best bounds for $c_n$ for $n \leq 4$ all take this form. For instance, the $c_4=52$ example takes B to be the entire triangle except for $(0,0,4), (1,1,2), (0,3,1), (3,0,1), (0,4,0), (0,0,4)$ . It looks feasible to search for optimal Bs for the next few ns. Note that the set $D_n$ in the main post corresponds to excluding those $(a,b,c)$ for which $a=b \hbox{ mod } 3$ ; after excluding those, the only equilateral triangles remaining are those whose length is a multiple of 3 and so the hypergraph splits into disconnected components based on the residues of a,b,c mod 3, which should simplify things significantly.

7 February, 2009 at 12:33 am

Sune Kristian Jakobsen

207. Lower bounds for $c_n$

The algorithm in Tao.206 is very effective. I has found the following _without_ useing a computer:

For $c_5$ take $D_5$ and remove $(0,4,1), (0,5,0), (4,0,1), (5,0,0)$ . This gives a set without triangles and with 150 elements. Thus $c_5\geq 150$ , and this bound cannot be improved using the algoritm in 206.

For $c_6$ take $D_6$ and remove the permutations of $(0,1,5)$ . This gives $c_6\geq 450$ , and agian, this cannot be improved using the algorithm in 206.

7 February, 2009 at 12:40 am

none

208. proof theoretic analysis

Could it be interesting to try to prove there is NO combinatorial proof of the theorem, sort of like Kirby and Paris proved there is no PA proof of Goodstein’s theorem? I’m guessing “combinatorial proof” means one codeable in primitive recursive arithmetic, whose proof theoretic ordinal is omega**omega. So we’d try to use the Hales-Jewett theorem to prove some kind of well-ordering on those point collections, which has order type larger than omega**omega, which most interesting orderings probably would have.

7 February, 2009 at 4:07 am

Sune Kristian Jakobsen

209. Lower bound for $c_n$

Correction to 207: When I said that the bound could not be improved using the algorithm from Tao.206 I assume that triples with $a=b \hbox{ mod } 3$ had to be left out of the set. I don’t know if it can be improved without this assumption.

7 February, 2009 at 4:47 am

Sune Kristian Jakobsen

210. Algorithms

The idea in Tao.206 can only prove lower bound for $c_n$ . But perhaps it can be modified to prove the values of some $c_n$ :

Let $A\subset \Gamma_{a+r,b,c}, B\subset \Gamma_{a,b+r,c}, C\subset \Gamma_{a,b,c+r}$ . Now we want some inequality in $|A|, |B|,|C|, a, b, c, r$ that holds for every $A,B,C$ without combinatorial lines. More on this later.

Now, instead of giving each triple $(a,b,c)$ with $a+b+c=n$ the weight $\frac{n!}{a! b! c!}$ , we give it an integer weight between 0 and $\frac{n!}{a! b! c!}$ . Instead of looking for subsets of the triangular lattice with no equilateral triangles, we look for weightings where the weights of the points in each equilateral triangle obey the above inequality.

One example of such an inequality could be: $|A|+|B|+|C|\leq$ the sum of the two greatest of $\frac{n!}{(a+r)! b! c!}, \frac{n!}{a! (b+r)! c!}, \frac{n!}{a! b! (c+r)!}$ . I don’t think this inequality is strong enough, because we want to “remove” more than 1/3 of the total weight, but perhaps we can find some stronger inequalities.

7 February, 2009 at 5:06 am

DHJ — the triangle-removal approach « Gowers’s Weblog

[…] of the ensuing discussion that are most directly related to this initial proposal. Two other posts, one hosted by Terence Tao on his blog, and the other here, take up alternative approaches that emerged during the discussion. […]

7 February, 2009 at 7:16 am

Jason Dyer

211. Sequence for $c_n$

Sune.207 leaves this sequence as the last one standing in the OEIS.

At our current rate of progress I suspect we can at least get an exact value for $c_5$ , so I’d say wait a bit longer on sending our sequence in.

7 February, 2009 at 8:11 am

Jason Dyer

212. Algorithms

Here’s a summary of the different possible algorithm tracks.

1. Randomize the greedy algorithm, then run multiple times to see if any better lower bounds come out. If this doesn’t get any result that improves over Tao.206, that suggests that Tao.206 is optimal.

2. Implement Tao.206 with the dihedral group. As Sune.207 discovered this can be done well even by hand, so it might also be worth it to generate some graphics of lattices with the weights put in to let people try to solve as a puzzle — if anything in this project could be done by a non-expert, this is it.

3. Implement Tao.206 without the dihedral group. If no improvement is found then it would be worthwhile to attempt a proof that the dihedral group can *always* be removed.

4. Write a brute force confirmation algorithm that will leave no question once a $c_n$ is found that it’s exact.

7 February, 2009 at 8:56 am

Terence Tao

213. Upper and lower bounds

I added a table to the main post to reflect the progress so far on $c_n, c'_n, c''_n$ for n up to 7. (I may expand the table up to n=10 or so at some later point.)

7 February, 2009 at 9:21 am

Jason Dyer

(Meta) Quick fix: you put 1115 when it’s 1155 for $c_7$

7 February, 2009 at 9:28 am

Sune Kristian Jakobsen

214. Upper and lower bounds.

Shouldn’t the upper bound for $c_5$ be 156? And I think the next upper bounds should be higher too.

7 February, 2009 at 9:45 am

Terence Tao

Thanks for the corrections! I decided to go ahead and extend the table to n=10, though I am sure some of the bounds here could be optimised further.

7 February, 2009 at 10:13 am

Sune Kristian Jakobsen

215. Algorithm / Idea for bounding the $|A|,|B|,|C|$ in 210

This is almost a copy of 340:

In 331 Gowers gives a proof that if $\mathcal{A}$ is a antichain, $\sum_{A\in\mathcal{A}}\frac{1}{\binom n{|A|}}\leq 1$ . Using the same idea it is possible to show that if $\mathcal{A}$ is a family, that intersects every chain $\emptyset=A_0\subset A_1\subset A_2\subset\dots\subset A_n=[n]$ , then $\sum_{A\in\mathcal{A}}\frac{1}{\binom n{|A|}}\geq 1$ . Notice that when the elements of $\mathcal{A}$ is only allowed to have one of two given sizes, these two theorems are equivalent. The later theorem seems to be easier to generalize to the k=3 case, and it might be useful, at least in the 200-thread.

7 February, 2009 at 10:40 am

Sune Kristian Jakobsen

216. Algorithm.

This is almost the same as I suggested in 215, but simpler and weaker:

The chance that a random line with a 1s, b 2s, b 3s, and r wildcard intersects $A\subset \Gamma_{a+r,b,c}$ is $\frac{|A|}{\binom n{a+r,b,c}}$ . Using this and the similar for b and c we get
$\frac{|A|}{\binom n{a+r,b,c}}+\frac{|B|}{\binom n{a,b+r,c}}+\frac{|C|}{\binom n{a,b,c+r}}\leq 2$ , if $A\cup B\cup C$ doesn’t contain any lines. Still, I don’t think this inequality is strong enough. I think something stronger is true when A, B and C all are non-empty.

7 February, 2009 at 10:43 am

Frankl-Rodl’s Theorem and Variations on the Cap Set Problem: A Recent Research Project with Roy Meshulam (A) « Combinatorics and more

[…] to the density Hales-Jewett project discussed over Gowers’s blog (and even more to this thread at Tao’s blog), I decided to go ahead with […]

7 February, 2009 at 1:54 pm

Michael Peake

217. Lower bounds for c_n
Following Jakobsen.207 who used Tao.206
I got a lower bound for c_7 of 1302: Remove {016,106,052,502,151,511,160,610} from D_7.
and a lower bound for c_8 of 3780: Remove {017,107,026,206,125,215,071,701,161,611,080,800,260,620} from D_8

7 February, 2009 at 9:26 pm

Michael Peake

218. Lower bounds for c_n

It is curious that the current lower bounds for c_2, c_5 and c_8 are respectively one-third of the current lower bounds for c_3, c_6 and c_9.

I have a lower bound for c_12: 287892, built from (abc) = (A02,705,423,165,462) and permutations, with A=10);

and a lower bound for c_15 of 7376850, built from (abc) = (40B,13B,708,168,735,465,762) and permutations, with B=11.

7 February, 2009 at 10:05 pm

Terence Tao

219. Lower bounds for $c_n$

Hi Michael! I propagated your lower bounds back in n using (2), and they seem to give quite good bounds. Certainly our accuracy for $c_n$ is much superior to what we currently have for $c'_n$ or $c''_n$ .

I also like the suggestion in Jakobsen.210 to try to understand the ways in which a line-free set can intersect $\Gamma_{a+r,b,c}, \Gamma_{a,b+r,c}, \Gamma_{a,b,c+r}$ . A test problem that might be susceptible to brute force attack is the following: consider the set $S := \Gamma_{1,1,2} \cup \Gamma_{1,2,1} \cup \Gamma_{2,1,1} \subset [3]^4$ . This is the union of three groups of 12 vertices, and it contains 24 triangles, each of which meets each of the three groups in exactly one vertex, with each vertex belonging to two triangles. Now let $A \cup B \cup C$ be a line-free subset of S, where $A \subset \Gamma_{1,1,2}$ , $B \subset \Gamma_{1,2,1}$ , $C \subset \Gamma_{2,1,1}$ . The question is: what constraints are there on the triple $(|A|, |B|, |C|)$ ? A simple double counting argument shows that $|A| + |B| + |C| \leq 24$ (this is already alluded to in 210). And it is easy to see that $(|A|, |B|, |C|)$ can attain the values $(12, 12, 0), (12, 0, 12), (0, 12, 12)$ . But are these the only ways that $|A| + |B| + |C|$ can be as large as 24? If so, this suggests that the most efficient way to build line-free sets is to zero out some of the $\Gamma_{a,b,c}$ and pile all the vertices into the rest – in short, to perform the type of strategy we are already doing from 206 onwards.

8 February, 2009 at 12:13 am

Michael Peake

219. Lower bounds for c_n

I wish to correct the triples for c_12 in my previous post (see below).

I have found a way to automate construction of lower bounds,
when n is a multiple of 3.

The current lower bounds for c_{3m} are built like this,
written in terms of Tao.206’s (a,b,c):
c_3 from (012) and permutations
c_6 from (123,024) and perms
c_9 from (234,135,045) and perms
c_12 from (345,246,156,02A,057) and perms (A=10)
c_15 from (456,357,267,13B,168,04B,078) and perms (B=11)
To get the triples in each row, add 1 to the triples in the previous row; then include new triples that have a zero.

This method gives a lower bound for c_99 that is bigger than 3^98.

8 February, 2009 at 2:29 am

Michael Peake

220. Lower bounds for $c_n$

Hi Terry. An answer to your test question is that
you can keep 8 from each group of 12: Remove those, such as 0201,
whose doubled digits are in positions 1 and 3, or
positions 2 and 4. This removes all lines because the
wild-card digit has to match the digit two positions away
once in each line.

8 February, 2009 at 3:24 am

Sune Kristian Jakobsen

221. Algorithm / Upper bounds.

One way to show that the idea in 210 can _not_ work would be the following:
Find a weighting w, such that for every a,b,c and r, $a+b+c+r=n$ , there exist sets $A\subset \Gamma_{a+r,b,c}, B\subset \Gamma_{a,b+r,c}, C\subset \Gamma_{a,b,c+r}$ with $|A|=w((a+r,b,c)), |B|=w((a,b+r,c)), |C|=w((a,b,c+r))$ and no lines in $A\cup B\cup C$ , but with $\sum_{a+b+c=n} w(a,b,c) > c_n$ .

I don’t know if such a weighting exist, but in the k=2 case (Sperners theorem) it does: Let $w(a,b)=\frac{1}{3}\binom n{a,b}$ if $n/3 < a < n/2$ and 0 otherwise. Now for a given a, b and r we can choose a set A, of elements x with $x_1=2$ and a set B, of elements x with $x_1=1$ . These set are big enough, and don’t contain any lines. And the sum of the weight function is almost $\frac{2^n}{3} > \binom n{n/2}$ .

8 February, 2009 at 4:52 am

Sune Kristian Jakobsen

222. Alogrithm/ Upper bounds

The obvious generalization to the k=3 case works: Let $w(a,b,c)=\frac{1}{4}\binom n{a,b,c}$ if $a,b,c \geq n/4$ . Now we can choose a set A with elements x, such that $x_1=3$ and a set C with elements x, such that $x_1=1$ and a set B. Now $A\cup B\cup C$ don’t contain any lines.

This weight gives a density of almost ¼. So the idea in 210 won’t work for large n. Still, I think it might be interesting to look at the questions Tao asked in 219 for general a, b, c and r.

8 February, 2009 at 5:43 am

Michael Peake

223. Lower bounds of $c_n$

There is a connection between $c_4$ , $c_5$ and $c_6$ :
Of the 450 length-six sequences defined in Peake.219,
150 begin with a 1….., and 52 begin with 12…..

The same thing applies with the current lower bounds of c_7, c_8 and c_9

It also gives lower bounds of 32864 for c_10, and 837850 for c_13

8 February, 2009 at 7:36 am

Terence Tao

224. Lower bounds for $c_n$

@Peake.219: This is quite interesting. I wonder if it is possible to extract an asymptotic for the lower bound obtained by this method as $n \to \infty$ (i.e. Question II.C). It is also interesting to see that $c_n/3^n$ is really decaying very slowly as $n \to \infty$ .

It may be time to set up some sort of communal spreadsheet for all this data – I’ll have a look into this.

@Jakobsen.220: Ah well, it was worth a shot. (Note, by the way, that the bound $|A|+|B|+|C| \leq 24$ in 219 implies the sharp bound $c_4 \leq 52$ , since a line-free set must omit at least one element from $\Gamma_{0,0,4} \cup \Gamma_{1,0,3} \cup \Gamma_{0,1,3}$ and similarly for cyclic permutations; so a better understanding of when equality occurs in $|A|+|B|+|C|=24$ would lead to a classification of when one has the maximal cardinality of $c_4=52$ , which should assist with the upper bound for $c_5$ as with Jakobsen.90). [Update, Feb 8: I made an arithmetic error here, this inequality is not enough by itself to get to 52; one also needs to figure out how to relate $\Gamma_{2,0,0}$ , etc. into the mix. But the general point may still be valid.]

In light of the discussion in Gowers’ threads, it seems that the Kruskal-Katona theorem,

http://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem

is likely to be relevant here, at least for large n.

@Peake.223: Hmm. Does this mean that all of our optimal counterexamples are in fact nested (e.g. is the $c_6$ example a slice of the $c_7$ example?) This may be a transient phenomenon, but still an interesting one.

8 February, 2009 at 8:06 am

DHJ — quasirandomness and obstructions to uniformity « Gowers’s Weblog

[…] after the post entitled A combinatorial approach to density Hales-Jewett. The other two are Upper and lower bounds for the density Hales-Jewett problem , hosted by Terence Tao on his blog, and DHJ — the triangle-removal approach, which is on […]

8 February, 2009 at 8:09 am

Terence Tao

225. Spreadsheet

OK, I _think_ I’ve set up a collaborative spreadsheet at

http://spreadsheets.google.com/ccc?key=p5T0SktZY9DsU-uZ1tK7VEg

to track the current data we have for $c_n, c'_n, c''_n$ . It should be editable to anyone with a google account. It should automatically propagate the bounds (1), (2) to any new bound entered. (I also have a backup copy in case something goes wrong.) One should presumably be able to program the computations in 219 into here too. Please feel free to contribute to it.

8 February, 2009 at 1:47 pm

Jason Dyer

226. $c''_n$

Just a quick note: $c''_n$ is *not* in the OEIS.

8 February, 2009 at 6:19 pm

Michael Nielsen

227. This has perhaps already been pointed out, but there is at most one entry in the Encyclopedia of Integer Sequences consistent with what is already known about $c_n$ . That is A052979. It matches $c_n$ exactly where we already know the value, and matches the (current) bounds for at least the first fifteen entries.

8 February, 2009 at 7:05 pm

Michael Peake

227. Spreadsheet

Hi, I looked at the spreadsheet, but can’t edit it.
I logged into Google, but the Edit menu is grayed out.
Does anyone else have this problem?

8 February, 2009 at 7:05 pm

Terence Tao22

228. Edel

I’ve added the lower bound $c''_6 \geq 236$ from this paper of Edel. In this other paper of Edel, an inequality is obtained which in our notation reads

$\displaystyle c''_n \leq \frac{3c''_{n-1} + 1}{1 + c''_{n-1}/3^{n-1}}$

for $n \geq 3$ , and which thus slightly improves on (2) for this problem. I’ve updated the spreadsheet and the table accordingly.

Michael.227: oops, I didn’t set the permissions properly. I think it should be OK now…

8 February, 2009 at 8:07 pm

KS Chua

229 : $c_n$ via optimization

For HJ2, there is a well known method for expressing $c_n$ as the maximization of a quadratic polynomial over a box $D_n=[0,1]^{2^n}$ so that one can apply a continuous optimization method.

Let $G$ be a graph with vertex set given by all subsets of ${}[n]$ and let $(I,J) \in E_2$ be an edge if and only if it defines a line. Then $c_n$ is the size of a maximal independent set in $G$ .

Let $x$ be a variable vector of length $2^n$ , $x_{i_1...i_n},i_j \in \{0,1\}$ which we think
of as $x_I, I \subset [n]$ where $I=\{j: i_j=1\}$ indexing the subset of ${}[n]$ . The known quadratic programming problem defining $c_n$ is

$c_n[2]=\max_{x \in [0,1]^{2^n}} \left( \sum_{J} x_J -\sum_{ (I,J) \in E_2} x_I x_J \right).$

It just occurs to me that a similar result appears to hold for $k=3$ and in fact for all $k$ . For HJ3, let $G$ be the 3-hypergraph with vertex set as before and set $(I,J,K) \in E_3$ to be a 3-edge if and only if it is a line. $c_n$ is then the size of a maximal independent set as before.
Let

$f(x)= \sum_I x_I-\sum_{(I,J,K) \in E_3} x_Ix_Jx_K.$

The following then holds,

$c_n=\max_{x \in \{0,1\}^{2^n}}f(x)=\max_{x \in D_n}f(x)$

To check the first equality, if $V$ is an independent set in $G$ of size $k$ , set $x_J=1$ for $J \in V$ , and zero otherwise. Then $f(x)=k$ because $V$ is independent. So $c_n \le \max_{x \in \{0,1\}^{2^n}} f(x)$ . Conversely, if for some $x \in \{0,1\}^{2^n}, f(x)=k,$ and if there are triplets $x_I=x_J=x_K=1$ with $(I,J,K) \in E_3$ , we change $x_I$ to 0. This reduces $\sum x_I$ by 1 but also reduce the second term of $f(x)$ by at least one. So repeating we can find an $x \in \{0,1\}^{2^n}$ with $f(x) \ge k$ and $x_Ix_Jx_K=0$ if $(I,J,K) \in E_3$ , i.e. an independent set of size $\ge k$ . So $c_n \ge \max_{x \in \{0,1\}^{2^n}} f(x)$ . The 2nd equality follows from the maximum principle since $f$ is a square free polynomial.

So an algorithm which can always determine the maximum of a quadratic polynomial in a box will be able to determine $c_n$ but the problem is $NP$ hard. Maybe one can try to find $c_n$ this way using quadratic programming for small $n$ .

The same should hold for any $k>1$ with
$f(x)= \sum_I x_I-\sum_{(I_1,...,I_k) \in E_k} x_{I_1}...x_{I_k}.$

8 February, 2009 at 8:58 pm

Kristal Cantwell

A052979 is within the current bounds for c_n for the first 27 entries of
the spreadsheet.

8 February, 2009 at 9:38 pm

Kristal Cantwell

The sequence c_n’ matches the sequence A027994 for the first
five values and lies between the upper and lower bounds
of c_n’ as calculated in the spreadsheet for the next 23 values,
it matches the sequence A027068 for the first five values
and lies within the bounds of the next 22 values.

These are the only two sequences in the OEIS which could
possibly be equal to c_n’.

9 February, 2009 at 1:04 am

Boris

232. Can one modify Behrend construction to give lower bound on $c_n'$ ?

In a geometric line, the number of 1’s ,2’s and 3’s is $(a+t_1,b,c+t_2)$ , $(a,b+t_1+t_2,c)$ and $(a+t_2,b,c+t_1)$ respectively, where $t_1$ and $t_2$ denote the number of wildcards of the two types. In other words, if $(a,b,c)$ and $(a',b',c')$ are the first two signatures, then the third is $(a'+c-c',b,c'+a-a')$ . This is similar to when Behrend works: if one point is determined by the other two in a linear manner. Here “linear manner” is somewhat crooked, and I do not see how to apply Behrend, or any of the standard heuristics.

Hence, question: how large is the largest subset of $\{0,\dotsc,M\}^3$ not containing a configuration of the above form?

9 February, 2009 at 1:42 am

Michael Peake

232. Lower bounds of $c_n$

I have added some more lower bounds to Terry.225’s spreadsheet.
The sets of (abc) that I have used are the following for N a multiple of 3.
I think that they are triangle-free.

For N=3M-1, restrict the first digit of a 3M sequence to be 1;
For N=3M-2, restrict the first two digits of a 3M sequence to be 12.

For N<21, ignore any triple with a negative entry.

For N=6M:

(2x, 2x+2, N-4x-2) and permutations (x=0..M-4)
(2x, 2x+5, N-4x-5) and perms (x=0..M-4)
(2x, 3M-x-4, 3M+x+4) and perms (x=0..M-4)
(2x, 3M-x-1, 3M+x+1) and perms (x=0..M-4)

(2x+1, 2x+5, N-4x-6) and perms (x=0..M-5)
(2x+1, 2x+8, N-4x-9) and perms (x=0..M-5)
(2x+1, 3M-x-1, 3M-x) and perms (x=0..M-5)
(2x+1, 3M-x-4, 3M-x+3) and perms (x=0..M-5)

(N/3-7, N/3-3, N/3+10) and perms
(N/3-7, N/3, N/3+7) and perms
(N/3-7, N/3+3, N/3+4) and perms
(N/3-6, N/3-4, N/3+10) and perms
(N/3-6, N/3-1, N/3+7) and perms
(N/3-6, N/3+2, N/3+4) and perms
(N/3-5, N/3-1, N/3+6) and perms
(N/3-5, N/3+2, N/3+3) and perms
(N/3-4, N/3-2, N/3+6) and perms
(N/3-4, N/3+1, N/3+3) and perms
(N/3-3, N/3+1, N/3+2) and perms
(N/3-2, N/3, N/3+2) and perms
(N/3-1, N/3, N/3+1) and perms

For N=6M+3:

(2x, 2x+4, N-4x-4) and perms, x=0..M-3
(2x, 2x+7, N-4x-7) and perms, x=0..M-3
(2x, 3M+1-x, 3M+2-x) and perms, x=0..M-3
(2x, 3M-2-x, 3M+5-x) and perms, x=0..M-3

(2x+1, 2x+3, N-4x-4) and perms, x=0..M-4
(2x+1, 2x+6, N-4x-7) and perms, x=0..M-4
(2x+1, 3M-x, 3M-x+2) and perms, x=0..M-4
(2x+1, 3M-x-3, 3M-x+5) and perms, x=0..M-4

9 February, 2009 at 3:38 am

Gil

Even if we are tentatively happy about the bounds (like (6)) based on AP free sets for k=3. Regarding problem II.b for higher k’s it looks we should be able to do much better (than just replacing Behrend by the examples for larger k).

At least this is suggested by the way our bound changes between the k=2 case and the k=3 case.

E.g we can try something like this: map words of length n in an alphabet of 4 letters to words in 3 letters. Say with one letter a representing 1 or 2 letter b representing 2 or 3 and letter c representing 3 or 4.

Then try to find a large set of letters in a b and c whose preimage will automatically exclude a combinatorial line of length 4.

9 February, 2009 at 7:55 am

Jason Dyer

(Meta)

Kirstal, Terry’s original post already specified this sequence is $c'_n$ .

9 February, 2009 at 8:12 am

Jason Dyer

234. $c_n$ via optimization

Regarding Chua.229, shouldn’t that be $3^n$ rather than $2^n$ in the k=3 version of the algorithm? (Otherwise I’m confused how the indexing works.)

It looks like this could be the best algorithm to get exact values of $c_n$ , although the algorithm is elaborate enough I would be worried about the integrity of the code. Is there at least some implementation for k=2 out there already?

9 February, 2009 at 8:27 am

Boris

235.

I want to just add that if we restrict the triple $(a,b,c)$ to lie in a Cartesian product $A\times A\times A$ , then “crookedness” disappears and we end up with system of three linear equations in nine variables, whose solutions we want to avoid in $A$ . For the next few hours I will not have the time to try adapting Behrend to this setting though.

9 February, 2009 at 1:44 pm

Boris

236. Restriction to Cartesian products is too rough of a proposal. It does not even work for corners. Indeed the points $(x,y), (x+r,y), (x,y+r)$ have four distinct coordinates among them, $x_1=x_2, x_2=x+r, y_1=y, y_2=y+r$ . They are linked by the equation $x_2-x_1=y_2-y_1$ . The largest set avoiding solutions to this equation has size $\sqrt{n}(1+o(1))$ (this equation usually goes by the name of Sidon equation, and is extremely well-studied).

Similarly, straightforward implementation of my proposal in 235 gives the equation $y_2-x_2=y_3-x_1=y_1-x_3$ where $x_1=a, x_2=a', y_1=c, y_2=c', x_3=a'+c-c', y_3=c'+a-a'$ . Pigeonhole principle tells us that the largest solution-free set is of size $O(\sqrt{n})$ .

The question remains: is there a Behrend-type construction?

9 February, 2009 at 4:56 pm

Terence Tao

237.

Boris, this was discussed a little bit in 43, 48 of the original thread. The basic problem is the $t_1=t_2$ case (in the notation of your 232) when two of the points on the crooked line coincide. It basically means that one cannot have more than one point on any line $c-a = const$ . Conversely, any configuration with this property will be free of crooked lines, which I guess is what leads to the known $3^n/O(\sqrt{n})$ lower bound.

A subproblem may be to work out whether one can find denser sets on the set $\bigcup_{c-a=const} \Gamma_{a,b,c}$ that are free of geometric lines than just a single $\Gamma_{a,b,c}$ , and have a better density than $1/\sqrt{n}$ asymptotically. If so, then we can glue together such sets as $const$ ranges over a Behrend set and get a competitive example.

9 February, 2009 at 8:01 pm

Michael Peake

238. Lower bounds of $c_n$

The pattern I described in My.232 has a slight error
when N=6M+3, as x ranges from 0 to M-4, not M-3.

This pattern, for N a multiple of 3, leaves no room for any more points – any new point would complete a line.

I don’t know the asymptotic for this pattern’s value of c_n/3^n, but
2.7 sqrt(log(n)/n) is a good fit when n is between 4000 and 10000

9 February, 2009 at 9:25 pm

KS Chua

239. $c_n$ by optimization.

Sorry I made a mistake in 229. The box should be ${}[0,1]^{3^n}$
for $k=3$ instead of $2^n$ as Jason Dyer noted. Also for
$k>2$ it is no longer a QP problem and one needs a general
optimization routine.

10 February, 2009 at 3:56 am

Tyler Neylon

240. Algorithms

I think finding a minimum-sized hypergraph transversal in NP-hard, even for 3-uniform hypergraphs.

We can reduce 3-SAT to this problem. We are given a boolean expression $\phi_1\wedge\phi_2\wedge\ldots\wedge \phi_k$ where each $\phi_i$ is the OR of 3 terms, each term either a boolean value from $(x_i)_{i=1}^m$ , or the negation thereof. Form a hypergraph with vertices $x_1, \neg x_1, x_2, \neg x_2, \ldots$ , and each $\phi_i$ as a hyperedge. Add a dummy node $x_j'$ , and a hyperedge $(x_j, \neg x_j, x_j')$ for each boolean value. These last hyperedges ensure there is no smaller solution than the one corresponding to a satisfying boolean assignment, if one exists. It’s not hard to check that a minimum transversal is size $m$ (the number of boolean values) iff there is a satisfying assignment; this completes the reduction.

What does this mean for us? If we want a polynomial time algorithm (in the size of the graph), we have to use more of the structure than just the fact that every line has 3 points, assuming $NP\not\subset P$ . Also recall that the size of our graph itself is already exponential in n.

10 February, 2009 at 10:06 am

Michael Peake

241. Upper bound for $c_5 < 156$

This proof is along the lines of Sune.90
Sune shows there is just one way to place 18 points in a cube,
and that at most 52 points fit in $3^4$

Suppose 156 points may be chosen in $3^5$ .
There must be 52 points in each slice of $3^4$

Divide $3^5$ into nine cubes. There are 17 or 18 points in each cube, and one cube in each row and column has 18 points. For example

17, 17, 18
18, 17, 17
17, 18, 17

Cut the cubes further, into squares. The 18-point cubes must cut into three six-point slices x y and z, but the 17-point squares have more variation

pqr, stu, xyz
xyz, abc, def
ghk, xyz, lmn

Take the three cubes in the top row, and slice them along a different axis so they are psx, qty and ruz.
One of these cubes has 18 points, and so is xyz; so r=x and u=y.

Similar logic in second column gives u=x and c=y. So there is a contradiction.

There are four other ways to place the 17-point and 18-point cubes, but they all lead to contradictions.

So 156 points can’t be placed in $3^5$

10 February, 2009 at 11:39 am

Terence Tao

242. $c_5 < 156$

Michael: Nice! I’ve updated the spreadsheet and the table accordingly. Computing $c_5$ exactly may well be within reach now.

10 February, 2009 at 9:53 pm

Michael Peake

3^5. $c_5 < 155$

The same proof works for 155 points, except for the case

17 17 18
17 17 17
18 17 17

and permutations of that. I can assume that, when sliced along
any axis, each cube has at least 17 points.

Cut the cubes into slices as in Michael.240.
Some of the slices must be x,y or z, as shown there

pqx rsy xyz
tuy abc yde
xyz yfg zhk

When the pqx cube is cut into squares along any of its three axes,
it has an x slice in third position. That forces the placement of
thirteen points in the cube, and needs four points to be
placed in the remaining 2x2x2 sub-cube. It turns out that pqx is either
yz’x or y’zx, where z’ is a z slice with one point removed.

If pqx = yz’x when sliced along one axis, then it is yz’x when sliced
along all three axes. Then the cube paz, from reslicing the diagonal,
is yaz along all three axes, which is impossible.

So pqx = y’zx when sliced along each axis, and rsy=tuy=zx’y

For the same reasons, zhk = zxy’

So cube qbh = zbx along all three axes, which is impossible.

I think this contradiction completes the proof.

10 February, 2009 at 10:09 pm

Michael Peake

244. $c_5 < 155$

In 243., I made an error in the paragraph that begins “If pqx = yz’x”.
I just need the fact that a can’t have five points if yaz has no lines.
Also, at the end, b can’t have five points if zbx has no lines.

11 February, 2009 at 5:25 am

Michael Peake

245. $c_5 < 155$

Recall that there is just one pattern to fit 18 points in a cube;
the three square slices of this pattern (along any axis) are x, y and z.

To fit 17 points in a cube, the only way is to remove one point from
either xyz, yzx or zxy.

This makes the proof in 243. easier because the slices are formed
by removing points from

yzx zxy xyz
zxy xyz yzx
xyz yzx zxy

Now the major diagonal of the cube is yyy, and six points must be removed from that. Four of the off-diagonal cubes must also lose points. That leaves 152 points, which contradicts the 155 points we started with.

11 February, 2009 at 9:46 am

Terence Tao

246. $c_5 < 155$

Great! I’ve updated the table again (I see that the spreadsheet was already updated, excellent).

It would be interesting to see what the 150 lower bound example looks like in xyz notation, this may clarify what needs to be done to narrow the upper and lower bounds further.

11 February, 2009 at 12:46 pm

Kristal Cantwell

247. Let us look at the set of 150
points which form the lower
bound for c_5
It would consist of all points whose sum is not zero mod 3 with
all points with 5 coordinates equal to 1 or or all 5 points equal to 2 removed
combined with removal of all points
with one coordinate equal to 3 and the rest equal to
1 and the removal of all points with one coordinate
equal to 3 and the rest equal to 2

This gives the following
17 17 18
18 14 17
14 18 17

which gives let u equal x with one point removed
v = y with one point removed
and t =z with one point removed
uyz xvz xyz
xyz ??? xvz
??? xyz uyz
Note we have chosen three coordinates to be within
the cube and two other to determine
the position of the cube within the square
coordinates go from
one to three from left to right
and one to three upwards
xyz are squares determined
by one of the coordinates of the
cube. x (or any letter in the leftmost position)
corresponds to the
the square with coordinate equal
to one the letters in the next two positions correspond
to the squares with the coordinate equal to 2 and 3.
The question marks are for the cubes with 14 points. Are there problems with
having all the cubes having a value that is close to 18?
Is there a set of points having no combinatorial lines
with 5 coordinates varying from 1 to 3 such
that all of the cubes have value 17 or 18?

11 February, 2009 at 1:22 pm

Terence Tao

248. Conventions for xyz notation

I think it will be helpful to fix the conventions for the xyz notation. If we use Cartesian coordinates

13 23 33
12 22 32
11 21 31

to parameterise ${}[3]^2$ , then (if I understand Michael’s posts correctly), x is the six-element set

* _ *
* * _
_ * *

(where * denotes elements of x and _ denotes non-elements), y is the six-element set

_ * *
* _ *
* * _

and z is the six-element set

* * _
_ * *
* _ *

and xyz is the unique 18-element line-free set in ${}[3]^3$ (with the convention that abc is the set whose first slice is a, second slice is b, and third slice is c).

Michael, does this match your conventions?

Also, when you say “to fit 17 points on the cube, the only way is to remove one point from xyz, yzx, or zxy”, are there some restrictions on what point one can remove? Clearly one can remove any point one wishes from xyz, but there seems to be more constraints for yzx and zxy.

11 February, 2009 at 1:41 pm

Terence Tao

249. A hyper-optimistic conjecture from 400-499

Over at the 400-499 thread, Gil Kalai.455 and Tim Gowers.459 have proposed a “hyper-optimistic” conjecture, and asked whether it could be falsified using the examples from this thread. Let me rephrase it as follows. Given a set $A \subset {}[3]^n$ , define the weighted size $\mu(A)$ of A by the formula

$\mu(A) := \sum_{a+b+c=n} |A \cap \Gamma_{a,b,c}|/|\Gamma_{a,b,c}|$

thus each slice $\Gamma_{a,b,c}$ has weighted size 1 (and we have been referring to $\mu$ as “slices-equal measure” for this reason), and the whole cube ${}[3]^n$ has weighted size equal to the $(n+1)^{th}$ triangular number, $\frac{(n+1)(n+2)}{2}$ .

Example: in ${}[3]^2$ , the diagonal points 11, 22, 33 each have weighted size 1, whereas the other six off-diagonal points have weighted size 1/2. The total weighted size of ${}[3]^2$ is 6.

Let $c^\mu_n$ be the largest weighted size of a line-free set. For instance, $c^\mu_0 = 1$ , $c^\mu_1 = 2$ , and $c^\mu_2 = 4$ .

As in the unweighted case, every time we find a subset B of the grid $\Delta_n := \{ (a,b,c): a+b+c=n\}$ without equilateral triangles, it gives a line-free set $\Gamma_B := \bigcup_{(a,b,c) \in B} \Gamma_{a,b,c}$ . The weighted size of this set is precisely the cardinality of B. Thus we have the lower bound $c^\mu_n \geq \overline{c}^\mu_n$ , where $\overline{c}^\mu_n$ is the largest size of equilateral triangles in $\Delta_n$ .

Hyper-optimistic conjecture: We in fact have $c^\mu_n = \overline{c}^\mu_n$ . In other words, to get the optimal weighted size for a line-free set, one should take a set which is a union of slices $\Gamma_{a,b,c}$ .

This conjecture, if true, will imply the DHJ theorem (see the 400-499 discussion for details). Note also that all our best lower bounds for the unweighted problem to date have been unions of slices. Also, the k=2 analogue of the conjecture is true, and is known as the LYM inequality (in fact, for k=2 we have $c^\mu_n = \overline{c}^\mu_n = 1$ for all n).

If the conjecture is false, then perhaps this will be visible by computing upper and lower bounds for $c^\mu_n, \overline{c}^\mu_n$ for small n. By hand I can check that $\overline{c}^\mu_n = c^\mu_n$ for n=0,1,2… but perhaps with all the above progress we can also get good bounds for n=3,4,5?

11 February, 2009 at 4:25 pm

Tyler Neylon

250. A hyper-optimistic conjecture

Could someone clarify the definition of $\bar c_n^\mu$ ?

As far as generalizations of LYM go, let $d_{abc} = |A\cap \Gamma_{a,b,c}|$ , and suppose $\sum_{a+b+c=n} d_{abc}/|\Gamma_{a,b,c}| \le f(n)$ for all line-free $A$ . Then Michael’s examples seem to suggest $f(n)$ grows quickly – as opposed to $f(n) = 1$ in LYM – so, intuitively, how do we hope for something like LYM?

I don’t think this is exactly what’s needed, but we do have $\sum_{a+b+c=n} d_{abc}p_{abc} \le 2$ where $p_{abc} = (2^a+2^b+2^c-3)/(4^n-3^n)$ is the percent of lines passing through any single element of $\Gamma_{a,b,c}$ .

11 February, 2009 at 4:45 pm

Terence Tao

251. A hyper-optimistic conjecture

One can define $\overline{c}^\mu_n$ in two equivalent ways. One of them is that it is the largest weighted size $\mu(A)$ of a line-free set $A \subset [3]^n$ which is the union of slices $\Gamma_{a,b,c}$ . (This is in contrast to $c^\mu_n$ , which is the largest weighted size of any line-free set, not necessarily the union of slices.)

Another equivalent definition is that $\overline{c}^\mu_n$ is the largest subset of the triangular grid $\Delta_n := \{ (a,b,c) \in {\Bbb Z}_+^3: a+b+c=n \}$ which contain no equilateral triangles. For instance, by deleting the two points (0,0,2) and (1,1,0) from $\Delta_3$ one removes all triangles, whereas removing one point is not enough, and so $\overline{c}^\mu_2 = 4$ .

As for your second question, I don’t think we have yet a strategy for this, but one could imagine some sort of extremal combinatorics argument by showing that a line-free set which is not a union of slices can be “improved” to increase its weighted size, without losing the line-free property. Showing this rigorously, though, would be, well, hyper-optimistic.

(Incidentally, what you call f(n) would be what I would call an upper bound for $c^\mu_n$ .)

11 February, 2009 at 7:15 pm

Jason Dyer

252. Hyper-optimist conjecture

Am I understanding this right?

Minimal deletion for $\Delta_3$ removes (0,3,0) (0,2,1) (2,1,0) (1,0,2), leaving 6 points. So $\overline{c}^\mu_3=6$ ?

11 February, 2009 at 7:48 pm

Terence Tao

253.

Well, that certainly makes the set triangle-free, so $\overline{c}^\mu_3 \geq 6$ . If you know that you cannot make $\Delta_3$ triangle-free by removing only three points, then yes, $\overline{c}^\mu_3$ would equal 6.

11 February, 2009 at 8:12 pm

Jason Dyer

254. Proof $\Delta_3$ cannot be triangle free removing only 3 points

Yes, with only three removals each of these (non-overlapping) triangles must have one removal:
set A: (0,3,0) (0,2,1) (1,2,0)
set B: (0,1,2) (0,0,3) (1,0,2)
set C: (2,1,0) (2,0,1) (3,0,0)

Consider choices from set A:
(0,3,0) leaves triangle (0,2,1) (1,2,0) (1,1,1)
(0,2,1) forces a second removal at (2,1,0) [otherwise there is triangle at (1,2,0) (1,1,1) (2,1,0)] but then none of the choices for third removal work
(1,2,0) is symmetrical with (0,2,1)

12 February, 2009 at 12:49 am

Michael Peake

255.

Krystal.247: I think my 245 shows that, if all the cubes
have 17 or 18 points, then you have to delete ten points from
a full 9×18 pattern of xs, ys and zs. That leaves 152 points,
which is less than 9*17. So at least one cube has to have
16 or fewer points.

Another pattern of 150 points is this: Take the 450 points
in ${}[3]^6$ which are $(1,2,3), (0,2,4)$ and permutations,
then select the 150 whose final coordinate is 1. That gives
this many points in each cube:

17 18 17
17 17 18
12 17 17

Terry.248: Yes, that matches what I meant by x,y and z;
yzx and zxy have a full line on the cube’s major diagonal
so you have to remove one of those three points to leave
a valid seventeen points.

12 February, 2009 at 7:32 am

Jason Dyer

256. Hyper-optimist conjecture

The $\overline{c}^\mu_3$ case was originally proposed as a puzzle by Kobon Fujimura (who is best known for <a href=”Kobon Triangles).

I have been searching the recreational mathematics literature for any other mention of our problem but I haven’t found a reference.

12 February, 2009 at 7:51 am

Jason Dyer

(Meta) Coin puzzles

Fujimura’s version of $\overline{c}^\mu_3$ is simply given a pyramid of 10 coins, what is the smallest number you need to remove so there are no equilateral triangles?

The most common type of coin puzzle (which goes back to Dudeney) involves changing one configuration of coins into another with a certain number of moves. For example, invert a pyramid of 10 coins in the smallest number of moves.

This article from the (highly recommended book) Games of No Chance analyzes this type of puzzle in detail.

12 February, 2009 at 10:46 am

Sune Kristian Jakobsen

257. $\overline{c}^\mu_n$

$\overline{c}^\mu_4=9$ :
The set of all (a,b,c) in $\Delta_4$ with exactly one of a,b,c =0, has 9 elements and doesn’t contain any equilateral triangles.

Let $S\subset \Delta_4$ be a set without equilateral triangles. If $(0,0,4)\in S$ , there can only be one of (0,x,4-x) and (x,0,4-x) in S for x=1,2,3,4. Thus there can only be 5 elements in S with a=0 or b=0. The set of element with a,b>0 is isomorph to $\Delta_2$ , so S can at most have 4 elements in this set. So $|S|\leq 4+5=9$ . Similar if S contain (0,4,0) or (4,0,0). So if $|S| >9$ S doesn’t contain any of these. Also, S can’t contain all of (0,1,3), (0,3,1), (2,1,1). Similar for (3,0,1), (1,0,3),(1,2,1) and (1,3,0), (3,1,0), (1,1,2). So now we have found 6 elements not in S, but $|\Delta_4|=15$ , so $S\leq 15-6=9$ .

12 February, 2009 at 11:32 am

Sune Kristian Jakobsen

258. $\overline{c}^\mu_n$

$\overline{c}^\mu_5=12$ :
The set of all (a,b,c) in $\Delta_5$ with exactly one of a,b,c=0 has 12 elements and doesn’t contain any equilateral triangles.

Let $S\subset \Delta_5$ be a set without equilateral triangles. If $(0,0,5)\in S$ , there can only be one of (0,x,5-x) and (x,0,5-x) in S for x=1,2,3,4,5. Thus there can only be 6 elements in S with a=0 or b=0. The set of element with a,b>0 is isomorph to $\Delta_3$ , so S can at most have 6 elements in this set. So $|S|\leq 6+6=12$ . Similar if S contain (0,5,0) or (5,0,0). So if $|S| >12$ S doesn’t contain any of these. S can only contain 2 point in each of the following equilateral triangles:
(3,1,1),(0,4,1),(0,1,4)
(4,1,0),(1,4,0),(1,1,3)
(4,0,1),(1,3,1),(1,0,4)
(1,2,2),(0,3,2),(0,2,3)
(3,2,0),(2,3,0),(2,2,1)
(3,0,2),(2,1,2),(2,0,3)
So now we have found 9 elements not in S, but $|\Delta_5|=21$ , so $S\leq 21-9=12$ .

12 February, 2009 at 1:03 pm

Christian Elsholtz

259 About the constant c”(n): the value of c”(6)=112 has been proved by
Aaron Potechin: Maximal caps in AG (6, 3)
Journal Designs, Codes and Cryptography, Volume 46, Number 3 / March, 2008
http://www.springerlink.com/content/h003577g11112308/

This gives a new set of slightly improved upper bounds: for n=7 to 15 as follows:

{7, 292}, {8, 773}, {9, 2075}, {10, 5632}, {11, 15425},
{12, 42569}, {13, 118237}, {14, 330222}, {15, 926687}

A discussion of the problem on caps, with plenty of references, can also
be found in:
Yves Edel, Christian Elsholtz, Alfred Geroldinger, Silke Kubertin, Laurence Rackham: Zero-sum problems in finite abelian groups and affine caps.
Quarterly Journal of Mathematics 58 (2007), 159-186.
http://qjmath.oxfordjournals.org/cgi/content/abstract/58/2/159

12 February, 2009 at 1:29 pm

Jason Dyer

260. $\overline{c}^\mu_n$

Sune, could you give your explicit list for removals from $\overline{c}^\mu_4$ ? I am unable to reproduce a triangle-free configuration from your description.

For example, (4,0,0) (0,4,0) (0,0,4) (2,1,1) (1,1,2) (1,2,1) leaves the triangle (2,2,0) (0,2,2) (2,0,2).

12 February, 2009 at 1:30 pm

Terence Tao

260. Updates to spreadsheet

I’ve updated the spreadsheet to take into account the above developments (in particular, adding entries for upper and lower bounds for $c^\mu_n$ and $\overline{c}^\mu_n$ . I’m using the trivial bounds

$\overline{c}^\mu_n \leq \overline{c}^\mu_{n+1} \leq \overline{c}^\mu_n + n+1$

and

$\overline{c}^\mu_n \leq c^\mu_n \leq |\Delta_n| = \frac{(n+1)(n+2)}{2}$

but clearly we should be able to do better than these bounds.

12 February, 2009 at 1:56 pm

Jason Dyer

261. Lower bound for $\overline{c}^\mu_n$

One easy lower bound is to note that one can always go triangle free by removing (n,0,0), the triangle (n-2,1,1) (0,n-1,1) (0,1,n-1), and all points on the edges of and inside the same triangle.

For example, with $\overline{c}^\mu_4$ remove (0,4,0), (1,2,1), (2,1,1), (1,1,2), (3,0,1), (2,0,2), and (1,0,3).

Therefore a lower bound would be $\frac{(n+1)(n+2)}{2}-1-\frac{(n-1)(n)}{2}$ . (That is, the triangular number of n+1 with (n,0,0) removed and then the triangular number of n-1 removed, referring to the triangle (n-2,1,1) (0,n-1,1) (0,1,n-1).)

12 February, 2009 at 4:46 pm

Michael Peake

262. Three solutions for $c_4$

There are exactly three solutions for 52 points in ${}[3]^4$
I use recent notation from $c_5$ , x, y and z defined in Terry.248

x’ is x with one point removed; that point in ${}[3]^4$ is either 2222 or 3333. Likewise for y’ and z’

All three solutions are made from full $latex Gamma_{abc}
Each row is a different solution.

xyz yz’x zxy’
y’zx zx’y xyz
z’xy xyz yzx’

12 February, 2009 at 6:27 pm

Jason Dyer

263. Finishing the calculations

I guess that’s what I get for typing and running — the bound at 261 is just 2n.

Also, 254 the proof can be much, much simpler: just note (3,0,0) or something symmetrical has to be removed, leaving 3 triangles which do not intersect, so 3 more removals are required.

12 February, 2009 at 8:04 pm

Michael Peake

264. Lower bound for $\overline{c}^\mu_n$

Another lower bound is 3(n-1), as you keep most of all three sides of the triangle. Remove the corners and the inner triangle.

12 February, 2009 at 8:23 pm

Jason Dyer

265. Lower bound for \overline{c}^mu_n

Michael, I have a counterexample for that at 260.

12 February, 2009 at 8:44 pm

Terence Tao

266. Wiki

We’ve started up a wiki for the polymath project at

http://michaelnielsen.org/polymath1/index.php?title=Main_Page

I’ve put in a page for the proofs of the best bounds for c_n for small n at

http://michaelnielsen.org/polymath1/index.php?title=Upper_and_lower_bounds

The last few sections still need some work. Of course, everyone is invited to contribute. (For lengthy new computations, it may be best to put the details on the wiki and announce an abridged version here.)

At some point I’ll try to do something similar for $\overline{c}^\mu_n$ .

12 February, 2009 at 8:52 pm

Michael Peake

266. Lower bound for $\overline{c}^\mu_4$

You can fit nine points in a 15-point triangle (n=4),
(013,022,031,103,202,301,130,220,310)
but the best result for $c_4$ only uses seven points.
(022,112,121,202,220,310,301)

12 February, 2009 at 9:04 pm

Michael Peake

267. Lower bound for $\overline{c}^\mu_n$

Jason,

The triangle made up by (2,2,0),(2,0,2) and (0,2,2) is upside down.
It has a constant r=-2, so doesn’t apply to HJ sequences, which
use r as a number of columns.

I think you were right the first time, in 254., to do the long-winded proof.

12 February, 2009 at 9:12 pm

Terence Tao

268. Wiki

Here is a page for $\overline{c}^\mu_n$ , the computation of which I have dubbed “Fujimura’s problem”:

http://michaelnielsen.org/polymath1/index.php?title=Fujimura%27s_problem

Again, some cleanup is required to convert the blog comments into wiki format and to integrate the text smoothly.

12 February, 2009 at 10:49 pm

Michael Peake

269. Upper limit for $\overline{c}^\mu_n$

From looking at triangles in the lowest two rows, we have

$c_n \leq c_{n-2} + \frac{3n+2}{2}$

12 February, 2009 at 11:29 pm

Michael Peake

270. Hyper-optimistic

My point in 266. was, does that contradict the hyper-optimistic conjecture?

13 February, 2009 at 4:25 am

Michael Peake

271. Upper limit for Fujimura ( $\overline{c}^\mu_n$ )

There are $\binom{n+2}{3}$ triangles, and each point is in n of them, so you must remove at least (n+2)(n+1)/6 points to remove all triangles.
So an upper limit for $\overline{c}^\mu_n$ is (n+1)(n+2)/3.

13 February, 2009 at 7:39 am

Terence Tao

272. Hyper-optimistic

Dear Michael, it’s not clear yet whether this example violates the hyper-optimistic one, because the extremiser for the $c_4$ problem is not going to be the extremiser for the $c^\mu_4$ problem. Indeed, the $c_4$ example, involving only seven of the slices, will have a weighted size of 7, whereas the $\overline{c}^\mu_4$ example has a weighted size of 9. To contradict the conjecture we would need to find a line-free set in ${}[3]^4$ with a weighted size exceeding 9.

Incidentally, I found the lower bound $\overline{c}^\mu_{n+1} \geq \overline{c}^\mu_n + 2$ for $n \geq 2$ , since one can always take an extremiser in $\Delta_n$ , add a new edge to the triangular grid and put two points on it so that the triangle these two points generate doesn’t have the third point in the extremiser.

Given how this thread is filling up, I will probably start a fresh thread in a day or so. The wiki is very helpful in this regard, it reduces the extent to which I will have to summarise all the progress…

13 February, 2009 at 7:49 am

Jason Dyer

272. When r<0

re: Peake.267, yes, I see now. I don’t remember r ever being defined as positive so I never thought about the case. (2,0,2) (2,2,0) (0,2,2) would be 1133, 1122, and 2233 which form no combinatorial lines.

That does bring the interesting question of: is there anything important about this problem relating to the cases of r<0? They might affect the “subcubes” from O’Donnell.422 which seem to be working with “partial” combinatorial lines. Calling the points a, b and c: a and b form a partial combinatorial line, b and c do, and a and c do, but a, b, and c do not form a line together. I believe this situation may be unique for the r<0 case.

Also, it means there are two variants of Fujimura, and while r<0 doesn’t apply to our problem it might be worth looking into as a side project (or at least noting it as a separate case).

13 February, 2009 at 8:48 am

Sune Kristian Jakobsen

273.

Michael.219: “This method gives a lower bound for c_99 that is bigger than 3^98.” and
Terry.467: “We also have an example of a subset of ${}[3]^{99}$ of density $>1/3$ that still has no combinatorial line.”

Then why is c_96/3^96=0.006155058319549. Shouldn’t it be >1/3?

13 February, 2009 at 8:49 am

Sune Kristian Jakobsen

273b

The number I mentioned is L98 in the spreadsheet: Lower bound for $c_96/3^96$

13 February, 2009 at 12:04 pm

Kristal Cantwell

The two examples we have for a lower bound for c_5 being 150 have cubes with 14 and 12 points is there an example with all cubes 16 or higher
and total 150 or higher? Or failing that all cubes 15 or higher and total 150 or higher?

13 February, 2009 at 4:14 pm

Thomas Sauvaget

275. $c_5=154$ : an example

Inspired by the previous discussion, I think I’ve found an example showing that $c_5=154$ , I’d be grateful if someone could check it.

I’m using slightly different notations: instead of cartesian coordinates I’m using left-to-right ordering of words recursively to make visualisation easy. Namely, when $n$ is even increase upwards, when $n$ is odd increase righwards. In this way we can deal with 2-dimensional patterns only. For example ${}[3]^3$ looks like this:
131 132 133 231 232 233 331 332 333
121 122 123 221 222 223 321 322 323
111 112 113 211 212 213 311 312 313

Given those notations here is what I think is a 154-element line-free pattern in ${}[3]^5$ :

The bottom-left black element is 11111 (not in the set), and so on. The two lone red elements are removed (Michael’s idea, here these are 12222 and 13333), then I found that removing the 6 other red elements leads to a line-free set (note that these 6 red elements are all on a super-diagonal). Total is thus $(9\times 6 -2)+(9\times 6 -3)+(9\times 6 -3)=52+51+51=154$ . This would also fit with the OEIS sequence A052979 mentionned above.

I’ve built the example recursively by matching lower conditions starting from the bottom left $3\times 3$ square, first killing straight lines then diagonals, then doing the same with the other $3\times 3$ squares from ${}[3]^4$ . In fact there is still some freedom in the pattern: the two squares I’ve circled with blue could have any of the 3 elementary $3\times 3$ patterns, but here I’ve chosen the most symmetric ones.

It seems that this construction is fairly topological and systematic, it may well be possible to get an explicit recursive formulation, and thus a formula for estimating $c_n$ . I’ll try to come back to it if indeed the example is correct.

13 February, 2009 at 5:07 pm

Terence Tao

276: $c_5 = 154$

Dear Thomas,

It unfortunately seems to me that the bottom row of the middle ${}[3]^4$ contains some horizontal lines (e.g. the three centres of the three ${}[3]^2$ ‘s in this bottom row). There are also some lines on the top row and on the left and right columns of this middle ${}[3]^4$ .

(If you write each of the ${}[3]^2$ ‘s in xyz notation, one sees the problem; there are a bunch of rows and columns which only have two of the three patterns x, y, z and so let some lines slip in. The ${}[3]^2$ ‘s with three red squares in them are the intersection of two of the x, y, z and can kill more lines, but unfortunately this doesn’t cover all the possible lines.)

But it could be that some permutation of this sort of strategy could work… it may provide the first good example we have which is not based off of the $D_n$ set.

13 February, 2009 at 8:13 pm

Bounds for the first few density Hales-Jewett numbers, and related quantities « What’s new

[…] 2009 in math.CO | Tags: polymath1 | by Terence Tao This thread is a continuation of the previous thread here on the polymath1 project. Currently, activity is focusing on the following […]

13 February, 2009 at 8:14 pm

Terence Tao

277. Thread moving

As this thread is beginning to get quite long, I am moving it to a new thread, starting at 700:

https://terrytao.wordpress.com/2009/02/13/bounds-for-the-first-few-density-hales-jewett-numbers-and-related-quantities/

14 February, 2009 at 12:24 am

Michael Peake

277. lower bound of $c_n$

I tried a pattern of points based on Terry.39’s suggestion. It seems to give asymptotic results similar to what he thought.

First define a sequence, of all positive numbers which, in base 3, do not contain a 1. Add 1 to all multiples of 3 in this sequence. This sequence does not contain a length-3 arithmetic progression.

It starts 1,2,7,8,19,20,25,26,55, …

Second, list all the (abc) triples for which the larger two differ by a number
from the sequence, excluding the case when the smaller two differ by 1, but then including the case when (a,b,c) is a permutation of N/3+(-1,0,1)

This had numerical asymptotics for $\log(c_n/3^n)$ close to
$latex 1.2-\sqrt(\log(n)) between n=1000 and n=10000

Sune.273: Sorry, I haven’t written all the numbers in yet for my pattern – I am only up to 70, so another formula is used to give lower bounds after that.

19 February, 2009 at 4:16 pm

A quick review of the polymath project « What Is Research?

[…] By this time, Gowers’ blog was receiving hundreds of comments, mostly comments by Gowers himself, but also including comments from distinguished mathematicians such as Terence Tao. Tao has his own blog, and he published a post giving the background of the Hales-Jewett theorem and a later post with some of his own ideas about the problem. […]

25 March, 2009 at 12:13 am

An Open Discussion and Polls: Around Roth’s Theorem « Combinatorics and more

[…] (as a little spin off to the polymath1 project, (look especially here and here)) if you have any thoughts about where the truth is for these problems, or about how to […]

11 April, 2009 at 11:17 am

Seva

278. Edel?

Just to remark that the upper bound for $c_n''$ , ascribed in 228. to Edel, is actually present in Meshulam’s paper, in the most explicit form.

12 May, 2009 at 6:26 am

Around the Cap-Set problem (B) « Combinatorics and more

[…] An affine line are three vectors so that for every . A cap set is a subset of without an affine line. The cap set problem asks for the maximum size of a cap set. For information on the cap set problem itself look here. For questions regarding density of sets avoiding other types of lines look here. […]

16 July, 2009 at 1:06 pm

The Polynomial Hirsch Conjecture: A proposal for Polymath3 « Combinatorics and more

[…] the idea of attempting a “polymath”-style open collaboration (see here, here and here) aiming to have some progress for these conjectures. (The Hirsch conjecture and the polynomial […]

1 May, 2010 at 10:42 am

Michael Nielsen » Introduction to the Polymath Project and “Density Hales-Jewett and Moser Numbers”

[…] evolved. Four days after Gowers opened his blog up for discussion, Terence Tao used his blog to start a discussion aimed at understanding the behaviour of for small . This discussion rapidly gained momentum, and […]

	Dan Romik on the Rie… on Polymath15, eleventh thread: W…
	Andrew Verras on Analysis II
	Yaver Gulusoy (cebis… on Analysis II
	Anonymous on Don’t prematurely obsess…
	What do mathematicia… on The Collatz conjecture, Little…
	L on Don’t prematurely obsess…
	L on Don’t prematurely obsess…
	Andrew Krause on Don’t prematurely obsess…
	Arsene1412 on Living Proof: Stories of Resil…
	Anonymous on Don’t prematurely obsess…
	Yaver Gulusoy (cebis… on Analysis II
	Anonymous on Analysis I
	Math grad student on Work hard
	Nic Dobson on How to assign partial credit o…
	Nic Dobson on How to assign partial credit o…

Upper and lower bounds for the density Hales-Jewett problem

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

100 comments

Leave a Reply to Sune Kristian Jakobsen Cancel reply

For commenters

Upper and lower bounds for the density Hales-Jewett problem

Share this:

Like this:

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

100 comments

Leave a Reply to Sune Kristian Jakobsen Cancel reply

For commenters