Partition regularity

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

Given a set $X$, a collection of subsets $\mathbb{𝕊}\subset {𝒫}(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 $A\in \mathbb{𝕊}$, and any finite partition $A=C_1\cup C_2\cup \cdots \cup C_n$, there exists an i ≤ n such that $C_i$ belongs to $\mathbb{𝕊}$. Ramsey theory is sometimes characterized as the study of which collections $\mathbb{𝕊}$ 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 $\mathbb{\mathbb{N}}$: the upper density $\bar{d}(A)$ of $A\subset \mathbb{\mathbb{N}}$ is defined as $\bar{d}(A)=\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{|\{1,2,\dots ,n\}\cap A|}{n}.$ (Szemerédi's theorem)
• For any ultrafilter $\mathbb{𝕌}$ on a set $X$, $\mathbb{𝕌}$ is partition regular: for any $A\in \mathbb{𝕌}$, if $A=C_1\bigsqcup \cdots \bigsqcup C_n$, then exactly one $C_i\in \mathbb{𝕌}$.
• Sets of recurrence: a set R of integers is called a set of recurrence if for any measure-preserving transformation $T$ of the probability space (Ω, β, μ) and $A\in \beta$ of positive measure there is a nonzero $n\in R$ so that $\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 $[A{]}^n$ be the set of all n-subsets of $A\subset \mathbb{\mathbb{N}}$. Let ${\mathbb{𝕊}}^n=\bigcup _{A\subset \mathbb{\mathbb{N}}}^{}[A{]}^n$. For each n, ${\mathbb{𝕊}}^n$ is partition regular. (Ramsey, 1930).
• For each infinite cardinal $\kappa$, the collection of stationary sets of $\kappa$ is partition regular. More is true: if $S$ is stationary and $S=\bigcup _{\alpha <\lambda }{S}_{\alpha }$ for some $\lambda <\kappa$, then some $S_{\alpha }$ is stationary.
• The collection of $\mathrm{\Delta }$-sets: $A\subset \mathbb{\mathbb{N}}$ is a $\mathrm{\Delta }$-set if $A$ contains the set of differences $\{s_m-s_n:m,n\in \mathbb{\mathbb{N}},n<m\}$ for some sequence $⟨s_n{⟩}_{n=1}^{\mathrm{\infty }}$.
• The set of barriers on $\mathbb{\mathbb{N}}$: call a collection $\mathbb{𝔹}$ of finite subsets of $\mathbb{\mathbb{N}}$ a barrier if:
  • $\mathrm{\forall }X,Y\in \mathbb{𝔹},X\subset ̸Y$ and
  • for all infinite $I\subset \cup \mathbb{𝔹}$, there is some $X\in \mathbb{𝔹}$ such that the elements of X are the smallest elements of I; i.e. $X\subset I$ and $\mathrm{\forall }i\in I\setminus X,\mathrm{\forall }x\in X,x<i$.

This generalizes Ramsey's theorem, as each $[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 (Jon Folkman, Richard Rado, and J. Sanders, 1968).
• (m, p, c)-sets
• IP sets
• MT^k sets for each k, i.e. k-tuples of finite sums (Milliken–Taylor, 1975)
• Central sets; i.e. the members of any minimal idempotent in $\beta \mathbb{\mathbb{N}}$, the Stone–Čech compactification of the integers. (Furstenberg, 1981, see also Hindman, Strauss, 1998)

Diophantine equations

A Diophantine equation $P(\mathbf{𝐱})=0$ is called partition regular if the collection of all infinite subsets of $\mathbb{\mathbb{N}}$ containing a solution is partition regular. Rado's theorem characterises exactly which systems of linear Diophantine equations $\mathbf{𝐀}\mathbf{𝐱}=\mathbf{𝟎}$ are partition regular. Much progress has been made recently on classifying nonlinear Diophantine equations.

Further reading

• "Partition regular structures contained in large sets are abundant". Journal of Combinatorial Theory. Series A 93 (1): 18–36. 2001. doi:10.1006/jcta.2000.3061.