You are currently browsing the tag archive for the ‘density Hales-Jewett’ tag.
1. Upper and lower bounds for for small n.
The current best-known bounds for are . 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 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 with a 1s, b 2s, and c 3s is weighted by the factor ; this gives a total weight of . Let be the largest weight of a line-free set of , and let be the largest size of a subset of
which contains no upward-pointing equilateral triangles with r>0. It is known that ; the “hyper-optimistic conjecture” is that one in fact has . This would imply density Hales-Jewett for k=3.
3. Asymptotics for Moser’s cube problem
Moser’s cube problem asks to compute the largest size of a subset of the cube without geometric lines. The first few values of are known:
The best asymptotic lower bound known is still of the order of . 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 ; we know that it is equal to either 124 or 125, and it is looking increasingly unlikely that it is 125.
Comments on this thread should start at 900.
In this lecture, we describe the simple but fundamental Furstenberg correspondence principle which connects the “soft analysis” subject of ergodic theory (in particular, recurrence theorems) with the “hard analysis” subject of combinatorial number theory (or more generally with results of “density Ramsey theory” type). Rather than try to set up the most general and abstract version of this principle, we shall instead study the canonical example of this principle in action, namely the equating of the Furstenberg multiple recurrence theorem with Szemerédi’s theorem on arithmetic progressions.
Read the rest of this entry »