History of the Random Graph

That wonderful object, the countable random graph, was first considered by Erdős and Rényi in their paper on “Asymmetric graphs” in 1963. After proving that a large random finite graph (edges chosen independently with probability 1/2) has (with high probability) trivial automorphism group, and indeed cannot be transformed into a graph which has some symmetry by changing only n(1−ε)/2 edges for any positive ε, they turn to the countably infinite case, and show that an infinite random graph has infinitely many automorphisms with probability 1. They show, moreover, that this statement remains true if the edges are chosen independently with any probabilities, as long as these probabilities are bounded away from zero and one.

As Greg Cherlin pointed out to me in Durham, Erdős and Rényi did not prove in this paper that there is a unique countable random graph.

Lemma 3 of their paper shows that a countable random graph has the “Alice’s Restaurant” property – you can get anything you want. More precisely, given any finite set A of vertices, and any subset B of A, there is (w.h.p.) a vertex z whose neighbours within A are precisely the vertices of B. Using this property, they construct directly an automorphism which interchanges the vertices 1 and 2. Since there is nothing special about vertex 2, there is an automorphism interchanging any pair of vertices; so the result holds.

The following year, Richard Rado published an explicit construction of a countable graph and showed that his graph was universal for finite and countable graphs, in the sense that any such graph can be embedded as an induced subgraph. His proof implicitly uses the Alice’s Restaurant property, which holds in the graph he constructs, but he does not state the property explicitly. There is nothing in the paper suggesting any uniqueness of the graph.

The uniqueness follows from the Alice’s Restaurant property using the method of “back-and-forth”, which seems to have been invented by E. V. Huntington earlier than 1904 (it appears in his book on the continuum in 1907). The original application of back-and-forth was to prove the uniqueness of the rational numbers as countable dense ordered set without endpoints (Cantor’s theorem); however, as Jack Plotkin showed, Cantor did not use back-and-forth in his proof.

In brief: back-and-forth constructs an isomorphism between two countable structures X and Y in stages. We start with explicit enumerations of X and Y. At any given stage, we have a bijection between finite subsets of X and Y. At even-numbered stages, we select the first unused point in the enumeration of X, and find an image of it in Y; at odd-numbered stages, we select the first unused point in the enumeration of Y, and find a pre-image in X. After countably many stages, we have defined an isomorphism betweem X and Y.

Neither Erdős and Rényi nor Rado quite rediscovered back-and-forth. It is clear that, if we go “forth” (from X to Y) only, we will obtain a map defined on every point of X but perhaps missing some points of Y, in other words, an embedding of X in Y; in doing this, we use the Alice’s Restaurant property in Y but not in X. This is precisely what Rado did to show that any countable graph could be embedded in the graph he constructed.

Back-and-forth will also construct an isomorphism from X to Y starting from any “finite isomorphism”, and hence an automorphism (if we choose X = Y); thus it proves the homogeneity of the random graph. Erdős and Rényi could get away with less because they were constructing an involution, so they could produce the 2-cycles of their map one at a time using the Alice’s Restaurant property.

As a digression, Cantor succeeded because the ordered set of rationals is one of relatively few structures where the isomorphism can be constructed by going forth only. This strategy would not work with the random graph!

The book Probabilistic Methods in Combinatorics was published by Erdős and Spencer in 1974. In this book they prove the uniqueness of the countable random graph, remarking that this “demolishes the theory of countable random graphs” (though I would contend that instead it “creates the theory of the countable random graph”). I cannot speculate at what point it was realised that this remarkable fact was true. It follows, of course, that Rado’s graph is the countable random graph. Indeed, many people call it the Rado graph.

I cannot remember exactly when I learned about this graph. It was probably in the early 1980s, though I did not refer to it in print until 1987, in a paper with Ken Johnson. (Graham Higman had given a sufficient condition for a countable group to fail to be a B-group, in other words, to be contained as a regular subgroup in a primitive permutation group which was not doubly transitive. Ken and I showed that rather than needing a different primitive group for each group satisfying Higman’s condition, a single one would suffice for all of them, namely, the automorphism group of the random graph.)

I had been thinking about infinite permutation groups since the mid-1970s, and read the paper of Lachlan and Woodrow when it came out in 1980. But who first told me about the random graph, I am not sure. I may have picked it up from a throwaway remark by Ken Regan, who was a graduate student at Merton College, Oxford.

Not surprisingly, there is a back story. The nice properties of the random graph (that uniqueness and homogeneity follow from the Alice’s Restaurant property) had been worked out in much greater generality by Fraïssé in the late 1940s and early 1950s, and the Hungarians were presumably unaware of this. Fraïssé himself was probably unaware of the posthumously-published paper by Urysohn, who used the same technique in 1924 or earlier to construct a universal homogeneous rational metric space, whose completion is the celebrated Urysohn space.

Advertisements

About Peter Cameron

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

7 Responses to History of the Random Graph

  1. Gordon Royle says:

    Whenever I hear about the random graph, I cannot get my mind around the fact that if you construct a countably infinite Erdos-Renyi random graph with edge probability p, then you get the same graph regardless of the value of p (unless it is 0 or 1).

    I think my Intro to Pure Maths students have a similar reaction when I try to convince them that there are the same number of even integers as all integers, but for some reason this seems natural to me, while the graph case does not.

    • There is an interesting footnote to this. The Erdos-Renyi paper actually shows that p can vary as long as it is bounded away from 0 and 1. But more is true: you can allow p to approach zero, as long as it does so sufficiently slowly (an interesting exercise in elementary analysis). So the coin can slowly become more biased as the experiment goes on. But if the probability goes to zero too fast, then other interesting phenomena occur!

  2. Shahrooz says:

    Dear professor Cameron, this post is very interesting for me. Would you please give me some good references for study in this field? Recently, I asked a question in the M.O page via this link:
    http://mathoverflow.net/questions/211458/cayley-graphs-with-special-subgraphs-and-some-related-problems

    I think by this area that you introduced, we can give some answers to the questions in special cases.

    Thanks a lot dear Cameron.
    Shahrooz.Janbaz

    • Dear Shahrooz, I don’t know whether the random graph will be of much use for your questions. It has infinite degree, and its automorphism group is simple.

  3. Shahrooz says:

    You are right. I surprised by the beautiful properties of such graphs and I forgot the finite valency.
    Thank you very much dear Cameron.

    • In fact, the Alice’s Restaurant property shows that the random graph and its complement both have diameter 2. Now some of the most important tools of combinatorial group theory involve the large-scale structure (ends, quasi-isometries, etc.), and from this point of view the random graph, like any countably categorical structure, is quasi-isometric to a point (or “trivial”), as Christian Rosendal pointed out at the recent Durham symposium. This is perhaps why the results on the random graph as a Cayley graph have not aroused very much interest!

  4. abonato99 says:

    Wonderful post as always, Peter. Maybe in your semi-retirement you will get around to writing a book on the topic!

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