Partition regularity

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

• 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\rightarrow \infty }{\frac {|\{1,2,\ldots ,n\}\cap A|}{n}}$.

• For any ultrafilter $\mathbb {U}$ on a set $X$, $\mathbb {U}$ is partition regular. If $\mathbb {U} =\bigcup _{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 \ \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 \mathbb {N}$. Let $\mathbb {S} ^{n}=\bigcup _{A\subset \mathbb {N} }^{}[A]^{n}$. For each n, $\mathbb {S} ^{n}$ is partition regular. (Ramsey, 1930).

• 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, 1933).

• 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\not \subset 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,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)

• IP sets (Hindman, 1974)

• IP* sets: $\{A\subset \mathbb {N} :\forall B\in IP,A\cap B\neq \emptyset \}$

• central sets; i.e. the members of any minimal idempotent in $\beta \mathbb {N}$, the Stone-Čech compactification of the integers.

• MT^k sets for each k, i.e. k-tuples of finite sums (Milliken-Taylor, 1975)

See also

• Bartel Leendert van der Waerden

References

1. V. Bergelson, N. Hindman Partition regular structures contained in large sets are abundant J. Comb. Theory (Series A) 93 (2001), 18-36.
2. T. Brown, An interesting combinatorial method in the theory of locally finite semigroups, Pacific J. Math. 36, no. 2 (1971), 285–289.
3. N. Hindman, Finite sums from sequences within cells of a partition of N, J. Combinatorial Theory (Series A) 17 (1974) 1-11.
4. C.St.J.A. Nash-Williams, On well-quasi-ordering transfinite sequences, Proc. Camb. Phil. Soc. 61 (1965), 33-39.