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

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