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, Ci 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 \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)
  • 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: \{A \subset \mathbb{N} : \forall B \in IP, A \cap B \neq \empty \}
  • MTk sets for each k, i.e. k-tuples of finite sums (Milliken-Taylor, 1975)


[edit] 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. W. Deuber, Mathematische Zeitschrift 133, (1973) 109-123
  4. N. Hindman, Finite sums from sequences within cells of a partition of N, J. Combinatorial Theory (Series A) 17 (1974) 1-11.
  5. C.St.J.A. Nash-Williams, On well-quasi-ordering transfinite sequences, Proc. Camb. Phil. Soc. 61 (1965), 33-39.
  6. J.Sanders, A Generalization of Schur's Theorem, Doctoral Dissertation, Yale University, 1968.