Random graphs. (English) Zbl 0968.05003

Wiley-Interscience Series in Discrete Mathematics and Optimization. New York, NY: Wiley. xii, 333 p. (2000).
This book is a beautiful presentation of new developments in the asymptotic theory of random graphs. It covers the period since about 1985 when Bollobás’ monograph with the same title appeared (see Zbl 0567.05042). It emphasizes new techniques and tools that have successfully contributed to recent progress for Bernoulli graphs and uniform random graphs. Among the topics studied are thresholds for monotone properties of random subsets, exponential bounds for tail probabilities, thresholds for subgraph containment, perfect matchings, the emergence of the giant component, convergence in distribution, approximation by projection, vertex coloring and the chromatic number, edge coloring and monochromatic triangles, and random regular graphs. The last chapter gives results for families of graph properties by employing notions and facts from mathematical logic.


05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05C80 Random graphs (graph-theoretic aspects)
60C05 Combinatorial probability
60-02 Research exposition (monographs, survey articles) pertaining to probability theory
60F05 Central limit and other weak theorems
82B41 Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics


Zbl 0567.05042