The Hales-Jewett theorem

by liberator, Apr 2, 2018, 7:50 PM

This is just some stuff I've been looking at recently.

In this blog post, we will discuss the powerful Hales-Jewett theorem, one of the central results of Ramsey theory. We use it to prove the famous van der Waerden theorem, as well as its $n$ -dimensional generalisation, Gallai's theorem.

1. Definitions and Examples

For any positive integer $n$ , we write $[n]=\{1,2,\dots,n\}$ . Given a finite set $X$ , we denote by $X^n$ the $n$ -dimensional hypercube on the alphabet $X$ ; that is, the set of all possible $n$ -tuples $(x_1,x_2,\dots,x_n)$ , with $x_i\in X$ .

A $k$ -colouring of $X^n$ is a map $X^n\to[k]$ ; that is, we assign each element of $X^n$ one of $k$ colours, labelled by the elements of $[k]$ .

A subset $L$ of $X^n$ is called a combinatorial line if there exists a non-empty set of indices $I=\{i_1,i_2,\dots,i_k\}\subseteq[n]$ and, for each $i\not\in I$ , an $a_i\in X$ such that $L=\{(x_1,\dots,x_n)\in X^n\mid x_{i_1}=x_{i_2}=\dots=x_{i_k} \text{ and }x_i=a_i \text{ for } i\not\in I\}.$ We call $I$ the set of active coordinates of $L$ , since these are the coordinates that vary: the others are "fixed". More informally, a combinatorial line is the set of $n$ -tuples we get when we fix the values of some of the components, and set the other components equal to each other, allowing this common value to vary among the elements of $X$ .

For example, in $[3]^2$ , we have the following combinatorial lines:

$\begin{tabular}{|c|c|} \hline Active coordinates $I$ & Combinatorial line $L$ \\ \hline $~$ & $\{(1,1),(2,1),(3,1)\}$ \\ $\{1\}$ & $\{(1,2),(2,2),(3,2)\}$ \\ $~$ & $\{(1,3),(2,3),(3,3)\}$ \\ \hline $~$ & $\{(1,1),(1,2),(1,3)\}$ \\ $\{2\}$ & $\{(2,1),(2,2),(2,3)\}$ \\ $~$ & $\{(3,1),(3,2),(3,3)\}$ \\ \hline $\{1,2\}$ & $\{(1,1),(2,2),(3,3)\}$ \\ \hline \end{tabular}$ Displayed more pictorially,
$[asy] unitsize(1cm); real e = 0.5; for (int x=0; x<=2; ++x) { for (int y=0; y<=2; ++y) { label("$("+string(3-y)+","+string(x+1)+")$",(x,y)); } } DPA((-e,2)--(2+e,2)^^(-e,1)--(2+e,1)^^(-e,0)--(2+e,0),red); DPA((0,-e)--(0,2+e)^^(1,-e)--(1,2+e)^^(2,-e)--(2,2+e),blue); DPA((-e,2+e)--(2+e,-e),green); [/asy]$
Visual representations of combinatorial lines can be good when $n\leq3$ ; however, for $n\geq4$ , I find them less useful, essentially because I struggle to visualise in $4$ or more dimensions

.

Consider the standard "product order" on $[m]^n$ , given by $(x_1,x_2,\dots,x_n)\preceq(y_1,y_2,\dots,y_n)\iff x_i\leq y_i$ for all $i$ . If we restrict our attention to a combinatorial line, this partial order $\preceq$ is in fact a total order. Thus given a combinatorial line $L$ , we define $\alpha(L)$ to be the last element in our ordering of $L$ and $\beta(L)$ to be the first element.

Given a $k$ -colouring of $[m]^n$ and a positive integer $r\leq k$ , a rainbow $r$ -windmill is a set of $r$ combinatorial lines $L_1,L_2,\dots,L_r$ such that

There exists $f\in[m]^n$ such that $\alpha(L_i)=f$ for all $i$ . We call $f$ the focus of the rainbow $r$ -windmill.
Each individual $L_i\setminus\{\alpha(L_i)\}$ is monochromatic; i.e. all the points of an $L_i$ , ignoring the focus, are the same colour.
No two $L_i\setminus\{\alpha(L_i)\}$ have the same colour.

Finally, we introduce a definition needed for Gallai's theorem. Given a finite set $S\subset\mathbb N^d$ , a homothetic copy of $S$ is a set of the form $a+\lambda S$ , where $a\in\mathbb N^d$ and $\lambda\in\mathbb N$ . Geometrically, we are enlarging the set $S$ by a positive integer scale factor from the origin, then translating the enlarged image by some vector in $\mathbb N^d$ . As an example, when $d=1$ , a homothetic copy of $[m]$ is an arithmetic progression of length $m$ .

2. The Theorem

We are now ready to state the main result of this post.

Theorem. [Hales-Jewett] Given $m,k\in\mathbb N$ , there exists $n\in\mathbb N$ such that for any $k$ -colouring of $[m]^n$ , there is a monochromatic combinatorial line.

The smallest such $n$ with the desired property is denoted by $HJ(m,k)$ .

Proof. We go by induction on $m$ ; the base case $m=1$ is trivial. Now consider the following claim:

Claim. For $r\leq k$ , there exists $n$ such that for any $k$ -colouring of $[m]^n$ , there is either a monochromatic combinatorial line or a rainbow $r$ -windmill.

Note that our theorem follows from this claim: take $r=k$ , and look at the colour of the focus of the rainbow $k$ -windmill.

We prove our claim by induction on $r$ . For the base case $r=1$ , take $n=HJ(m-1,k)$ . Now assume that $n$ works for $r$ ; we show that $n+d$ , where $d=HJ\left(m-1,k^{m^n}\right)$ , works for $r+1$ .

Suppose that we have $k$ -coloured $[m]^{n+d}$ such that there are no monochromatic combinatorial lines. Note that $[m]^{n+d}$ is isomorphic to $[m]^n\times[m]^d$ . There are $k^{m^n}$ possible $k$ -colourings of $[m]^n$ , so by our choice of $d$ , there is a (monochromatic) combinatorial line $L$ in $[m]^d$ , with active coordinate set $I$ , such that for any $a\in[m]^n$ and $b\in L\setminus\{\alpha(L)\}$ , the colour of $(a,b)$ in our $k$ -colouring of $[m]^{n+d}$ is the same as the color of $a$ in the $k$ -colouring of $[m]^n$ .

Now take a rainbow $r$ -windmill $L_1,\dots,L_r$ for our $k$ -colouring of $[m]^n$ . Suppose the respective active coordinate sets are $I_1,\dots,I_r$ , and let $f$ be the focus. For each $1\leq i\leq r$ , let $L_i'$ be the combinatorial line through the point $(\beta(L_i),\beta(L))$ and with active coordinate set $I_i\cup I$ . Then $L_1',\dots,L_r'$ is a rainbow $r$ -windmill with focus $(f,\alpha(L))$ . Combining this with the combinatorial line through the point $(f,\beta(L))$ with active coordinate set $I$ gives us the desired rainbow $(r+1)$ -windmill.

This completes the proof of the claim, and hence of the theorem. $\square$

3. Applications

We now see how the Hales-Jewett theorem can be used to prove van der Waerden's theorem and Gallai's theorem easily.

Theorem. [van der Waerden] Given $m,k\in\mathbb N$ , there exists $n\in\mathbb N$ such that for any $k$ -colouring of $[n]$ , there is a monochromatic arithmetic progression of length $m$ .

Proof. Given a $k$ -colouring $\mathcal C$ of $\mathbb N$ , consider the $k$ -colouring $\mathcal C'$ of $[m]^n$ , with $n$ sufficiently large, given by $\mathcal C'((x_1,\dots,x_n))=\mathcal C\left(\sum_{i=1}^nx_i\right).$ By the Hales-Jewett theorem, there is a monochromatic combinatorial line in $[m]^n$ , which corresponds to an arithmetic progression of length $m$ in $\mathbb N$ . Explicitly, if $I$ is the set of active coordinates of our combinatorial line, then our arithmetic progression is $A+|I|, \quad A+2|I|, \quad \dots\quad,\quad A+m|I|,$ where $A=\sum_{i\not\in I}x_i$ . $\square$

Gallai's theorem is essentially a generalisation of van der Waerden's theorem to $\mathbb N^d$ . Recall that a homothetic copy of $S\subset\mathbb N^d$ is a set of the form $a+\lambda S$ , where $a\in\mathbb N^d$ and $\lambda\in\mathbb N$ .

Theorem. [Gallai] Given a finite set $S\subset\mathbb N^d$ , for any $k$ -colouring of $\mathbb N^d$ , there exists a monochromatic homothetic copy of $S$ .

Proof. Let $S=\{S(1),\dots,S(m)\}$ . Given a $k$ -colouring $\mathcal C$ of $\mathbb N^d$ , consider the $k$ -colouring $\mathcal C'$ of $[m]^n$ , with $n$ sufficiently large, given by $\mathcal C'((x_1,\dots,x_n))=\mathcal C\left(\sum_{i=1}^nS(x_i)\right).$ By the Hales-Jewett theorem, there is a monochromatic combinatorial line in $[m]^n$ , which corresponds to a monochromatic homothetic copy of $S$ in $\mathbb N^d$ . Explicitly, if $I$ is the set of active coordinates of our combinatorial line, then our homothetic copy of $S$ is $\sum_{i\not\in I}S(x_i)+|I|S$ . $\square$

combinatorics

Ramsey Theory

Comment

0 Comments

Submit

whoa....
by bachkieu, Jan 31, 2025, 1:40 AM
hello...
by ethan2011, Jul 4, 2024, 5:13 PM
2024 shout ftw
by Shreyasharma, Feb 19, 2024, 10:28 PM
time flies
by Asynchrone, Dec 13, 2023, 9:29 PM
first 2023 shout
by gracemoon124, Aug 2, 2023, 4:58 AM
offline.................
by 799786, Dec 27, 2021, 7:08 AM
YOU SHALL NOT PASS! - liberator
by OlympusHero, Aug 16, 2021, 4:10 AM
Nice Blog!
by geometry6, Jul 31, 2021, 1:39 PM
First shout out in 2021
by Aimingformygoal, May 31, 2021, 4:23 PM
indeed a pr0 blog
by Kanep, Dec 3, 2020, 10:46 PM
pr0 blog !!
by Hamroldt, Dec 2, 2020, 8:32 AM
niice bloog!
by Eliot, Oct 1, 2020, 3:27 PM
nice blog
by fukano_2, Aug 8, 2020, 7:49 AM
Nice blog
by Feridimo, Mar 31, 2020, 9:29 AM
Very nice blog !
by Kamran011, Oct 31, 2019, 5:48 PM
1000 VISITS!!!

IN 10 DAYS!!!
by liberator, Aug 23, 2014, 3:47 PM
YOU ARE SO PRO!!!!

Have you been to the IMO? If you have, then on not bragging about it. If you haven't, HOW ARE YOU SO CLEVER??!!?
by jlammy, Aug 23, 2014, 12:51 PM
Cool blog, great geometry problems!
by HYP135peppers, Aug 22, 2014, 6:25 PM
Extremely good at Geometry

Could you consider joining an Online Math Open Team with me?
by DanielL2000, Aug 22, 2014, 12:40 AM
Nice blog! I like geo too.
by sjaelee, Aug 21, 2014, 10:00 PM
thanks Cyclicduck!
by liberator, Aug 21, 2014, 9:56 PM
Hi, you are very good at geometry!
by Cyclicduck, Aug 21, 2014, 8:29 PM
Posts? What are those, exactly?
by kmw2001, Aug 19, 2014, 8:50 PM
@kmw2001, have 5 posts first.
by bcp123, Aug 19, 2014, 8:19 PM
How do i blog?
by kmw2001, Aug 19, 2014, 5:30 PM
thx bcp123, I guess its because I only have 10 posts, not much to brag on about
by liberator, Aug 15, 2014, 10:26 PM
why no one is writing here?
keep this going. nice collection of geoish things
by bcp123, Aug 15, 2014, 10:14 PM
thx!
by liberator, Aug 14, 2014, 2:56 PM
nice blog
by bcp123, Aug 14, 2014, 2:39 PM

56 shouts

Liberator's blog

The Hales-Jewett theorem

by liberator, Apr 2, 2018, 7:50 PM

0 Comments