Large set (Ramsey theory)

Short description: Sets big enough to assert the existence of arithmetic progressions with common difference

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

* 1 Examples
* 2 Properties
* 3 2-large and k-large sets
* 4 See also
* 5 Further reading
* 6 External links

## 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={s1,s2,s3,…} 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(ℕ)∩ℕ 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⋅ℕ={k,2k,3k,…} is large.
* If S is large, k⋅S is also large.

If S is large, then for any m, S∩{x:x≡0(modm)} 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.

## See also

* Partition of a set

## Further reading

* Brown, Tom; Graham, Ronald; Landman, Bruce (1999). "On the Set of Common Differences in van der Waerden's Theorem on Arithmetic Progressions". Canadian Mathematical Bulletin 42 (1): 25–36. doi:10.4153/cmb-1999-003-9.

## External links

* Mathworld: van der Waerden's Theorem

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Large set (Ramsey theory). Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Large_set_(Ramsey_theory)&oldid=199088"