Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 840.05085
Autor: Erdös, Paul; Gimbel, John
Title: A note on the largest H-free subgraph in a random graph. (In English)
Source: Alavi, Yousef (ed.) et al., Graph theory, combinatorics, and applications, Vol. 1. Proceedings of the sixth quadrennial international conference on the theory and applications of graphs held at Western Michigan University, Kalamazoo, Michigan, May 30-June 3, 1988. New York: John Wiley & Sons Ltd. Wiley-Interscience Publication. 435-437 (1991).
Review: Given a fixed graph H and a random graph G, in Model A with an edge probability of 1/2 , there is a c > 0 dependent only on H, such that G almost surely contains no H-free subgraph on c log n vertices, where n is the order of G.
Classif.: * 05C80 Random graphs
Keywords: random graph; probability; subgraph
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag