- Partition regular
In

mathematics , the notion of**partition regularity**incombinatorics is one approach to explaining when aset 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 $mathbb\{U\}\; i\; A\; =igcup\_1^n\; C\_i$, 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 $A\; in\; eta$ 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\; =\; igcup^\{\; \}\_\{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 set s of $kappa$ is partition regular. More is true: if $S$ is stationary and $S=igcup\_\{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\}\; math>\; for\; some\; sequence$ langle\; s\_n\; angle^omega\_\{n=1\}$.$

* 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 $forall\; i\; in\; I\; setminus\; X,\; forall\; x\; in\; X,\; xmath>.:\; This\; generalizesRamsey\text{'}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 (Folkman-Rado-Sanders, 1968).

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

*

IP set s (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 $etamathbb\{N\}$, 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.

*Wikimedia Foundation.
2010.*