Graham–Rothschild Theorem

In mathematics, the Graham–Rothschild theorem is a theorem that applies Ramsey theory to combinatorics on words and combinatorial cubes. It is named after Ronald Graham and Bruce Lee Rothschild, who published its proof in 1971. Through the work of Graham, Rothschild, and in 1972, it became part of the foundations of structural Ramsey theory. A special case of the Graham–Rothschild theorem motivates the definition of Graham's number, a number that was popularized by Martin Gardner in ''Scientific American'' and listed in the ''Guinness Book of World Records'' as the largest number ever appearing in a mathematical proof.

Background

The theorem involves sets of strings, all having the same length $n$, over a finite alphabet, together with a group acting on the alphabet. A combinatorial cube is a subset of strings determined by constraining some positions of the string to contain a fixed letter of the alphabet, and by constraining other pairs of positions to be equal to each other or to be related to each other by the group action. This determination can be specified more formally by means of a labeled parameter word, a string with wildcard characters in the positions that are not constrained to contain a fixed letter and with additional labels describing which wildcard characters must be equal or related by the group action. The dimension of the combinatorial cube is the number of free choices that can be made for these wildcard characters. A combinatorial cube of dimension one is called a combinatorial line.

For instance, in the game of tic-tac-toe, the nine cells of a tic-tac-toe board can be specified by strings of length two over the three-symbol alphabet (the Cartesian coordinates of the cells), and the winning lines of three cells form combinatorial lines. Horizontal lines are obtained by fixing the $y$-coordinate (the second position of the length-two string) and letting the $x$-coordinate be chosen freely, and vertical lines are obtained by fixing the $x$-coordinate and letting the $y$-coordinate be chosen freely. The two diagonal lines of the tic-tac-toe board can be specified by a parameter word with two wildcard characters that are either constrained to be equal (for the main diagonal) or constrained to be related by a group action that swaps the 1 and 3 characters (for the antidiagonal).

The set of all combinatorial cubes of dimension $d$, for strings of length $n$ over an alphabet $A$ with group action $G$, is denoted ,Gtbinom. A ''subcube'' of a combinatorial cube is another combinatorial cube of smaller dimension that forms a subset of the set of strings in the larger combinatorial cube. The subcubes of a combinatorial cube can also be described by a natural composition action on parameter words, obtained by substituting the symbols of one parameter word for the wildcards of another.

Statement

With the notation above, the Graham–Rothschild theorem takes as parameters an alphabet $A$, group action $G$, finite number of colors $r$, and two dimensions of combinatorial cubes $m$ and $k$ with $m > k$. It states that, for every combination of $A$, $G$, $r$, $m$, and $k$, there exists a string length $n\ge m$ such that, if each combinatorial cube in ,Gtbinom is assigned one of $r$ colors, then there exists a combinatorial cube in ,Gtbinom all of whose $k$-dimensional subcubes are assigned the same color.

An infinitary version of the Graham–Rothschild theorem is also known.

Applications

The special case of the Graham–Rothschild theorem with $m=1$, $k=0$, and the trivial group action is the Hales–Jewett theorem,
stating that if all long-enough strings over a given alphabet are colored, then there exists a monochromatic combinatorial line.

Graham's number is a bound for the Graham–Rothschild theorem with $, A, =2$, $r=2$, $m=2$, $k=1$, and a nontrivial group action. For these parameters, the set of strings of length $n$ over a binary alphabet describes the vertices of an $n$-dimensional hypercube, every two of which form a combinatorial line. The set of all combinatorial lines can be described as the edges of a complete graph on the vertices. The theorem states that, for a high-enough dimension $n$, whenever this set of edges of the complete graph is assigned two colors, there exists a monochromatic combinatorial plane: a set of four hypercube vertices that belong to a common geometric plane and have all six edges assigned the same color. Graham's number is an upper bound for this number $n$, calculated using repeated exponentiation; it is believed to be significantly larger than the smallest $n$ for which the statement of the Graham–Rothschild theorem is true.

References

{{DEFAULTSORT:Graham-Rothschild theorem
Ramsey theory
Combinatorics on words
Theorems in combinatorics