Introduction to Ramsey Theory: Students' Projects

Subsection 14.5.1 Jacob Fox's favourite proof

One of Jacob Fox's favourite proofs is the Hales–Jewett theorem. Professor Fox wrote to us:

Among my favourite proofs in Ramsey theory is that of the Hales-Jewett theorem and the primitive recursive bound proof obtained by Shelah. One of the intriguing aspects is that it follows a recursive argument very similar to the earlier proof, but done in a different order. By just changing the order in the recursive argument, Shelah's proof obtains a much better quantitative bound. An exposition of this can be found here. [14.5.3.2]

This is the very beginning of the text on the webpage that Professor Fox suggested.

This means there is a collection of points where one coordinate is fixed, and the remaining vary over all \(k\) values but form a line where all the points have the same colour.

The smallest such number \(N\) is called the Hales–Jewett number \(HJ(k,r)\text{.}\) Combinatorial lines are similar to arithmetic progressions in the sense that they represent ordered structures within a lattice but are defined within the high–dimensional context of the hypercube.

It is noted that combinatorial lines extend beyond simple two–dimensional structures and can be seen in games like tic–tac–toe, with implications for more complex high–dimensional spaces.

Let \(k\text{,}\) \(r\ge 2\) be positive integers. Then there exists a positive integer \(N\) such that whenever\((1,2,\ldots,k)^N\) is coloured with \(r\) colours, there is a monochromatic combinatorial line, that is, a collection \(P_1,\ldots ,P_k\) of \(k\) points such that in some coordinates the \(P_i\) are equal, while all the other coordinates in \(Pi\) have value \(i\text{.}\)

The smallest such \(N\) is called the Hales–Jewett number \(HJ(k,r)\text{.}\) The combinatorial lines are very natural structures in the lattice cube, somewhat similarly to arithmetic progressions in the integers. As an example, the combinatorial lines in the \(3\times 3\) square \(\{1,2,3\}^2\) are

Note that these lines would count as a victory in a tic–tac–toe game on a \(3\times 3\) board, and more generally combinatorial lines are always winning lines in a tic-tac-toe on some board. The additional requirement for a combinatorial line is that it should be increasing. Now the Hales–Jewett theorem immediately implies the following (not very practical) statement about tic–tac–toe. Given \(k\) and \(r\text{,}\) if \(r\) players are playing tic–tac–toe on a hypercube of side length \(k\text{,}\) then as long as the dimension is large enough, there will be no draw. We will see that the Hales–Jewett theorem, despite assuming almost no structure on the set of integers, has strong consequences in arithmetic Ramsey theory.

Subsection 14.5.2 Reflection

It was interesting to learn that there is much more about the Hales-Jewett theorem than we learned in the class. As our instructor said in the class, "We are just scratching the surface of Ramsey Theory."