The graph that coin tosses always make

Two lists that are one order found that the countable orders which are dense and have no ends are all one order, relabelled, by matching two lists in a zigzag that kept every comparison. The zigzag used exactly one property of dense orders: whatever finite part had been matched, any new element could be answered on the other side, in the right gap. That property is not special to orders. This essay finds it in a graph, and the graph turns out to be the one that randomness produces.

Take the whole numbers as vertices, and for every pair of them toss a fair coin: heads they are joined, tails they are not. Infinitely many independent coin tosses, a graph that is random in every detail. Do it again with fresh coins and every edge may come out differently. And yet, as Paul Erdős and Alfréd Rényi proved in 1963, the two graphs are, with probability one, isomorphic — the same graph, with the vertices relabelled.

The graph they always make can also be written down with no coins at all. The figure below is the start of it: join two whole numbers $i < j$ when the $i$-th binary digit of $j$ is a one. So $3 = 11_2$ is joined to $0$ and $1$; $12 = 1100_2$ is joined to $2$ and $3$. Wilhelm Ackermann used this relation in 1937 to code finite sets as numbers, and Richard Rado showed in 1964 that it defines a graph with a remarkable property. It is called Rado’s graph, or simply the random graph.

The one property that matters #

The property is the graph’s version of density.

For any two finite disjoint sets of vertices $U$ and $V$, there is a vertex joined to every vertex of $U$ and to no vertex of $V$. Call a vertex like that a witness for the request $(U, V)$.

In Rado’s graph a witness can be written down. Let $m$ be the largest number in $U$ or $V$, and take

$$z = 2^{m+1} + \sum_{u \in U} 2^u.$$

Its binary digits are ones exactly at the positions in $U$ and at position $m + 1$, and zeros at every position in $V$. Since $z$ is larger than everything in $U$ and $V$, whether it is joined to each of them is read off its own digits — joined to $U$, not to $V$.

The figure checks five requests and the witnesses the formula gives, and also finds the smallest witness for each by search: usually far smaller than the formula’s, since smaller numbers can satisfy the request through the digits of the larger vertices in $U$ and $V$. What matters is not the size of the witness but that one always exists.

Why coin tosses produce it #

Now the coins. Fix a request: a set $U$ of $a$ vertices to be joined to and a set $V$ of $b$ vertices to avoid. For any other vertex $z$, the chance that $z$ is joined to all of $U$ and none of $V$ is $2^{-(a+b)}$, and these events are independent for different $z$. So the chance that none of the next $n$ vertices is a witness is $(1 - 2^{-(a+b)})^n$, which goes to nought.

Each request fails with probability nought, and there are only countably many requests — finite subsets of a countable set — so with probability one every request has a witness. The random graph has the extension property almost surely. The figure watches this happen in a finite piece: requests about three of the first ten vertices, answered by later ones, with the share answered climbing to all of them.

Nothing about a fair coin was used except that the chance of a witness was positive. With a coin that comes up heads one time in a hundred, or ninety-nine times in a hundred, each request’s chance is still positive and the same argument works. The random graph is the same graph for every edge probability strictly between nought and one. A graph with almost every edge present and a graph with almost none, built the same way, are isomorphic — which makes sense only because each has infinitely many vertices, and what an infinite graph “looks like” is decided by its extension property, not by its density.

One zigzag, one graph #

The extension property is all the zigzag needs.

Match the two graphs step by step, as the orders were matched. At a forth step take the next unmatched vertex of the first graph; it is joined to some of the already-matched vertices and not to others, so look on the other side for a vertex joined to exactly the partners of the first kind and none of the second — a witness for a finite request, which exists. At a back step do the same the other way. Every finite matching keeps edges and non-edges, which the figure checks pair by pair, and every vertex is eventually matched, so the union is an isomorphism.

So any two countable graphs with the extension property are isomorphic. The coin-toss graph has it with probability one; the bit graph has it outright; so the coin-toss graph is, with probability one, the bit graph. The same argument shows any two coin-toss graphs are isomorphic to each other. Randomness in every detail, and a single outcome. It is one of the few places in mathematics where a random construction produces a specific, nameable object rather than a typical member of a family.

The parallel with dense orders is exact. There, the property was “any finite configuration of matched elements can be extended by one more element in any gap”, and here it is “any finite configuration of vertices can be extended by one more vertex with any pattern of joins”. In both cases a structure with the property is unique among countable ones, and in both cases the uniqueness is proved by the same alternating matching.

Every graph is inside it #

The extension property also makes Rado’s graph contain every finite graph, and every countable one.

To find a copy of a given graph, place its vertices one at a time. Each new vertex must be joined to some of those already placed and not to the others — a finite request — so a witness can be chosen, and the copy grows without ever getting stuck. The figure places the ten vertices of Petersen’s graph this way and checks that the chosen vertices are joined exactly as Petersen’s are. Continued for ever, the same greedy placement copies any countable graph into Rado’s graph, each vertex’s joins to earlier vertices a finite request.

The figure uses a coin-toss graph rather than the bit graph, for a practical reason worth knowing. In the bit graph the witnesses the rule supplies are powers of two beyond everything chosen so far: a greedy search for Petersen’s graph there picks vertices up to 1,552 within nine steps, the tenth needs a witness beyond fifty million, and the rule’s own witness for it has more than fifteen hundred binary digits. The bit graph is a convenient definition and a terrible place to search. The coin-toss graph on three thousand vertices, which almost surely looks like the bit graph in every finite respect that matters here, has small witnesses everywhere.

A graph no finite damage can hurt #

The extension property is about finite requests, and it survives any finite change.

Delete finitely many vertices: every request about the remaining vertices still has infinitely many witnesses, since the rule produces witnesses beyond any bound, and only finitely many were deleted. So what remains has the extension property and is Rado’s graph again. Add or remove finitely many edges: a request can be spoiled only if its witness touched one of the changed edges, and there are witnesses beyond every changed vertex. Rado’s graph again. Take the complement, joining exactly the pairs that were not joined: the extension property is symmetric in $U$ and $V$, so the complement has it too. Rado’s graph again.

A stronger form holds. Split the vertices of Rado’s graph into two parts, any way at all. At least one of the parts, as a graph on its own, is Rado’s graph. The graph is indivisible: it cannot be cut into two pieces both of which have lost what makes it itself. It shares that property with the rationals, whose any two-part split leaves a part containing a copy of the rationals, and the resemblance is not an accident — both are the unique countable structures that are universal and homogeneous, containing every finite configuration and looking the same around every one.

Sets written in binary #

Ackermann’s reason for the binary rule had nothing to do with graphs. He wanted to show that the finite part of set theory — the sets built from the empty set by collecting finitely many sets already built — could be coded by whole numbers, and the binary digits record the membership. The number $0$ stands for the empty set; the number $j$ stands for the set whose members are the numbers $i$ at whose positions $j$ has a binary one. So $1$ stands for $\{0\}$, $2$ for $\{1\}$, $3$ for $\{0, 1\}$, and every finite set of finite sets gets exactly one number.

Under this coding, “$i$ is a member of $j$” is “the $i$-th digit of $j$ is one”, and Rado’s graph is membership with its direction forgotten: two hereditarily finite sets are joined when one is a member of the other. The extension property is then a statement a set theorist would find obvious. Given finite collections $U$ and $V$ of sets, the set $U \cup \{U \cup V\}$ contains every member of $U$ and nothing from $V$ — a witness, built by the axioms of pairing and union. The random graph and the finite part of the set theory whose countable models were met earlier are the same object seen from two directions.

The same trick for other structures #

The pattern of the rationals and this graph — a countable structure characterised by being able to answer every finite request, unique by a zigzag, containing every finite piece of its kind — is general, and Roland Fraïssé described it in 1954. Start with a class of finite structures that is closed under taking substructures and in which any two structures sharing a common part can be glued along it. Then there is exactly one countable structure that contains every member of the class and in which every isomorphism between finite parts extends to a symmetry of the whole: the class’s limit.

The finite linear orders have the rationals as their limit. The finite graphs have Rado’s graph. Finite tournaments — graphs with every edge given a direction — have the random tournament; finite partial orders have a generic countable partial order. And finite graphs with no triangle have a limit too, Henson’s graph, which contains every triangle-free graph and has every symmetry the definition asks for — though it is not what tossing coins produces, since a coin-toss graph contains triangles with probability one. Each limit is to its class what the party of six people is to Ramsey’s theorem: the place where every finite pattern the class allows is guaranteed to occur.

The zero-one law, from the other side #

This graph has appeared before without its name. Nearly always, or nearly never showed that for a first-order property of graphs — one expressible with quantifiers over vertices and the relation of being joined — the probability that a random graph on $n$ vertices has it tends to one or to nought as $n$ grows. The engine of that proof was the extension property in finite form: a large random graph satisfies every request about a fixed small number of vertices, with probability tending to one.

The infinite graph explains the law. A first-order sentence is true in Rado’s graph or false in it. The extension property, written as one axiom for each size of request, is a first-order theory; every countable model of it is Rado’s graph, so by the test that turns categoricity into completeness the theory is complete, and it decides every sentence. Any sentence it proves uses only finitely many of the axioms, finitely many extension requests, and those hold in large finite random graphs with probability tending to one. So a sentence true in Rado’s graph is almost surely true in large finite random graphs, and a false one almost surely false. The limit law for finite graphs is the truth in one infinite graph.

That is also why the law’s exceptions are what they are, and why the finite random graphs of the giant component behave so differently: there the edge probability shrinks as the graph grows, the extension property fails, and the limit is a different object altogether. Properties like “the graph is connected” — whose threshold is an event in its own right at other edge probabilities — or “the number of vertices is even” are not first-order in the language of graphs, and the infinite graph says nothing about them.

Finite graphs that almost satisfy it #

No finite graph has the full extension property: a finite graph cannot answer requests of every size. But a finite graph can answer every request with $|U| + |V| \le k$, and such graphs are useful as small stand-ins for Rado’s graph.

Random graphs do it with probability tending to one once they have more than about $k^2 2^k$ vertices. Explicit ones come from number theory. The Paley graph on a prime $q \equiv 1 \pmod 4$ joins two residues when their difference is a square modulo $q$ — the same quadratic residues that built a table of signs with perpendicular rows — and for $q$ large enough compared with $4^k$ it answers every request of size $k$. The squares modulo a prime behave, for this purpose, exactly like coin tosses.

What the figures cannot certify #

Every figure is finite: the first sixteen vertices of the bit graph, requests among the first ten vertices of a three-thousand-vertex random graph, eight steps of a zigzag, ten vertices of an embedding. The theorem is about an infinite graph and an infinite matching, and the finite pieces verify that each step of the argument succeeds where it is tried. That every step succeeds for ever is the extension property, which for the bit graph is proved by the witness formula and for the coin-toss graph holds with probability one.

“With probability one” is itself a limitation the figures cannot reach. There are outcomes of the coin tosses — all heads, for instance — that give a graph which is not Rado’s; they have probability nought, and no finite sample can distinguish a probability-nought exception from a probability-one rule. The seeded random graph in the figures is one outcome, which happens to behave as almost every outcome does.

Still open: the smallest graph that answers every small request #

Call a finite graph $k$-extending if it answers every request with $|U| + |V| \le k$. Such graphs exist for every $k$, by the random construction, and the smallest one for $k = 2$ is known: nine vertices, the Paley graph on nine elements. For larger $k$ it is not. The smallest number of vertices a $k$-extending graph can have is not known even for $k = 3$, where it is pinned only between bounds found by computer search and explicit constructions, and for general $k$ the known bounds differ by a factor that grows with $k$.

It is a finite question about a property whose infinite version is the simplest thing about Rado’s graph. The random construction shows such graphs are plentiful at about $k^2 2^k$ vertices; nothing shows they cannot be much smaller; and the best explicit constructions, from quadratic residues and from designs, beat randomness only by constant factors.