Kalpana Kalpana (Editor)

Large set (Ramsey theory)

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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.

Contents

Examples

  • The natural numbers are large. This is precisely the assertion of Van der Waerden's theorem.
  • The even numbers are large.

    • Properties

    Necessary conditions for largeness include:

  • If S is large, for any natural number n, S must contain at least one multiple (equivalently, infinitely many multiples) of n.
  • If S = { s 1 , s 2 , s 3 , … } is large, it is not the case that sk≥3sk-1 for k≥ 2.

    • Two sufficient conditions are:

  • If S contains n-cubes for arbitrarily large n, then S is large.
  • If S = p ( N ) ∩ 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 is a thick set, then S is large.

    Other facts about large sets include:

  • If S is large and F is finite, then S – F is large.
  • k ⋅ N = { k , 2 k , 3 k , … } is large.
  • If S is large, k ⋅ S is also large.

    • If S is large, then for any m , S ∩ { x : x ≡ 0 ( mod m ) } is large.

    2-large and k-large sets

    A set is k-large, for a natural number k > 0, when it meets the conditions for largeness when the restatement of van der Waerden's theorem is concerned only with k-colorings. Every set is either large or k-large for some maximal k. This follows from two important, albeit trivially true, facts:

  • k-largeness implies (k-1)-largeness for k>1
  • k-largeness for all k implies largeness.

    • It is unknown whether there are 2-large sets that are not also large sets. Brown, Graham, and Landman (1999) conjecture that no such sets exists.

    References

    Large set (Ramsey theory) Wikipedia
    (Text) CC BY-SA