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