Partition regularity explained

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 S \subset l{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 S , and any finite partition A = C _{1} \cup C _{2} \cup … \cup C _{n} , there exists an i ≤ n such that C _{i} belongs to S . Ramsey theory is sometimes characterized as the study of which collections 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

N : the upper density \overline{d}(A) of A \subset N is defined as \overline{d}(A) = \limsup _{n} (| \{ 1 , 2 ,\ldots,n\)/(\cap) A|}{n}. (Szemerédi's theorem)U on a set X , U is partition regular: for any A \in U , if A = C _{1} \sqcup … \sqcup C _{n} , then exactly one C _{i} \in 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 N . Let S ^{n} = c up _{A \subset N} [A] ^{n} . For each n, S ^{n} is partition regular. (Ramsey, 1930).\kappa , the collection of stationary sets of \kappa is partition regular. More is true: if S is stationary and S = c up _{\alpha} S _{\alpha} for some λ < \kappa , then some S _{\alpha} is stationary.

• The collection of

\Delta -sets: A \subset N is a \Delta -set if A contains the set of differences \{s _{m} - s _{n} : m,n \in N , n<m \} for some sequence \langle s _{n} \rangle ^{inf ty} _{n =1} .

• The set of barriers on

N : call a collection B of finite subsets of N a barrier if:\forall X,Y \in B , X \not\subset Y and

• • for all infinite

I \subset \cup B , there is some X \in 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<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 N , the Stone–Čech compactification of the integers. (Furstenberg, 1981, see also Hindman, Strauss, 1998)

Diophantine equations

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

Further reading

• Vitaly Bergelson, N. Hindman Partition regular structures contained in large sets are abundant J. Comb. Theory A 93 (2001), 18–36.