The Random Graph

A graph is a set of vertices, with some pairs joined by an edge. Take the vertices to be the natural numbers. For every pair of them, every pair, flip a fair coin. Heads, you draw an edge. Tails, you don't.

You have built a graph. Run the experiment again with fresh coins: different flips, different edges, so you would expect a different graph.

What you actually get, with probability one, is the same graph. Not edge for edge, but after relabeling the vertices, identical. There is a single countable graph that the random construction picks out almost surely. Erdős and Rényi proved it exists; Rado wrote down a construction. Call it $R$.

The extension property#

A graph has the extension property if for any two disjoint finite sets of vertices $U$ and $V$, there is a vertex $z$, outside both, connected to every vertex in $U$ and to no vertex in $V$. Any finite set to hit, any finite set to avoid: somewhere, a witness has exactly that pattern.

This is a strong condition. On a finite graph it is impossible: let $U$ and $V$ together cover every vertex, and no vertex is left to be the witness. So the extension property forces the graph to be infinite. Every theorem in this article comes from this single property.

The coin flips have it, almost surely#

Fix disjoint finite sets $U$ and $V$ of total size $k$. For any candidate vertex $z$ outside them, the $k$ edges from $z$ to $U\cup V$ were each decided by an independent coin flip, so $z$ has exactly the right pattern with probability $1/2^k$. A positive number.

The infinitely many candidates outside $U\cup V$ make their connections independently of one another, and the probability that the first $N$ of them all fail is $(1-1/2^k{)}^N$, which goes to zero. So for this fixed pair, a witness exists almost surely.

There are countably many pairs $(U,V)$, and a countable union of probability-zero failure events still has probability zero. Almost surely, every pair has its witness.

Only one such graph#

One more fact: any two countable graphs with the extension property are isomorphic. The proof is the back-and-forth argument.

Enumerate the vertices of both graphs and pair $a_1$ with $b_1$. Now alternate sides: take the smallest unpaired vertex on one side, read off its adjacency pattern to the already-paired vertices, and use the other graph's extension property to find a partner with the same pattern; pair them. Because the construction keeps returning to each side, no vertex is missed forever, and the partial bijection grows into a total one that preserves and reflects edges: an isomorphism.

Put the two facts together: flip the coins twice, and almost surely both outcomes have the extension property, hence are isomorphic. That is why $R$ deserves the definite article.

Rado's construction#

Now drop the randomness entirely. Richard Rado, in 1964: take the vertex set to be the natural numbers, and for $n<m$, draw an edge if and only if the $n$-th bit of $m$, written in binary, is 1. That is the whole rule. No coins.

Check extension. Given disjoint finite $U$ and $V$, choose

$$z=\sum _{i\in U}{2}^i+2^M$$

where $M$ is larger than every element of $U\cup V$. Then $z$ is bigger than everything in sight, so the bit rule applies, and the $i$-th bit of $z$ is 1 for every $i\in U$ and 0 for every $i\in V$. The extension property holds, so by uniqueness this graph is $R$. A deterministic graph, written down with no probability at all, is the random graph.

Pause and try: in Rado's graph, list the neighbors of 5 among the numbers 0 through 9.

Two directions to check. For smaller numbers $n<5$, ask whether the $n$-th bit of $5=101$ in binary is 1: bits 0 and 2 are set, so 5 is adjacent to 0 and 2, and not to 1, 3, or 4. For larger $m>5$, ask whether the 5th bit of $m$ is 1, which first happens at $m=32$. So among 0 through 9, the neighbors of 5 are exactly 0 and 2.

Universal, homogeneous, indestructible#

Once you have the extension property, properties of $R$ fall right out.

$R$ is universal: every finite or countable graph embeds in it as an induced subgraph. Embed the target one vertex at a time; extension supplies, at each step, a vertex with exactly the right adjacencies to the previous ones.

$R$ is homogeneous: every isomorphism between two finite induced subgraphs extends to an automorphism of all of $R$. Run back-and-forth again, seeded with the given finite isomorphism. One consequence: the automorphism group has the cardinality of the continuum. $R$ is as symmetric as a countable graph can be.

$R$ is indestructible. Delete any finite set of vertices: the witnesses were infinite in number anyway, so extension survives. Delete an edge: still $R$. Take the complement: the extension property is symmetric in $U$ and $V$, so still $R$. Partition the vertices into finitely many parts: at least one part induces a copy of $R$.

And $R$ is not alone. Forbid triangles, so a pattern may only be requested when the witness creates none, and the same machinery yields the Henson graph: universal for triangle-free graphs, homogeneous, countable. For finite linear orders the pattern is a gap, and a countable order meeting every gap request is dense without endpoints: by Cantor's isomorphism theorem, the rationals. These are Fraïssé limits, countable structures containing all the allowed finite pieces, as symmetric as possible. Finite graphs give $R$, the first example of a much larger pattern.

The zero-one law#

Now back to finite graphs. For each $n$, let $G(n,1/2)$ be a graph on $n$ labeled vertices, each pair joined independently with probability one half. A first-order sentence about graphs is built from variables ranging over vertices, the edge relation, equality, boolean connectives, and quantifiers over vertices. "Contains a triangle" is first-order. "Connected" is not.

The zero-one law, proved by Fagin in 1976, and earlier by Glebskii, Kogan, Liogon'kii, and Talanov in 1969: for every first-order sentence $\phi$, the probability that $G(n,1/2)$ satisfies $\phi$ tends to 0 or to 1 as $n$ grows. Never anything in between.

The proof goes through $R$. Each instance of the extension property, for fixed sizes of $U$ and $V$, is a first-order sentence; call these the extension axioms. Step one: each axiom holds on $G(n,1/2)$ with probability tending to 1. This is the earlier calculation in finite form: the probability that no witness exists is at most $(1-1/2^k{)}^{n-k}$, and a union bound over the polynomially many pairs still goes to zero. Step two: the extension axioms form a complete theory. That is the back-and-forth argument again: every countable model is isomorphic to $R$, and by Vaught's test, a countably categorical theory in a countable language is complete.

Proofs are finite, so when the complete theory decides a sentence $\phi$, it uses only finitely many extension axioms, all almost surely true for large $n$. And a complete theory decides every sentence. So every first-order $\phi$ is almost surely true or almost surely false on $G(n,1/2)$, and the limiting probability is the truth value of $\phi$ in $R$.

The first-order restriction matters: first-order logic cannot say "the number of vertices is even," while second-order logic can, by quantifying a pairing of the vertices, and then the limit need not exist at all: parity alternates with $n$.

Asking R#

The zero-one law is also a calculator: to learn whether a first-order property holds for almost all finite graphs, ask $R$.

Does the random finite graph almost surely contain a triangle? In $R$, take any edge $xy$; extension with $U=\{x,y\}$ and $V=\mathrm{\varnothing }$ gives a common neighbor $z$, and $xyz$ is a triangle. Yes.

Does every vertex almost surely have a non-neighbor? Extension with $U=\mathrm{\varnothing }$ and $V=\left\{x\right\}$. Yes.

Does the random finite graph almost surely have an isolated vertex? In $R$, no: for any $x$, extension with $U=\left\{x\right\}$ gives a neighbor, so no vertex of $R$ is isolated. The limiting probability is zero.

Random plus countable plus independent: with probability one, a single graph. You cannot generate variation. Shuffle the natural numbers however you like, flip the coins again, take the complement, delete any finite piece. $R$ looks back.

If you remember three things#

1. One condition, the extension property, characterizes the random graph: the coin flips satisfy it almost surely, and back-and-forth makes any two countable graphs with it isomorphic.
2. The random graph is not random: Rado's rule, an edge between $n<m$ exactly when the $n$-th bit of $m$ is 1, constructs it deterministically.
3. The zero-one law turns asymptotic probability questions about finite graphs into truth questions about the single graph $R$: every first-order property holds almost surely or almost never.