Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  759.05095
Autor:  Erdös, Paul; Galvin, Fred
Title:  Some Ramsey-type theorems. (In English)
Source:  Discrete Math. 87, No.3, 261-269 (1991).
Review:  For any set A let [A]r denote the collection of r-element subsets of A. By a k-coloring of the r-subsets of A we mean a function f: [A]r ––> {1,...,k}. A set X\subset A is said to be f-homogeneous if f is a constant on [X]r. The partition symbol a ––> (x)rk denotes the assertion: given a set A with | A| = a and a coloring f: [A]r ––> {1,...,k}, there is an f- homogeneous set X\subset A with |X| \leq x.
The main result of this paper is
Theorem 2.1. Let r and k be positive integers, and let the function \phi: N ––> R be such that n ––> (\phi(n))rk+1 holds for all sufficienty large n. Given any coloring f: [N]r ––> {1,...,k}, there is a set A\subsetN such that: (1) |{f(X): X in [A]r}| \leq 2r-1; (2) |A\cap{1,...,n}| \geq \phi(n) for infinitely many n.
Reviewer:  J.E.Graver (Syracuse)
Classif.:  * 05D10 Ramsey theory
Keywords:  Ramsey-type theorems; homogeneous set; partition; coloring

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page