Partition regular

Partition regular

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.


* 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 sets 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 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, x.: 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, see also Hindman, Strauss, 1998)

* MTk 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)


# 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.
# 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.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Partition topology — In mathematics, the partition topology is a topology that can be induced on any set X by partitioning X into disjoint subsets P; these subsets form the basis for the topology. There are two important examples which have their own names: The… …   Wikipedia

  • Partition (database) — A partition is a division of a logical database or its constituting elements into distinct independent parts. Database partitioning is normally done for manageability, performance or availability reasons.A popular and favourable application of… …   Wikipedia

  • First Partition of Poland — The First Partition of Poland or First Partition of the Polish Lithuanian Commonwealth took place in 1772 as the first of three partitions that ended the existence of the Polish Lithuanian Commonwealth by 1795. The first partition was carried out …   Wikipedia

  • Noncrossing partition — A noncrossing partition of ten points In combinatorial mathematics, the topic of noncrossing partitions has assumed some importance because of (among other things) its application to the theory of free probability. The set of all noncrossing… …   Wikipedia

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

  • Halpern-Lauchli theorem — In mathematics, the Halpern Läuchli theorem is a partition result about finite products of infinite trees. Its original purpose was to give a model for set theory in which the Boolean prime ideal theorem is true but the axiom of choice is false.… …   Wikipedia

  • IP set — In mathematics, an IP set is a set of natural numbers which contains all finite sums of some infinite set.The finite sums of a set D of natural numbers are all those numbers that can be obtained by adding up the elements of some finite nonempty… …   Wikipedia

  • Milliken-Taylor theorem — In mathematics, the Milliken Taylor theorem in combinatorics is a generalization of both Ramsey s theorem and Hindman s theorem. It is named after Keith Milliken and [ Alan D.… …   Wikipedia

  • Milliken's tree theorem — In mathematics, Milliken s tree theorem in combinatorics is a partition theorem generalizing Ramsey s theorem to infinite trees, objects with more structure than sets. Let T be a finitely splitting rooted tree of height ω, n a positive integer,… …   Wikipedia

  • Milliken–Taylor theorem — In mathematics, the Milliken–Taylor theorem in combinatorics is a generalization of both Ramsey s theorem and Hindman s theorem. It is named after Keith Milliken and Alan D. Taylor. Let denote the set of finite subsets of . Given a sequence of… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”