The random graph, 1

Now at last I get to write about one of my favourite topics in mathematics.

In 1963, in what was really just a footnote to a paper on finite random graphs, Paul Erdős and Alfred Rényi proved the following theorem:

There is a countable graph R such that a random countable graph is almost surely isomorphic to R.

Here the random countable graph is chosen by starting with a countable set of vertices, ordering the pairs of vertices in a countable sequence, and tossing a fair coin for each pair: heads, the two vertices are joined by an edge; tails, they are not joined. I discussed the probability measure associated with a countable sequence of coin tosses in the preceding post in this sequence. “Almost surely” means that the probability that the random graph is isomorphic to R is 1. R is the (countable) random graph.

Erdős and Rényi didn’t bother giving an explicit construction of the graph R: if almost all graphs are isomorphic to it, then it certainly exists. But quite by chance, a paper by another Hungarian mathematician, Richard Rado, appeared the following year giving an explicit construction. Rado’s purpose was quite different: he was interested in countable universal graphs (those containing a copy of every countable graph), and R has this property, as we will see.

To see how remarkable this is, think about the finite case for a moment. We construct a random graph on n vertices by the same method, by means of n(n–1)/2 coin tosses. Now every n-vertex graph (up to isomorphism) occurs with non-zero probability, and the probability of a graph is inversely proportional to its symmetry (the order of its automorphism group). Worse still, the asymmetric graphs predominate overwhelmingly in the enumeration of graphs; searching randomly for symmetric graphs is much worse than searching for needles in haystacks or free quarks in oyster beds.

But we will see that the (unique) countable random graph has a huge amount of symmetry.

Before I sketch the proof given by Erdős and Rényi, here is the proof using the notion of Baire category. (This shows that the isomorphism class of R is residual in the set of all countable graphs.) Note that we represent each countable graph by an infinite binary sequence, namely the sequence of coin tosses required to generate it. See the previous post in this series if this is new to you. Half of the proof is common to both methods; I give that first.

We consider countable graphs with the following property (*):

Given finite disjoint sets U and V of vertices, there is a vertex z joined to everything in U and to nothing in V.

I shall say that z is correctly joined. Now the proof has two parts:

  • Any two countable graphs satisfying (*) are isomorphic.
  • The set of countable graphs satisfying (*) is residual in the set of all graphs.

The proof of the first statement involves the method known as “back-and-forth”. As a preliminary, here is a proof that a graph satisfying (*) is universal (that is, embeds all countable graphs). Let two countable graphs A and B be given, with vertex sets {a1,a2,…} and {b1,b2,…}; suppose that B satisfies (*). We construct an embedding of A in B. Suppose that a1,…,an have been mapped into B preserving the graph structure. We have to map an+1. Let S and T be the neighbours and non-neighbours of an+1 among a1,…,an, and U and V their images under the map so far defined. Use (*) to choose a correctly joined vertex with respect to these sets. This vertex is a suitable image for an+1.

Continue this process; eventually every vertex gets mapped, and we have our embedding.

How to modify this to get an isomorphism if A also satisfies (*)? At odd-numbered steps, we proceed as described to choose an image for the first unmapped vertex in A. At even numbered steps, work in reverse, using (*) in A to choose a suitable pre-image for the first unmapped vertex in B. Now eventually any point in A falls into the domain, and every point of B into the range, of the map.

Now to the second point: property (*) is residual in the set of all graphs. Recall that a set is residual if it contains a countable intersection of open dense sets; and that, in the space of binary sequences, “open” means finitely determined, while “dense” means always reachable.

There are only countably many choices of two finite disjoint sets U and V. So it is enough to show that, for fixed U and V, the set of graphs having a correctly joined vertex is finitely determined and always reachable. These facts are practically obvious:

  • If a graph has a correctly joined vertex, then so does every graph which agrees with it at all pairs up to the point when all edges from this vertex to U and V had been decided.
  • Given any finite number of edges and non-edges, choose z lying on none of them and not in U or V; then judicious choice of edges and non-edges from z to these two sets will ensure that (*) holds.

Since residual sets are non-empty (by the Baire category theorem), there is a countable graph satisfying (*). Now the set of all graphs satisfying (*) is a single isomorphism class, and is residual. Moreover, this unique graph is universal, as we have seen.

Finally, let us consider what Erdős and Rényi actually did, which was to use measure instead of Baire category. It is slightly more complicated, since a small calculation is required.

The intersection of countably many sets of measure 1 in a space of total measure 1 itself has measure 1. So we have to show that, for fixed U and V, the event that a random graph has a correctly joined vertex is 1; in other words, the probability that no vertex is correctly joined is 0.

Suppose that U and V contain k vertices between them. For any given choice of z, the probability that z is not correctly joined is 1–1/2k. Since these events for different z are independent, the probability that none of n chosen vertices is correctly joined is (1–1/2k)n. This tends to 0 as n tends to infinity, so the event that no vertex is correctly joined does have probability 0, as required.

The machinery shows us something else about the unique countable graph R satisfying (*). A graph G is called homogeneous if every isomorphism between finite subgraphs of G can be extended to an automorphism of G. This is obviously a very strong symmetry condition, saying that we can map any vertex to any other by an automorphism, and similarly for edges, non-edges, …, indeed any configuration we choose. It was shown by Sheehan and Gardiner in the 1970s that, apart from trivial examples (disjoint unions of complete graphs and their complements), there are only two finite homogeneous graphs: the pentagon, and the 3×3 grid on the torus.

The random graph R is homogeneous. For consider the proof by back-and-forth that any two graphs satisfying (*) are isomorphic. We can regard this as a machine which computes an isomorphism. Now suppose we have an isomorphism f between finite subgraphs. Start the machine with two copies of R, but with f as initial data: it will compute an isomorphism between the two copies (that is, an automorphism of R) extending f.

Erdős and Spencer, in their book on random graphs, describe the theorem of Erdős and Rényi as “demolishing the theory of countable random graphs”. I claim that it creates a new theory, of the countable random graph. The next post will look at some constructions for it, and some of its properties.

Previous | Next

About these ads

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition. Bookmark the permalink.

7 Responses to The random graph, 1

  1. “the probability of a graph is inversely proportional to its symmetry (the order of its automorphism group)”

    proportional, not inversely proportional, right?

    (I think this is great! Thanks for the post; it’ll take me weeks of spare moments to unpack it…)

  2. Never mind — inversely proportional is right. For some reason I can’t put my finger on, I find this strangely counterintuitive.

    • Not sure whether this helps with the intuition, but the more symmetry an object has, the fewer different ways you can draw it, and so the fewer copies there are lying around for the random search to find.

  3. Pingback: Almost all « Peter Cameron's Blog

  4. Pingback: The random graph, 2 « Peter Cameron's Blog

  5. Rupert says:

    In the definition of “correctly joined”, does z have to lie outside of U and V? Or is it somehow automatic that this can always be done?

    I’m wondering why the image you find for a_{n+1} in the proof that a graph satisfying (*) is universal is guaranteed to not be among the preceding a_i’s.

    • Let me answer the second question first. If z is always outside U and V, then there are infinitely many z that work (since having found any. finite number we can add them to U and find another one), so we can always avoid any finite number of previously chosen vertices.

      As to the first question, it is easiest just to assume that z is outside both U and V. Certainly it will automatically be outside U because we are considering graphs with no loops. In fact you can prove that even if you don’t assume it’s outside V, there will be a suitable z outside V that works.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s