An ergodic take on the random graph

I wanted to learn about the random graph, which is normally an object studied in model theory, but I know very little model theory. Since I’m taking a course on ergodic theory this term, I figured now would be the time to figure out the basic properties of the random graph from an analyst’s perspective. (I’m sure none of the ideas here are original, though I haven’t seem them written down in this presentation before.)

We will be considering undirected graphs without loops, at most one edge per pair of vertices, and one vertex for each natural number. We want to think of such graphs as being encoded by real numbers, but since multiple decimal expansions encode the same real number, this will prove problematic. So instead, we will encode them using infinite binary strings.

Let C be the usual Cantor set of infinite binary strings. If 2 denotes the 2-element set then C is a product of countably many copies of 2. We define a probability measure mu on C. The topology of C is generated by cylinders C_y, where y ranges over finite binary strings. If y is length l, then $\mu(C_y) = 2^{-\ell}$ . (Actually, we could replace mu by any Bernoulli measure, but this is slightly cleaner.) This measure mu extends to the Borel sets of C.

Fix your favorite bijection F from N to the set X of pairs (n, m) of natural numbers such that $n < m$ . F lifts to a bijection between the power sets of N and X. Now the power set of N is C, while the power set of X, say G, is nothing more than the set of possible adjacency relations that could give N the structure of a graph. Pushing mu forward along F, we obtain a probability space G = (G, mu) whose outcomes are graphs on N! Moreover, to specify such a graph, we just need to choose a point in the Cantor set.

But wait, this probability space is highly uniform. That is, if we pick two elements of G at random, then almost surely they will be isomorphic. To see this, we show that almost surely, every finite graph embeds into a randomly chosen element of G.

To see that the graph G on N such that every countable graph embeds uniquely into G is unique up to isomorphism, let G’ be another such graph. Since both graphs are defined on N, there is a natural ordering on their vertices. We construct an isomorphism between G and G’ in countably many stages. Assume inductively that at stage 2n – 1, we have constructed isomorphic finite subgraphs H_{2n – 1} and H_{2n – 1}’ of G and G’ respectively, with 2n – 1 elements. At stage 2n, let g be the least element of G that does not appear in H_{2n – 1} and let H_{2n} be the union of g with H_{2n – 1}. Then H_{2n} is a finite graph, so is isomorphic to a subgraph H_{2n}’ of G’, which can be chosen to contain H_{2n – 1}’. Then at stage 2n + 1, let g’ be the least element of G’ which does not appear in H_{2n}’, adjoin it to get a graph H_{2n + 1}’, and find an isomorphism to a subgraph H_{2n + 1} of G. The H_n and H_n’ eventually exhaust G and G’, respectively, so give rise to an isomorphism between G and G’.

Now, to see that every finite graph embeds almost surely. It suffices to show that every finite binary string appears in a randomly chosen infinite binary string almost surely. To do this, say that an infinite binary string x is normal if 0 appears in x with frequency 1/2. If x is normal, then any finite word of length l appears in x with frequency $2^{-\ell}$ , and in particular appears at least once.

So it suffices to show that almost every infinite binary string is normal. This follows by the ergodic theorem. Let T be the shift map on C (so $T(x_1x_2x_3\dots) = x_2x_3x_4\dots$ .) Clearly T is measure-preserving. Now define a Borel function $f: C \to 2$ by projection onto the first factor: $f(x_1x_2x_3\dots) = x_1$ . Then $f(T^n(x_1x_2x_3\dots)) = x_{n+1}$ and obviously the expected value of f is 1/2. So by the ergodic theorem, the frequency of 0 in x is the expected value of f, so we are done.