Carlson's theorem: Difference between revisions
New page: '''Carlson-Simpson Graham-Rothschild theorem''' (k=3), Version I: If <math>[4]^\omega := \bigcup_{n=0}^\infty [4]^n</math> is partitioned into finitely many color classes, then there exist... |
No edit summary |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
'''Carlson | '''Carlson's theorem''' (k=3), Version I: If <math>[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. | 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. | ||
| Line 5: | Line 5: | ||
It has an equivalent formulation: | It has an equivalent formulation: | ||
'''Carlson | '''Carlson's theorem''' (k=3), Version I: If the [[combinatorial line]]s in <math>[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>[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.
