The Strange Logic of Random Graphs explained
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
in which
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
of making a connection. 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
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
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
, other outcomes can occur.For instance, the limiting probability of containing a triangle is between 0 and 1 when
for a constant
; it tends to 0 for smaller choices of
and to 1 for larger choices. The function
is said to be a
threshold for the property of containing a triangle, meaning that it separates the values of
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
are never threshold functions. That is, whenever
is an
irrational number, there is a zero-one law for the first-order properties of the random graphs
. 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".
