Hales Jewett Theorem - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T09:45:17Z http://mathoverflow.net/feeds/question/92253 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/92253/hales-jewett-theorem Hales Jewett Theorem Shahab 2012-03-26T11:21:27Z 2012-03-26T14:50:21Z <p>In the book <em>Ramsey Theory</em> by Graham, Rothschild and Spencer the authors state:</p> <blockquote> <p>The Hales Jewett Theorem strips van der Waerden's theorem of its unessential elements and reveals the heart of Ramsey theory. It provides a focal point from which many of the results can be derived and acts as a cornerstone of much of the more advanced work. Without this result Ramsey theory would more properly be called Ramseyian theorems.</p> </blockquote> <p>I am interested in knowing as to what further advanced results flow from the Hales Jewett theorem and why is the theorem so crucial.</p> <p>Thanks for your time.</p> http://mathoverflow.net/questions/92253/hales-jewett-theorem/92256#92256 Answer by Stefan Geschke for Hales Jewett Theorem Stefan Geschke 2012-03-26T12:12:06Z 2012-03-26T13:23:38Z <p>The Hales-Jewett Theorem works in a context that is more abstract than that of the semi-group $\mathbb N$. This is what makes it more applicable than earlier theorems. This paper by Sabine Koppelberg points out some easy implications as well as a more general form of the Hales Jewett Theorem: [The Hales-Jewett theorem via retractions. Proceedings of the 18th Summer Conference on Topology and its Applications. Topology Proc. 28 (2004), no. 2, 595–601]</p> <p>I think some of the developments around Hindman's theorem, speaking about semi-groups more abstract (i.e., with fewer relations) than $(\mathbb N,+)$, for example the finite subsets of $\omega$ with union, are motivated by the abstractness of Hales Jewett. Furstenberg and Katznelson used topological dynamics to prove a density version of the Hales Jewett Theorem. Blass gave a proof of the Hales Jewett Theorem using ultrafilters. The main result in Koppelberg's paper mentioned above is also proved using algebra in the Stone-Czech compactification of a semi-group. Here the Hales Jewett Theorem and variants seem to be interesting test questions for a method of proof.</p> <hr> <p>Edit: It just occurred to me that a combinatorial proof of the density Hales Jewett Theorem was the outcome of a massive collaboration called the "Polymath Project" initiated by Timothy Gowers. The abstract of the corresponding paper, which can be found <a href="http://arxiv.org/abs/0910.3926" rel="nofollow">here</a>, says "The Hales-Jewett theorem has a density version as well, proved by Furstenberg and Katznelson in 1991 by means of a significant extension of the ergodic techniques that had been pioneered by Furstenberg in his proof of Szemeredi's theorem". The "significant extension of the ergodic techniques" and the fact that no combinatorial proof was known before the 2009 Polymath paper indicates some of the subtleties of Hales Jewett.</p> http://mathoverflow.net/questions/92253/hales-jewett-theorem/92277#92277 Answer by Péter Komjáth for Hales Jewett Theorem Péter Komjáth 2012-03-26T14:37:40Z 2012-03-26T14:50:21Z <p>A simple application of the Hales-Jewett theorem give the following result: if $r$, $k$ are natural numbers, then there is a finite set $S$ of natural numbers which does not contain a $(k+1)$-AP, yet every coloring with $r$ colors gives a monochromatic $k$-AP. </p> <p>Let $N$ be sufficiently large. The HJ theorem says that if we color all sequences of length $N$, consisting of numbers between 0 and $k-1$, with $r$ colors, there is a monocolored combinatorial line, that is, a configuration of the form $f_0,\dots,f_{k-1}$, such that for a nonempty subset <code>$T\subseteq \{0,\dots,N-1\}$ $f_i$</code> is $i$ in $T$, and the same outside it. Now the set $S$ above consists of the sums $x_0+x_1M+x_2M^2+\cdots+x_{N-1}M^{N-1}$, ($0\leq x_j\leq k-1$), where $M$ is very large. That is, we map the HJ-hypercube via the mapping $(x_0,x_1,\dots,x_{N-1})\mapsto x_0+x_1M+x_2M^2+\cdots+x_{N-1}M^{N-1}$. If $M$ is large enough, then no linear combination with small ($\lt k$) coefficients that gives 0, unless the same linear combination gives 0 in the left hand side, i.e., in the hypercube, in which there is no $(k+1)$-AP. </p>