Hindman's theorem

2009-05-21T11:06:29Z

75.82.57.223:

'''Hindman's theorem''': If <math>[2]^\omega := \bigcup_{n=0}^\infty [2]^n</math> is finitely colored, then one of the color classes contain all elements of an infinite-dimensional [[combinatorial subspace]] which contain the digit 1, and such that none of the fixed digits of this subspace are equal to 1.

The generalization of this theorem which replaces 2 with larger k is [[Carlson's theorem]]. Hindman's theorem also implies [[Folkman's theorem]].

Folkman's theorem

2009-05-21T11:05:27Z

75.82.57.223:

'''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 [http://en.wikipedia.org/wiki/Rado%27s_theorem_(Ramsey_theory) 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 [http://en.wikipedia.org/wiki/Schur%27s_theorem Schur's theorem].

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

Polymath Wiki - User contributions [en]

Hindman's theorem

Folkman's theorem