Folkman's theorem

From Polymath Wiki
Revision as of 07:50, 16 February 2009 by Teorth (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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.

This theorem can be deduced from Hindman's theorem, or from the Graham-Rothschild theorem.