RT Part 8; Hales-Jewett and how to make Tic-Tac-Toe Interesting

A preliminary note:  I am beginning to lose steam on Ramsey theory.  I want to move on to a few other things and so I will probably gloss over or postpone a few topics that I planned on getting to.  In my first post I said that I would cover what I have covered so far as well as the Hales-Jewett theorem, the growth of Ramsey numbers, sparse Ramsey theory, and probabilistic results.  I will cover HJ today, sparse RT next time, and postpone the rest.

Alrighty, now back to math.  The Hales-Jewett theorem is one about combinatorial lines.  So first we must define what those are.  Even though the definition makes them sound more confusing than they really are, let’s start there.

Definition.  Let X be a finite set and let X^n denote n-tuples over the alphabet X.  A set L \subseteq X^n is called a combinatorial line if there exists a nonempty I \subseteq [n] and a_i \in X for each i \notin I such that

L = \{(x_1, \dots, x_n) \in X^n : x_i = a_i \text{ for all } i \notin I, x_i = x_j \text{ for all } i,j \in I\}.

So some of the coordinates are fixed, the rest move in synch.  The best way to picture it is by seeing an example.  In [3]^3, (3-tuples with entries from [3] = \{1,2,3\}), one example of a line is  $((1,1,1), (1,2,2), (1,3,3)).$  It’s completely analogous lines in \mathbb{R}^n, or better yet, in \mathbb{Z}^n.

The Hales-Jewett Theorem.  For each m, k \in \mathbb{N}, there exist some n such that whenever [m]^n is k-colored there exists a monochromatic combinatorial line.  The least such n is written as HJ(m,k).

Remarks.  How this result relates to the title of this post is the following.  Assume we are playing a generalization of tic-tac-toe in which there are k players playing on an n-dimensional cube of side length m-1, say with one corner at the origin.  Each  player has a bunch of marbles of their color and they take turns placing their marbles on the lattice points of the cube.  These points are obviously in bijection with the n-tuples whose entries come from [m].

The goal is to get a vertical, horizontal, or diagonal sequence of marbles, all of which are of your color, of length m — i.e. from one edge of the cube to the other, usually contained within a smaller, n-dimensional rectangular box which is a subset of the cube.  If m=3 and n=k=2, then this is tic-tac-toe.

This is what m=4, n=k=3 looks like:

What the Hales-Jewett theorem says is that as long as you play k-person, m-in-a-row tic-tac-toe in enough dimensions, you can guarantee that the game will not end in a draw!  So tic-tac-toe may seem like a silly game in which a player has to make a really boneheaded move to have the game not end in a draw.  But that’s only because you are playing on a measly 2 dimensional board.  And even just 3-in-a-row, 2-person tic-tac-toe requires more than two dimensions for the game to be interesting.

Now, it does turn out that when playing in enough dimensions to guarantee that the game won’t end in a draw, the first player to move, if they play perfectly, will be guaranteed to win (try to prove this).  But this is not immediately obvious, so I will still assert that the new game is still “interesting” – as is chess, even if it is one day proved to solvable.

Our second remark is that HJ implies Van Der Waerden’s theorem which we talked about last time.  Given a coloring c : \mathbb{N} \to [k] of \mathbb{N}, create a coloring c' of [m]^n by c'((x_1, \dots, x_n)) = c((x_1 + \dots + x_n)).  And note that a combinatorial line in [m]^n (which will have length m) gives a monochromatic arithmetic progression in \mathbb{N} of length m.

Now I will briefly sketch a proof of the HJ theorem.

Proof.  The proof is by induction on m.  If m=1 it is trivial.  Assume m > 1.  I claim that for all r \leq k, there exists an n such that whenever  [m]^n is k-colored there either exists a monochromatic line or there exist r color-focused lines.

The proof of the claim is by induction on r.  r=1 is trivial.  If n = HJ(m-1,k) is suitable for r-1, then one can show that n + \text{HJ}(m-1, k^{m^n}) is suitable for r.  The rest of the claim is an exercise in focusing.

This finishes it off since we can then set r=k and look at the color of the focus.                                                                                                                                                                               \square

Next time we will finish off this sequence of posts on Ramsey theory by talking about one of my favorite topics:  sparse Ramsey theory.

Advertisements

About Jay Cummings

I am a fifth year mathematics Ph.D. student at UCSD.
This entry was posted in Combinatorics, Ramsey Theory. Bookmark the permalink.

One Response to RT Part 8; Hales-Jewett and how to make Tic-Tac-Toe Interesting

  1. Pingback: RT Part 9; Sparse Ramsey Theory | whateversuitsyourboat

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s