# Partition regularity

(Redirected from Partition regular)

In combinatorics, a branch of mathematics, partition regularity is one notion of largeness for a collection of sets.

Given a set ${\displaystyle X}$, a collection of subsets ${\displaystyle \mathbb {S} \subset {\mathcal {P}}(X)}$ is called partition regular if every set A in the collection has the property that, no matter how A is partitioned into finitely many subsets, at least one of the subsets will also belong to the collection. That is, for any ${\displaystyle A\in \mathbb {S} }$, and any finite partition ${\displaystyle A=C_{1}\cup C_{2}\cup \cdots \cup C_{n}}$, there exists an i ≤ n, such that ${\displaystyle C_{i}}$ belongs to ${\displaystyle \mathbb {S} }$. Ramsey theory is sometimes characterized as the study of which collections ${\displaystyle \mathbb {S} }$ 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 ${\displaystyle \mathbb {N} }$: the upper density ${\displaystyle {\overline {d}}(A)}$ of ${\displaystyle A\subset \mathbb {N} }$ is defined as ${\displaystyle {\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {|\{1,2,\ldots ,n\}\cap A|}{n}}.}$
• For any ultrafilter ${\displaystyle \mathbb {U} }$ on a set ${\displaystyle X}$, ${\displaystyle \mathbb {U} }$ is partition regular. If ${\displaystyle \mathbb {U} \ni A=\bigcup _{1}^{n}C_{i}}$, then for exactly one ${\displaystyle i}$ is ${\displaystyle C_{i}\in \mathbb {U} }$.
• sets of recurrence: a set R of integers is called a set of recurrence if for any measure preserving transformation ${\displaystyle T}$ of the probability space (Ω, β, μ) and ${\displaystyle A\in \ \beta }$ of positive measure there is a nonzero ${\displaystyle n\in R}$ so that ${\displaystyle \mu (A\cap T^{n}A)>0}$.
• 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 ${\displaystyle [A]^{n}}$ be the set of all n-subsets of ${\displaystyle A\subset \mathbb {N} }$. Let ${\displaystyle \mathbb {S} ^{n}=\bigcup _{A\subset \mathbb {N} }^{}[A]^{n}}$. For each n, ${\displaystyle \mathbb {S} ^{n}}$ is partition regular. (Ramsey, 1930).
• For each infinite cardinal ${\displaystyle \kappa }$, the collection of stationary sets of ${\displaystyle \kappa }$ is partition regular. More is true: if ${\displaystyle S}$ is stationary and ${\displaystyle S=\bigcup _{\alpha <\lambda }S_{\alpha }}$ for some ${\displaystyle \lambda <\kappa }$, then some ${\displaystyle S_{\alpha }}$ is stationary.
• the collection of ${\displaystyle \Delta }$-sets: ${\displaystyle A\subset \mathbb {N} }$ is a ${\displaystyle \Delta }$-set if ${\displaystyle A}$ contains the set of differences ${\displaystyle \{s_{m}-s_{n}:m,n\in \mathbb {N} ,n for some sequence ${\displaystyle \langle s_{n}\rangle _{n=1}^{\omega }}$.
• the set of barriers on ${\displaystyle \mathbb {N} }$: call a collection ${\displaystyle \mathbb {B} }$ of finite subsets of ${\displaystyle \mathbb {N} }$ a barrier if:
• ${\displaystyle \forall X,Y\in \mathbb {B} ,X\not \subset Y}$ and
• for all infinite ${\displaystyle I\subset \cup \mathbb {B} }$, there is some ${\displaystyle X\in \mathbb {B} }$ such that the elements of X are the smallest elements of I; i.e. ${\displaystyle X\subset I}$ and ${\displaystyle \forall i\in I\setminus X,\forall x\in X,x.
This generalizes Ramsey's theorem, as each ${\displaystyle [A]^{n}}$ is a barrier. (Nash-Williams, 1965)
• finite products of infinite trees (Halpern–Läuchli, 1966)
• piecewise syndetic sets (Brown, 1968)
• Call a subset of natural numbers i.p.-rich if it contains arbitrarily large finite sets together with all their finite sums. Then the collection of i.p.-rich subsets is partition regular (FolkmanRado–Sanders, 1968).
• (m, p, c)-sets (Deuber, 1973)
• central sets; i.e. the members of any minimal idempotent in ${\displaystyle \beta \mathbb {N} }$, the Stone–Čech compactification of the integers. (Furstenberg, 1981, see also Hindman, Strauss, 1998)