# 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 $X$ , a collection of subsets $\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 $A\in \mathbb {S}$ , 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 {S}$ . Ramsey theory is sometimes characterized as the study of which collections $\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 $\mathbb {N}$ : the upper density ${\overline {d}}(A)$  of $A\subset \mathbb {N}$  is defined as ${\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {|\{1,2,\ldots ,n\}\cap A|}{n}}.$  (Szemerédi's theorem)
• For any ultrafilter $\mathbb {U}$  on a set $X$ , $\mathbb {U}$  is partition regular: for any $A\in \mathbb {U}$ , if $A=C_{1}\sqcup \cdots \sqcup C_{n}$ , then exactly one $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 $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 {N}$ . Let $\mathbb {S} ^{n}=\bigcup _{A\subset \mathbb {N} }^{}[A]^{n}$ . For each n, $\mathbb {S} ^{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 $\Delta$ -sets: $A\subset \mathbb {N}$  is a $\Delta$ -set if $A$  contains the set of differences $\{s_{m}-s_{n}:m,n\in \mathbb {N} ,n  for some sequence $\langle s_{n}\rangle _{n=1}^{\omega }$ .
• the set of barriers on $\mathbb {N}$ : call a collection $\mathbb {B}$  of finite subsets of $\mathbb {N}$  a barrier if:
• $\forall X,Y\in \mathbb {B} ,X\not \subset Y$  and
• for all infinite $I\subset \cup \mathbb {B}$ , there is some $X\in \mathbb {B}$  such that the elements of X are the smallest elements of I; i.e. $X\subset I$  and $\forall i\in I\setminus X,\forall x\in X,x .
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 (FolkmanRado–Sanders, 1968).
• (m, p, c)-sets (Deuber, 1973)
• IP sets (Hindman, 1974, see also Hindman, Strauss, 1998)
• MTk 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 {N}$ , the Stone–Čech compactification of the integers. (Furstenberg, 1981, see also Hindman, Strauss, 1998)

## Diophantine equations

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