# Ramsey's Theory and Tic-Tac-Toe analogy.

From my understanding, it went like this:

Imagine playing Tic-Tac-Toe in a k-dimensional hyper-cube. There is such a dimension k where, regardless of cheating and foul-play, the game must end with a winner.

I want to know if this is correct, where $k$ is the solution to Ramsey's Theory. Are there any other interesting analogies that, say the average high-schooler, would understand?

I would say that's right - you're basically describing the Hales-Jewett theorem. I would make a few points, though:

• There's more to the theorem than that! You can increase the number of players, as well as the size of the $k$-hypercube (e.g. number of cells in a row).

• This isn't the only problem in Ramsey theory. So saying e.g. "$k$ is the solution to Ramsey's theory" is very misleading: it suggests there is somehow a single problem, or even a "main problem," when in fact there is an incredibly rich supply of wildly different problems. For instance,

• Ramsey's original theorem: given any $n$ and $r$, there is some $k$ such that if I color the edges of the complete graph on $k$ vertices ($K_k$) with $r$ colors, I can always find a monochromatic $K_n$.

• The "Happy Ending Problem" https://en.wikipedia.org/wiki/Happy_ending_problem. For a given $n$, what is the least $k$ such that any $k$ points in the plane, no three collinear, contain a convex $n$-gon?

• Van-der-Waerden's theorem https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem on arithmetic progressions: For any $r$ and $k$, there is some $N$ such that if I color the first $N$ integers $1$, . . . , $N$ with $r$ colors, there is a monochromatic arithmetic sequence of length $\ge k$.

• And, of course, the problem that gave rise to this beauty: https://en.wikipedia.org/wiki/Graham%27s_number.

• Thank you, you've really cleared up a lot of confusion for me. – Simply Beautiful Art Jan 9 '16 at 17:15