Graphical evolution. An introduction to the theory of random graphs. (English) Zbl 0566.05002

Wiley-Interscience Series in Discrete Mathematics. A Wiley-Interscience Publication. New York etc.: John Wiley & Sons. XVII, 177 p. £40.40 (1985).
The theory of evolution of random graphs was found in 1959 and 1960 by Paul Erdős and Alfred Rényi in two now classical pioneering papers. Their many beautiful and unexpected results have caught the interest of combinatorists and probabilists. This book stresses the enumerative or combinatorial aspects of the theory and gives an excellent exposition of several important topics on random graphs.
After a brief review of graphical enumeration and an introduction of three basic probability models for graphs, the ground is set to discuss some of the main results on threshold functions. The fact that random graphs undergo sudden structural changes as the number of edges increases is proved, and various limiting distributions are derived. The links with phase transitions in chemical systems are mentioned and may thrill the readers’ curiosity for applications, but no efforts are made to discuss real applications. The potential for applications in computer science, chemistry and microbiology is evident, and it is also evident that these applications are likely to require more elaborate probability models than the ones discussed here. The last chapter contains some results on how to generate random graphs of different kinds, in particular random regular graphs and random trees.
The main text of about 120 pages is accompanied by an appendix section of about 40 pages covering relevant combinatorics, graph theory and probability theory. This makes the book an easy introduction to the subject. It is a pleasure to read this well and wittily written book.
Reviewer: O.Frank


05-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics
05C80 Random graphs (graph-theoretic aspects)
60C05 Combinatorial probability
60K35 Interacting random processes; statistical mechanics type models; percolation theory