The Strange Logic of Random Graphs

The Strange Logic of Random Graphs is a book on zero-one laws for random graphs. It was written by Joel Spencer and published in 2001 by Springer-Verlag as volume 22 of their book series Algorithms and Combinatorics.

Topics

The random graphs of the book are generated from the Erdős–Rényi–Gilbert model $G(n,p)$ in which $n$ 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 $p$ of making a connection. A zero-one law is a theorem stating that, for certain properties of graphs, and for certain choices of $p$, the probability of generating a graph with the property tends to zero or one in the limit as $n$ goes to infinity.

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 $G(n,1/2)$ for every property that can be described in the first-order logic of graphs. 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. For other choices of $p$, other outcomes can occur. For instance, the limiting probability of containing a triangle is between 0 and 1 when $p=c/n$ for a constant $c$; it tends to 0 for smaller choices of $p$ and to 1 for larger choices. The function $1/n$ is said to be a threshold for the property of containing a triangle, meaning that it separates the values of $p$ with limiting probability 0 from the values with limiting probability 1.

The main result of the book (proved by Spencer with Saharon Shelah) is that irrational powers of $n$ are never threshold functions. That is, whenever $a>0$ is an irrational number, there is a zero-one law for the first-order properties of the random graphs $G(n,n^{-a})$. A key tool in the proof is the Ehrenfeucht–Fraïssé game.

Audience and reception

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. Reviewer Alessandro Berarducci calls the book "beautifully written" and its subject "fascinating".