Folkman's theorem: Difference between revisions
No edit summary |
No edit summary |
||
| Line 5: | Line 5: | ||
The integer version can be deduced from the set version by considering colourings which depend only on the number of 1s of the string. | The integer version can be deduced from the set version by considering colourings which depend only on the number of 1s of the string. | ||
The set version of this theorem can be deduced from [[Hindman's theorem]]. The higher k generalization of this version is the [[Graham-Rothschild theorem]]. | |||
The m=2 case of the integer version of this theorem is [http://en.wikipedia.org/wiki/Schur%27s_theorem Schur's theorem]. | |||
Revision as of 23:54, 15 February 2009
Folkman's theorem (sets version): If [math]\displaystyle{ [2]^n }[/math] is partitioned into c color classes, and n is sufficiently large depending on c, m, then one of the color classes contains all the strings in a m-dimensional combinatorial subspace containing at least one 1, where none of the fixed digits are equal to 1.
Folkman's theorem (integer version): If [math]\displaystyle{ [N] }[/math] is partitioned into c color classes, and N is sufficiently large depending on c, m, then one of the color classes contains all the non-zero finite sums of an m-element set of positive integers.
The integer version can be deduced from the set version by considering colourings which depend only on the number of 1s of the string.
The set version of this theorem can be deduced from Hindman's theorem. The higher k generalization of this version is the Graham-Rothschild theorem.
The m=2 case of the integer version of this theorem is Schur's theorem.
