Partition regular

In mathematics, the notion of partition regularity in combinatorics is one approach to explaining when a set system is "quite" large.

Given a set $X$, a collection of subsets $mathbb\{S\}\; subset\; mathcal\{P\}(X)$ is called "partition regular" if for any $A\; in\; mathbb\{S\}$, and any finite partition $A\; =\; C\_1\; cup\; C\_2\; cup\; ...\; cup\; C\_n$, then for some i ≤ n, $C\_i$ contains an element of $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\; ightarrow\; infty\}\; frac\{n\}$.

* For any ultrafilter $mathbb\{U\}$ on a set $X$, $mathbb\{U\}$ is partition regular. If , then for exactly one $i$ is $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 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 . 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 for some , 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

* 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\; otsubset\; 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

* 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 (Folkman-Rado-Sanders, 1968).

* (m,p,c)-sets (Deuber, 1973)

* IP sets (Hindman, 1974, see also Hindman, Strauss, 1998)

* 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 , the Stone-Čech compactification of the integers. (Furstenberg, 1981, see also Hindman, Strauss, 1998)

References

# V. Bergelson, N. Hindman [http://members.aol.com/nhfiles2/pdf/large.pdf Partition regular structures contained in large sets are abundant] "J. Comb. Theory (Series A)" 93 (2001), 18-36.
# T. Brown, [http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1102971066 An interesting combinatorial method in the theory of locally finite semigroups] , "Pacific J. Math." 36, no. 2 (1971), 285–289.
# W. Deuber, Mathematische Zeitschrift 133, (1973) 109-123
# N. Hindman, Finite sums from sequences within cells of a partition of N, "J. Combinatorial Theory" (Series A) 17 (1974) 1-11.
# C.St.J.A. Nash-Williams, On well-quasi-ordering transfinite sequences, "Proc. Camb. Phil. Soc." 61 (1965), 33-39.
# N. Hindman, D. Strauss, Algebra in the Stone-Čech compactification, De Gruyter, 1998
# J.Sanders, A Generalization of Schur's Theorem, Doctoral Dissertation, Yale University, 1968.