Misplaced Pages

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (September 2015) (Learn how and when to remove this message)

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 ${\displaystyle S=\{s_{1},s_{2},s_{3},\dots \}}$ is large, it is not the case that s_k≥3s_k-1 for k≥ 2.

Two sufficient conditions are:

• If S contains n-cubes for arbitrarily large n, then S is large.
• If ${\displaystyle S=p(\mathbb {N} )\cap \mathbb {N} }$ where ${\displaystyle p}$ is a polynomial with ${\displaystyle p(0)=0}$ and positive leading coefficient, then ${\displaystyle 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.
• ${\displaystyle k\cdot \mathbb {N} =\{k,2k,3k,\dots \}}$ is large.
• If S is large, ${\displaystyle k\cdot S}$ is also large.

If ${\displaystyle S}$ is large, then for any ${\displaystyle m}$, ${\displaystyle S\cap \{x:x\equiv 0{\pmod {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.

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

• Basic concepts in set theory
• Ramsey theory
• Theorems in discrete mathematics