It was written by Joel Spencer and published in 2001 by Springer-Verlag as volume 22 of their book series Algorithms and Combinatorics.
The random graphs of the book are generated from the Erdős–Rényi–Gilbert model
vertices are given and a random choice is made whether to connect each pair of vertices by an edge, independently for each pair, with probability
A zero-one law is a theorem stating that, for certain properties of graphs, and for certain choices of
, the probability of generating a graph with the property tends to zero or one in the limit as
[1] A fundamental result in this area, proved independently by Glebskiĭ et al. and by Ronald Fagin, is that there is a zero-one law for
[2] Moreover, the limiting probability is one if and only if the infinite Rado graph has the property.
For instance, a random graph in this model contains a triangle with probability tending to one; it contains a universal vertex with probability tending to zero.
is said to be a threshold for the property of containing a triangle, meaning that it separates the values of
[1] The main result of the book (proved by Spencer with Saharon Shelah) is that irrational powers of
is an irrational number, there is a zero-one law for the first-order properties of the random graphs
[3] Although it is essentially the proof of a single theorem, aimed at specialists in the area, the book is written in a readable style that introduces the reader to many important topics in finite model theory and the theory of random graphs.
Reviewer Valentin Kolchin, himself the author of another book on random graphs, writes that the book is "self-contained, easily read, and is distinguished by elegant writing", recommending it to probability theorists and logicians.
[2] Reviewer Alessandro Berarducci calls the book "beautifully written" and its subject "fascinating".