Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  794.05086
Autor:  Erdös, Paul; Hattingh, Johannes H.
Title:  Asymptotic bounds for irredundant Ramsey numbers. (In English)
Source:  Quaest. Math. 16, No.3, 319-331 (1993).
Review:  Let G(V,E) be a graph. A set of vertices X\subseteq V is said to be irredundant if each vertex x in X is either an isolated vertex in the subgraph induced by X or there is vertex y in V-X which is incident with x and no other vertex in X. The irredundant Ramsey number s(m,n) is the smallest positive integer s so that, in every red-blue coloring of the edges of the complete graph on s vertices, either the blue graph contains an m-element irredundant set or the red graph contains an n-element irredundant set. The main result of this paper is
Theorem 1. For each m \geq 3 there is a positive constant Cm such that

s(m,n) > Cm({n\over log n}){m2- m-1\over 2(m-1)}.

Reviewer:  J.E.Graver (Syracuse)
Classif.:  * 05C55 Generalized Ramsey theory
Keywords:  bounds; irredundant Ramsey number

© 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