Large set (Ramsey theory)
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.
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 [math]\displaystyle{ S=\{s_1,s_2,s_3,\dots\} }[/math] 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 [math]\displaystyle{ S =p(\mathbb{N}) \cap \mathbb{N} }[/math] where [math]\displaystyle{ p }[/math] is a polynomial with [math]\displaystyle{ p(0)=0 }[/math] and positive leading coefficient, then [math]\displaystyle{ S }[/math] 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.
- [math]\displaystyle{ k\cdot \mathbb{N}=\{k,2k,3k,\dots\} }[/math] is large.
- If S is large, [math]\displaystyle{ k\cdot S }[/math] is also large.
If [math]\displaystyle{ S }[/math] is large, then for any [math]\displaystyle{ m }[/math], [math]\displaystyle{ S \cap \{ x : x \equiv 0\pmod{m} \} }[/math] 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
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
 |  |
