0
$\begingroup$

I read, briefly, about a connection between Ramsey's Theory and Tic-Tac-Toe.

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?

$\endgroup$
1
3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.