Carlson's theorem: Difference between revisions
No edit summary |
No edit summary |
||
| Line 8: | Line 8: | ||
This follows by viewing a combinatorial line in <math>[3]^\omega</math> as an element in <math>[4]^\omega</math> containing at least one 4, thinking of the 4 as the "wildcard" for the line. | This follows by viewing a combinatorial line in <math>[3]^\omega</math> as an element in <math>[4]^\omega</math> containing at least one 4, thinking of the 4 as the "wildcard" for the line. | ||
The k=2 version of this theorem is [[Hindman's theorem]]. | |||
Latest revision as of 23:51, 15 February 2009
Carlson's theorem (k=3), Version I: If [math]\displaystyle{ [4]^\omega := \bigcup_{n=0}^\infty [4]^n }[/math] is partitioned into finitely many color classes, then there exists an infinite-dimensional combinatorial subspace with no fixed coordinate equal to 4, such that every element of this combinatorial subspace with at least one 4 has the same color.
This theorem is a common generalization of the Carlson-Simpson theorem and the Graham-Rothschild theorem. It plays a key role in the Furstenberg-Katznelson argument. 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.
It has an equivalent formulation:
Carlson's theorem (k=3), Version I: If the combinatorial lines in [math]\displaystyle{ [3]^\omega := \bigcup_{n=0}^\infty [3]^n }[/math] are partitioned into finitely many color classes, then there exists an infinite-dimensional combinatorial subspace such that all combinatorial lines in this subspace have the same color.
This follows by viewing a combinatorial line in [math]\displaystyle{ [3]^\omega }[/math] as an element in [math]\displaystyle{ [4]^\omega }[/math] containing at least one 4, thinking of the 4 as the "wildcard" for the line.
The k=2 version of this theorem is Hindman's theorem.
