Graham-Rothschild theorem: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
'''Graham-Rothschild theorem''' (k=3): If all the [[combinatorial line]]s in <math>[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>[3]^n</math> such that all the combinatorial lines in this subspace have the same color. | '''Graham-Rothschild theorem''' (k=3), Version 1: If all the [[combinatorial line]]s in <math>[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>[3]^n</math> such that all the combinatorial lines in this subspace have the same color. | ||
This theorem implies the [[Hales-Jewett theorem]]. | This theorem implies the [[Hales-Jewett theorem]]. It has an alternate formulation: | ||
'''Graham-Rothschild theorem''' (k=3), Version 2: If <math>[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>[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>[3]^n</math> as a string in <math>[4]^n</math> containing at least one 4, by thinking of 4 as the "wildcard". | |||
The Graham-Rothschild theorem and the [[Carlson-Simpson theorem]] have a common generalisation, the [[Carlson-Simpson Graham-Rothschild theorem]]. | |||
Revision as of 17:31, 15 February 2009
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".
The Graham-Rothschild theorem and the Carlson-Simpson theorem have a common generalisation, the Carlson-Simpson Graham-Rothschild theorem.
