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.