Tic-Tac-Toe Games: Exact Values of Infinitely Many Game Numbers

COMPUTER SCIENCE/DISCRETE MATH, I
Topic:	Tic-Tac-Toe Games: Exact Values of Infinitely Many Game Numbers
Speaker:	Jozsef Beck
Affiliation:	Rutgers University
Date:	Monday, October 25
Time/Room:	11:15am - 12:15pm/S-101

---

Ordinary 3-by-3 tic-tac-toe is trivial; the 3-dimensional 4-by-4-by-4 version is interesting but very complicated (first player
wins; solved by Patashnik; heavy computer use); and the 5-by-5-by-5 version is already unsolved (expected to be a draw).

If even the simplest games are unsolved than how can we determine "infinitely many exact values"? Well, we cheat a little bit: instead of
the usual question of ``who does it first" we study the somewhat easier (but more fundamental) question of `what is doable" (but not necessarily first). In general this question is still hopeless, but to my greatest surprise, I could find the exact solutions of infinitely many ``natural games". For example,

(1) "Clique Game": Playing on a large complete graph, and taking edges, what is the largest complete subgraph that a player can occupy?

(2) "2-dimensional arithmetic progression game": Playing on an N-by-N board, what is the largest square lattice that a player can occupy?

(3) Multi-dimensional tic-tac-toe, but the "winning sets" are "planes" instead of the usual "lines".