Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 794.05084
Autor: Erdös, Paul; Faudree, Ralph J.
Title: Size Ramsey functions. (In English)
Source: Halász, G. (ed.) et al., Sets, graphs and numbers. A birthday salute to Vera T. Sós and András Hajnal. Amsterdam: North-Holland Publishing Company, Colloq. Math. Soc. János Bolyai. 60, 219-238 (1992).
Review: From the authors' abstract: ``For any given pair of graphs G and H there is the Ramsey number r = r(G,H). Any two-coloring of the edges of a Kr will give either a G in the first color or an H in the second color, and this is denoted by Kr ––> (G,H). We will investigate subgraphs L of Kr such that L ––> (G,H). In particular, we will consider two extremal functions: the upper size Ramsey number u(G,H), which is the minimum number such that if a subgraph L of Kr has at least u(G,H) edges, then L ––> (G,H), and the lower size Ramsey number l(G,H), which is the minimum number of edges in any subgraph L of Kr such that L ––> (G,H). For some pairs of graphs (G,H) the functions u(G,H) and l(G,H) will be determined precisely, and bounds will be given in other cases. Also, the relationship between the size Ramsey number \tilde r(G,H), which is the minimum number of edges in a graph F such that F ––> (G,H), and the restricted size Ramsey number will be considered.''
Typical of the results in this paper is:
Theorem 6. For n \geq 3, and G = K3, B2, or C5, u(G,K1,n) = ({2n+1\atop 2})- [{n+1\over 2}] and l(G,K1,n) = ({2n+1\atop 2})- ({n\atop 2}).
Reviewer: J.E.Graver (Syracuse)
Classif.: * 05C55 Generalized Ramsey theory
Keywords: Ramsey functions; Ramsey number; size Ramsey number
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag