Hales–Jewett theorem

In mathematics, the Hales–Jewett theorem[1] is a fundamental combinatorial result of Ramsey theory named after Alfred W. Hales and Robert I. Jewett, concerning the degree to which high-dimensional objects must necessarily exhibit some combinatorial structure.

In other words, assuming n and c are fixed, the higher-dimensional, multi-player, n-in-a-row generalization of a game of tic-tac-toe with c players cannot end in a draw, no matter how large n is, no matter how many people c are playing, and no matter which player plays each turn, provided only that it is played on a board of sufficiently high dimension H. By a standard strategy-stealing argument, one can thus conclude that if two players alternate, then the first player has a winning strategy when H is sufficiently large, though no practical algorithm for obtaining this strategy is known.

A variable word w(x) over WHn still has length H but includes the special element x in place of at least one of the letters.

One can prove the general case of the Hales–Jewett theorem by similar methods, using mathematical induction.

If we fix the first six elements of such a string and let the last two vary, we obtain an ordinary tic-tac-toe board, for instance "132113??"

This is simply because all of the combinatorial lines appearing in the above proof of the Hales–Jewett theorem, also form arithmetic progressions in decimal notation.

The theorem states that if H is sufficiently large depending on n and δ, then the set A must necessarily contain an entire combinatorial line.

The density Hales–Jewett theorem was originally proved by Furstenberg and Katznelson using ergodic theory.

[7] Dodos, Kanellopoulos, and Tyros gave a simplified version of the Polymath proof.