In mathematics, the notion of partition regularity in combinatorics is one approach to explaining when a set system is "quite" large.
Given a set , a collection of subsets is called "partition regular" if for any , and any finite partition , then for some i ≤ n, contains an element of . Ramsey theory is sometimes characterized as the study of which collections are partition regular.
Examples
* the collection of all infinite subsets of an infinite set "X" is a prototypical example. In this case partition regularity asserts that every finite partition of an infinite set has an infinite cell (i.e. the infinite pigeonhole principle.)
* sets with positive upper density in : the "upper density" of is defined as .
* For any ultrafilter on a set , is partition regular. If , then for exactly one is .
* sets of recurrence: a set R of integers is called a "set of recurrence" if for any measure preserving transformation of the probability space (Ω, β, μ) and of positive measure there is a nonzero so that .
* Call a subset of natural numbers "a.p.-rich" if it contains arbitrarily long arithmetic progressions. Then the collection of a.p.-rich subsets is partition regular (Van der Waerden, 1927).
* Let be the set of all n-subsets of . Let . For each n, is partition regular. (Ramsey, 1930).
* For each infinite cardinal , the collection of stationary sets of is partition regular. More is true: if is stationary and for some , then some is stationary.
* the collection of -sets: is a -set if contains the set of differences