Folkman's theorem

From Polymath1Wiki
Jump to: navigation, search

Folkman's theorem (sets version): If [math][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][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 integer version can also be deduced from Rado's theorem.

The set version can be deduced from the integer version by using Ramsey's Theorem to restrict to a coloring which depends only on the cardinality of a set. 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.

Folkman's theorem was also independently discovered by Arnautov and by Sanders.