Partition regularity

In combinatorics, a branch of mathematics, partition regularity is one notion of largeness for a collection of sets.

Given a set X, a collection of subsets \mathbb{S} \subset \mathcal{P}(X) is called partition regular if every set A in the collection has the property that, no matter how A is partitioned into finitely many subsets, at least one of the subsets will also belong to the collection. That is, for any A \in \mathbb{S}, and any finite partition A = C_1 \cup C_2 \cup \cdots \cup C_n, there exists an i  n, such that C_i belongs to \mathbb{S}. Ramsey theory is sometimes characterized as the study of which collections \mathbb{S} are partition regular.

Examples

This generalizes Ramsey's theorem, as each [A]^n is a barrier. (Nash-Williams, 1965)

References

  1. Vitaly 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. N. Hindman, D. Strauss, Algebra in the Stone–Čech compactification, De Gruyter, 1998
  7. J.Sanders, A Generalization of Schur's Theorem, Doctoral Dissertation, Yale University, 1968.
This article is issued from Wikipedia - version of the Monday, May 05, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.