Partition regularity

This article needs more citations. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Partition regularity" – news · newspapers · books · scholar · JSTOR (December 2009) (Learn how and when to remove this message)

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}}.}$ (Szemerédi's theorem)
• For any ultrafilter ${\displaystyle \mathbb {U} }$ on a set ${\displaystyle X}$, ${\displaystyle \mathbb {U} }$ is partition regular: for any ${\displaystyle A\in \mathbb {U} }$, if ${\displaystyle A=C_{1}\sqcup \cdots \sqcup C_{n}}$, then exactly one ${\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<m\}}$ for some sequence ${\displaystyle \langle s_{n}\rangle _{n=1}^{\infty }}$.
• 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<i}$.

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 (Jon Folkman, Richard Rado, and J. Sanders, 1968).
• (m, p, c)-sets ^{[clarification needed]}
• 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 ${\displaystyle \beta \mathbb {N} }$, the Stone–Čech compactification of the integers. (Furstenberg, 1981, see also Hindman, Strauss, 1998)

Diophantine equations

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

References

Further reading

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