Random graphs. (English) Zbl 0968.05003

Janson, Svante; Łuczak, Tomasz; Ruciński, Andrzej

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.

Reviewer: Ove Frank (Stockholm)

MSC:

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

Keywords:

graph processes; Bernoulli graphs; uniform random graphs; random subsets; probabilities; perfect matchings; giant component; coloring; random regular graphs

Citations:

Zbl 0567.05042