# Graham-Rothschild theorem

Graham-Rothschild theorem (k=3), Version 1: If all the combinatorial lines in $[3]^n$ is partitioned into c color classes, and n is sufficiently large depending on c, m, then there is an m-dimensional combinatorial subspace of $[3]^n$ such that all the combinatorial lines in this subspace have the same color.
Graham-Rothschild theorem (k=3), Version 2: If $[4]^n$ is partitioned into c color classes, and n is sufficiently large depending on c, m, then there is an m-dimensional combinatorial subspace of $[4]^n$, 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 $[3]^n$ as a string in $[4]^n$ 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.