Jacob Fox

Section 14.5 Jacob Fox

Jacob Fox is a Professor in the Department of Mathematics at Stanford University. Before joining Stanford in 2015, Dr. Fox was a faculty at the MIT Department of Mathematics. He completed his Ph.D. in mathematics at Princeton University in 2010.

🔗

His advisor was Benny Sudakov. Dr. Fox's research interests include extremal combinatorics, algebraic and probabilistic methods in combinatorics, Ramsey theory, graph theory, combinatorial geometry, and applications of combinatorics to computer science. In 2010, Fox was awarded the Dénes Kőnig Prize, an early–career award of the Society for Industrial and Applied Mathematics Activity Group on Discrete Mathematics. He was an invited speaker at the International Congress of Mathematicians in 2014. He was awarded the Oberwolfach Prize in 2016. [14.5.3.1] Fox and our instructor Dr. Veselin Jungić co–authored two papers. ([14.5.3.3], [14.5.3.4])

🔗

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.

🔗

Theorem 14.5.1. Hales–Jewett Theorem.

For any given positive integers $r$ and $k\text{,}$ there is a positive integer $N$ such that if the points of a $k$ –ary $N$ –dimensional cube are coloured with $r$ colours, there exists a monochromatic combinatorial line.

🔗

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

$\begin{equation*} \{(1,1),(1,2),(1,3)\},\{(1,1),(2,1),(3,1)\},\{(2,1),(2,2),(3,2)\}, \\ \{(2,1),(2,2),(3,2)\} \{(3,1),(3,2),(3,3)\},\{(3,1),(3,2),(3,3)\},\{(1,1),(2,2),(3,3)\}\text{.} \end{equation*}$

🔗

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."

🔗

References 14.5.3 References

🔗

[1]

Jacob Fox. (2024, January 17). Wikipedia. Retrieved April 7, 2024, from Wikipedia

🔗

[2]

Jacob Fox. Personal Communication. February 12, 2024.

🔗

[3]

Jungić, V., Licht (Fox), J., Mahdian, M., Nešetŗil, J., Radoičić, R., Rainbow Arithmetic Progressions and Anti–Ramsey Results, Combinatorics, Probability, Computing 12 (2003) 599–620.

🔗

[4]

Fox J., Jungić, V., Radoičić, R., Sub–Ramsey Numbers for Arithmetic Progressions and Schur Triples, Proceedings of Integers Conference 2005 in Honor of Ron Graham's Birthday, de Gruyter, 2007.