Large set (Ramsey theory)

From Wikipedia, the free encyclopedia

You have new messages (last change).
For other uses of the term, see small set or large set.

In Ramsey theory, a set S of natural numbers is considered to be a large set if and only if Van der Waerden's theorem can be generalized to assert the existence of arithmetic progressions with common difference in S. That is, S is large if and only if every finite partition of the natural numbers has a cell containing arbitrarily long arithmetic progressions having common differences in S. A small set is then a set that is not large.

Examples:

Necessary conditions for largeness include:

  • If S is large, for any natural number n, S must contain infinitely many multiples of n.
  • If S=\{s_1,s_2,s_3,\dots\} is large, it is not the case that sk≥3sk-1 for k≥ 2.

Two sufficient conditions are:

  • If S contains arbitrarily long n-cubes, then S is large.
  • If S \subseteq p(\mathbb{N}) \cap \mathbb{N} where p is a polynomial with p(0) = 0 and positive leading coefficient, then S is large.

The first sufficient condition implies that if S contains a thick set, then S is large.

Other facts about large sets include:

  • If S is large and F is finite, then S − F (see Complement) is large.
  • k\cdot \mathbb{N}=\{k,2k,3k,\dots\} is large. Similarly, if S is large, k\cdot S is also large.

If S is large, then for any m, S \cap \{ x : x \equiv 0\pmod{m} \} is large.

[edit] References

Brown, Tom, Ronald Graham, & Bruce Landman. On the Set of Common Differences in van der Waerden's Theorem on Arithmetic Progressions. Canadian Math Bulletin, Vol 42 (1), 1999. p 25-36.

[edit] See also

[edit] External links

Retrieved from "http://en.wikipedia.org../../../l/a/r/Large_set_%28Ramsey_theory%29_8150.html"