Milliken-Taylor theorem

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 [http://www.math.union.edu/people/faculty/publications/taylora.html Alan D. Taylor] .

Let mathcal{P}_f(mathbb{N}) denote the set of finite subsets of mathbb{N}. Given a sequence of integers langle a_n angle_{n=0}^{infty} subset mathbb{N} and nowrap|"k" > 0 let : [FS(langle a_n angle_{n=0}^{infty})] ^k_< = left { left { sum_{t in alpha_1}x_t, ... , sum_{t in alpha_k}x_t ight }: alpha_1 <...< alpha_k in mathcal{P}_f(mathbb{N}) ight },where alpha < eta in mathcal{P}_f(mathbb{N}) if and only if maxα [S] ^k denote the "k"-element subsets of a set "S". The Milliken-Taylor theorem says that for any finite partition [mathbb{N}] ^k=C_1 cup C_2 cup ... cup C_r, there exist some nowrap|"i" &lt; "r" + 1 and a sequence langle x_n angle_{n=0}^{infty} subset mathbb{N} such that [FS(langle a_n angle_{n=0}^{infty})] ^k_< subset C_i.

For each langle a_n angle_{n=0}^{infty} subset mathbb{N}, call [FS(langle a_n angle_{n=0}^{infty})] ^k_< an "MTk set". Then, alternatively, the Milliken-Taylor theorem asserts that the collection of MT"k" sets is partition regular for each "k".

References

#K. Milliken, Ramsey's Theorem with sums or unions, "J. Comb. Theory (Series A)" 18 (1975), 276-290
#A. Taylor, A canonical partition relation for finite subsets of &omega;, "J. Comb. Theory (Series A)" 21 (1976), 137-146


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • 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

  • List of theorems — This is a list of theorems, by Wikipedia page. See also *list of fundamental theorems *list of lemmas *list of conjectures *list of inequalities *list of mathematical proofs *list of misnamed theorems *Existence theorem *Classification of finite… …   Wikipedia

  • List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia

  • Ramsey theory — This article provides an introduction. For a more detailed and technical article, see Ramsey s theorem. Ramsey theory, named for Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear. Problems in… …   Wikipedia

  • 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… …   Wikipedia

  • List of important publications in physics — Optics Book of Optics *Ibn al Haytham (Alhacen)Description: The Book of Optics (Arabic: Kitab al Manazir , Latin: De Aspectibus ) is a seven volume treatise on optics and physics, written by the Iraqi Arab Muslim scientist Ibn al Haytham… …   Wikipedia

Share the article and excerpts

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