Partition regular

From Wikipedia, the free encyclopedia

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.

[edit] 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 \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).

For each infinite cardinal $κ$ , the collection of stationary sets of $κ$ is partition regular. More is true: if $S$ is stationary and $S=\bigcup_{\alpha < \lambda} S_{\alpha}$ for some $λ < κ$ , then some $S α$ is stationary.

the collection of $Δ$ -sets: $A \subset \mathbb{N}$ is a $Δ$ -set if $A$ contains the set of differences $\{s_m - s_n : m,n \in \mathbb{N}, n<m \}$ for some sequence $\langle s_n \rangle^\omega_{n=1}$ .

the set of barriers on : call a collection of finite subsets of 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)

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)

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

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{N}$ , the Stone-Čech compactification of the integers. (Furstenberg, 1981)

[edit] References

V. Bergelson, N. Hindman Partition regular structures contained in large sets are abundant J. Comb. Theory (Series A) 93 (2001), 18-36.
T. Brown, 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.
J.Sanders, A Generalization of Schur's Theorem, Doctoral Dissertation, Yale University, 1968.