Graham-Rothschild theorem

Graham-Rothschild theorem (k=3), Version 1: If all the combinatorial lines in [math]\displaystyle{ [3]^n }[/math] is partitioned into c color classes, and n is sufficiently large depending on c, m, then there is an m-dimensional combinatorial subspace of [math]\displaystyle{ [3]^n }[/math] such that all the combinatorial lines in this subspace have the same color.

This theorem implies the Hales-Jewett theorem. It has an alternate formulation:

Graham-Rothschild theorem (k=3), Version 2: If [math]\displaystyle{ [4]^n }[/math] is partitioned into c color classes, and n is sufficiently large depending on c, m, then there is an m-dimensional combinatorial subspace of [math]\displaystyle{ [4]^n }[/math], with none of the fixed positions equal to 4, such that all elements of this subspace that contain at least one 4 have the same color.

Indeed, one can think of a combinatorial line in [math]\displaystyle{ [3]^n }[/math] as a string in [math]\displaystyle{ [4]^n }[/math] containing at least one 4, by thinking of 4 as the "wildcard". It is necessary to restrict to elements containing at least one 4; consider the coloring that colors a string black if it contains at least one 4, and white otherwise.

The Graham-Rothschild theorem and the Carlson-Simpson theorem have a common generalisation, Carlson's theorem.

The k=1 case of the Graham-Rothschild theorem is Folkman's theorem.