Rado–Folkman–Sanders Theorem

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

Given a set $X$, a collection of subsets $\mathbb \subset \mathcal(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$: the ''upper density'' $\overline(A)$ of $A \subset \mathbb$ is defined as $\overline(A) = \limsup_ \frac.$ (Szemerédi's theorem)
* For any Ultrafilter (set theory), ultrafilter $\mathbb$ on a set $X$, $\mathbb$ is partition regular: for any $A \in \mathbb$, if $A = C_1 \sqcup \cdots \sqcup 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^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's theorem, Van der Waerden, 1927).
* Let $[A]^n$ be the set of all ''n''-subsets of $A \subset \mathbb$. Let $\mathbb^n = \bigcup^_ [A]^n$. For each ''n'', $\mathbb^n$ is partition regular. (Ramsey's theorem, Ramsey, 1930).
* For each infinite cardinal number, cardinal $\kappa$, the collection of stationary sets of $\kappa$ is partition regular. More is true: if $S$ is stationary and $S=\bigcup_ S_$ for some $\lambda < \kappa$, then some $S_$ is stationary.
* The collection of $\Delta$-sets: $A \subset \mathbb$ is a $\Delta$-set if $A$ contains the set of differences $\$ for some sequence $\langle s_n \rangle^_$.
* The set of barriers on $\mathbb$: call a collection $\mathbb$ of finite subsets of $\mathbb$ a ''barrier'' if:
** $\forall X,Y \in \mathbb, X \not\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 \forall i \in I \setminus X, \forall x \in X, x.
: This generalizes Ramsey's theorem, as each $[A]^n$ is a barrier. (Crispin St. J. A. Nash-Williams, Nash-Williams, 1965)

* Finite products of infinite trees (Halpern–Läuchli theorem, 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
* Milliken–Taylor theorem, 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$, 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 $\N$ containing a solution is partition regular. Rado's theorem (Ramsey theory), 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.

References

Further reading

*{{cite journal
, last1=Bergelson , first1=Vitaly , authorlink1=Vitaly Bergelson
, last2=Hindman , first2=Neil
, title=Partition regular structures contained in large sets are abundant
, journal=Journal of Combinatorial Theory
, series=Series A
, volume=93
, issue=1
, date=2001
, pages=18–36
, doi=10.1006/jcta.2000.3061 , doi-access=free

Ramsey theory
Families of sets