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

My good friend Tim Gowers has just started an experimental “massively collaborative mathematical project” over at his blog.  The project is entitled “A combinatorial approach to density Hales-Jewett“, and the aim is to see if progress can be made on this problem by many small contributions by a large number of people, as opposed to the traditional model of a few very large contributions by a small number of people (see this article for more on the “rules of the game”, and this article for why this particular project was picked as a test project).  I think this is an interesting experiment, and hopefully a successful one, though it is far too early to tell as yet.

I can describe the problem here.  Let n be a large integer, and let ${}[3]^n$ be the set of all strings of length n using the alphabet $\{1,2,3\}$, thus for instance $13323 \in [3]^5$.  A combinatorial line in ${}[3]^n$ is a triple of points in ${}[3]^n$ that can be formed by taking a string of length n using the alphabet $\{1,2,3,x\}$ with at least one occurrence of the “wildcard” x, and then substituting the values of 1, 2, 3 for the wildcard.  For instance, the string $1xx2x$ would lead to the combinatorial line $\{11121, 12222, 13323\}$ in ${}[3]^5$.  The (k=3) case of the density Hales-Jewett theorem of Furstenberg and Katznelson asserts:

Density Hales-Jewett theorem. Let $0 < \delta < 1$.  Then if n is sufficiently large depending on $\delta$, every subset of ${}[3]^n$ of density at least $\delta$ contains a combinatorial line.

[Furstenberg and Katznelson handled the case of general k in a subsequent paper.  The k=1 case is trivial, and as pointed out in this post by Gil Kalai, the k=2 case follows from Sperner's theorem.]

Furstenberg and Katznelson’s proof uses ergodic theory, and in particular does not obviously give any bound as to how large n has to be depending on $\delta$ before the theorem takes effect.  No other proofs of this theorem are currently known.  So it would be desirable to have a combinatorial proof of the k=3 density Hales-Jewett theorem.  Since this theorem implies Roth’s theorem, and Roth’s theorem has a combinatorial proof based on the triangle removal lemma (see e.g. my Simons lecture on the subject, or Tim Gowers’ background article for the project), it is thus natural to ask whether the density Hales-Jewett theorem has a proof based on something similar to the triangle removal lemma.  This is basically the question being explored in the above project. (Some further motivation for this problem can be found here.)

Further articles on this project are collected at this page.

In this lecture, we use topological dynamics methods to prove some other Ramsey-type theorems, and more specifically the polynomial van der Waerden theorem, the hypergraph Ramsey theorem, Hindman’s theorem, and the Hales-Jewett theorem. In proving these statements, I have decided to focus on the ultrafilter-based proofs, rather than the combinatorial or topological proofs, though of course these styles of proof are also available for each of the above theorems.