Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 858.05073
Autor: Erdös, Paul; Tuza, Zsolt; Valtr, Pavel
Title: Ramsey-remainder. (In English)
Source: Eur. J. Comb. 17, No.6, 519-532 (1996).
Review: The following general question is considered: Given a positive integer k, find the minimum number rr(k) such that any sufficiently large set S belonging to some class S can be decomposed into ``regular'' sets of size at least k with a remainder set of size at most rr(k). The number rr(k) is the Ramsey-remainder. It is shown for example, that if S is the set of all posets, and regularity refers to a poset being a chain or an antichain, then rr(k) = (k-1)(k-2) = r(k,k-1), where r(k,k-1) is the poset Ramsey number. A similar result is proved when S is the class of all finite r-uniform complete hypergraphs the edges of which are colored by c colors and a regular hypergraph is one that is monochromatic. In this case rr(k) = rc,k(k)-1. Other interesting Ramsey-remainder results are investigated, in particular, when S is the class of finite sets of points in general position in the plane and regularity refers to convexity. In this later case a sharp bound for the corresponding Ramsey-remainder number is obtained if the Erdös-Szekeres conjecture on the Ramsey number for convex sets in the plane is true.
Reviewer: R.Faudree (Memphis)
Classif.: * 05C55 Generalized Ramsey theory
05D10 Ramsey theory
Keywords: Ramsey-remainder; Ramsey number; hypergraph; Erdös-Szekeres conjecture
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag