This article includes a list of general references but lacks sufficient corresponding inline citations. (September 2015) |
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.
Necessary conditions for largeness include:
Two sufficient conditions are:
The first sufficient condition implies that if S is a thick set, then S is large.
Other facts about large sets include:
If is large, then for any , is large.
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:
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. In 2026, Ryan Alweiss and Sohail Farhangi posted a preprint claiming to disprove this conjecture by constructing a set that is 2-large but not 3-large. They also showed that the family of 2-large sets is not partition regular, answering another question of Brown, Graham, and Landman.