In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed (with probability one) by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of . The Rado graph can also be constructed non-randomly, as a graph whose vertices are hereditarily finite sets (finite sets whose elements are hereditarily finite) with edges representing set membership, as a graph whose vertices are natural numbers and whose edges are given by the BIT predicate that uses the smaller of two numbers as an index into the binary representation of the other number, or as a graph of certain prime numbers that are connected by edges when one number is a square modulo another.
Every finite or countably infinite graph is an induced subgraph of the Rado graph, and can be found as an induced subgraph by a greedy algorithm that builds up the subgraph one vertex at a time. The Rado graph is uniquely defined, among countable graphs, by an extension property that guarantees the correctness of this algorithm: no matter which vertices have already been chosen to form part of the induced subgraph, and no matter what pattern of adjacencies is needed to extend the subgraph by one more vertex, there will always exist another vertex with that pattern of adjacencies that the greedy algorithm can choose.
The Rado graph is highly symmetric: any isomorphism of its finite induced subgraphs can be extended to a symmetry of the whole graph. The first-order logic sentences that are true of the Rado graph are also true of almost all random finite graphs, and the sentences that are false for the Rado graph are also false for almost all finite graphs. In model theory, the Rado graph is an example of the unique countable model of an ω-categorical theory.
History The Rado graph was first constructed by in two ways, with vertices either the hereditarily finite sets or the natural numbers. (Strictly speaking Ackermann described a directed graph, and the Rado graph is the corresponding undirected graph given by forgetting the directions on the edges.) constructed the Rado graph as the random graph on a countable number of points. They proved that it has infinitely many automorphisms, and their argument also shows that it is unique though they did not mention this explicitly. rediscovered the Rado graph as a universal graph, and gave an explicit construction of it with the natural numbers as the vertex set. Rado's construction is essentially equivalent to one of Ackermann's constructions.
Constructions Binary numbers and constructed the Rado graph using the BIT predicate as follows. They identified the vertices of the graph with the natural numbers 0, 1, 2, ... An edge connects vertices and in the graph (where ) whenever the th bit of the binary representation of is nonzero. Thus, for instance, the neighbors of vertex 0 consist of all odd-numbered vertices, because the numbers whose 0th bit is nonzero are exactly the odd numbers. Vertex 1 has one smaller neighbor, vertex 0, as 1 is odd and vertex 0 is connected to all odd vertices. The larger neighbors of vertex 1 are all vertices with numbers congruent to 2 or 3 modulo 4, because those are exactly the numbers with a nonzero bit at index 1.; .
Random graph The Rado graph arises almost surely in the Erdős–Rényi model of a random graph on countably many vertices. Specifically, one may form an infinite graph by choosing, independently and with probability 1/2 for each pair of vertices, whether to connect the two vertices by an edge. With probability 1 the resulting graph is isomorphic to the Rado graph. This construction also works if any fixed probability not equal to 0 or 1 is used in place of 1/2.See , Fact 1 and its proof.
This result, shown by , justifies the definite article in the common alternative name "the random graph" for the Rado graph. Repeatedly drawing a finite graph from the Erdős–Rényi model will in general lead to different graphs; however, when applied to a countably infinite graph, the model almost always produces the same infinite graph.
For any graph generated randomly in this way, the complement graph can be obtained at the same time by reversing all the choices: including an edge when the first graph did not include the same edge, and vice versa. This construction of the complement graph is an instance of the same process of choosing randomly and independently whether to include each edge, so it also (with probability 1) generates the Rado graph. Therefore, the Rado graph is a self-complementary graph., Proposition 5.
Other constructions In one of Ackermann's original 1937 constructions, the vertices of the Rado graph are indexed by the hereditarily finite sets, which are defined recursively as the finite sets whose elements are hereditarily finite sets, allowing only finitely many levels of recursion. There is an edge between two vertices exactly when one of the corresponding finite sets is a member of the other. This construction is equivalent to the BIT predicate construction, under the Ackermann coding of hereditarily finite sets as binary numbers. A similar construction can be based on Skolem's paradox, the fact that there exists a countable model for the first-order theory of sets. One can construct the Rado graph from such a model by creating a vertex for each set, with an edge connecting each pair of sets where one set in the pair is a member of the other., Theorem 2.
The Rado graph may also be formed by a construction resembling that for Paley graphs, taking as the vertices of a graph all the prime numbers that are congruent to 1 modulo 4, and connecting two vertices by an edge whenever one of the two numbers is a quadratic residue (that is, congruent to a square) modulo the other. By quadratic reciprocity and the restriction of the vertices to primes congruent to 1 mod 4, this is a symmetric relation, so it defines an undirected graph, which turns out to be isomorphic to the Rado graph.
Another construction of the Rado graph shows that it is an infinite circulant graph, with the integers as its vertices and with an edge between each two integers whose distance (the absolute value of their difference) belongs to a particular set . To construct the Rado graph in this way, may be chosen randomly, or by choosing the indicator function of to be the concatenation of all finite binary sequences., Section 1.2.
The Rado graph can also be constructed as the block intersection graph of an infinite block design in which the number of points and the size of each block are countably infinite. It can also be constructed as the Fraïssé limit of the class of finite graphs.
Properties Extension
The Rado graph satisfies the following extension property: for every two disjoint finite sets of vertices and , there exists a vertex outside both sets that is connected to all vertices in , but has no neighbors in . For instance, with the binary-number definition of the Rado graph, let
Then the nonzero bits in the binary representation of cause it to be adjacent to everything in . However, has no nonzero bits in its binary representation corresponding to vertices in , and is so large that the th bit of every element of is zero. Thus, is not adjacent to any vertex in .Essentially the same construction, described in set-theoretic terms rather than using binary numbers, is given as Theorem 2 of .
With the random-graph definition of the Rado graph, each vertex outside the union of and has probability of fulfilling the extension property, independently of the other vertices. Because there are infinitely many vertices to choose from, each with the same finite probability of success, the probability is one that there exists a vertex that fulfils the extension property. With the Paley graph definition, for any sets and , by the Chinese remainder theorem, the numbers that are quadratic residues modulo every prime in and nonresidues modulo every prime in form a periodic sequence, so by Dirichlet's theorem on primes in arithmetic progressions this number-theoretic graph has the extension property.
Induced subgraphs The extension property can be used to build up isomorphic copies of any finite or countably infinite graph within the Rado graph, as induced subgraphs. To do so, order the vertices of , and add vertices in the same order to a partial copy of within the Rado graph. At each step, the next vertex in will be adjacent to some set of vertices in that are earlier in the ordering of the vertices, and non-adjacent to the remaining set of earlier vertices in . By the extension property, the Rado graph will also have a vertex that is adjacent to all the vertices in the partial copy that correspond to members of , and non-adjacent to all the vertices in the partial copy that correspond to members of . Adding to the partial copy of produces a larger partial copy, with one more vertex., Proposition 6.
This method forms the basis for a proof by induction, with the 0-vertex subgraph as its base case, that every finite or countably infinite graph is an induced subgraph of the Rado graph.
Uniqueness The Rado graph is, up to graph isomorphism, the only countable graph with the extension property. For example, let and be two countable graphs with the extension property, let and be isomorphic finite induced subgraphs of and respectively, and let and be the first vertices in an enumeration of the vertices of and respectively that do not belong to and . Then, by applying the extension property twice, one can find isomorphic induced subgraphs and that include and together with all the vertices of the previous subgraphs. By repeating this process, one may build up a sequence of isomorphisms between induced subgraphs that eventually includes every vertex in and . Thus, by the back-and-forth method, and must be isomorphic.. Because the graphs constructed by the random graph construction, binary number construction, and Paley graph construction are all countable graphs with the extension property, this argument shows that they are all isomorphic to each other., Fact 2.
Symmetry group Applying the back-and-forth construction to any two isomorphic finite subgraphs of the Rado graph extends their isomorphism to an automorphism of the entire Rado graph. The fact that every isomorphism of finite subgraphs extends to an automorphism of the whole graph is expressed by saying that the Rado graph is ultrahomogeneous. In particular, there is an automorphism taking any ordered pair of adjacent vertices to any other such ordered pair, so the Rado graph is a symmetric graph.
The automorphism group of the Rado graph is a simple group, whose number of elements is the cardinality of the continuum. Every subgroup of this group whose index is less than the cardinality of the continuum contains the pointwise stabilizer of a finite set of vertices, and furthermore is contained within the setwise stabilizer of the same set., Section 1.8: The automorphism group. The statement about pointwise stabilizers is called the small index property, and proving it required showing that for every finite graph , there is a finite graph containing as an induced subgraph such that every isomorphism between induced subgraphs of extends to an automorphism of . This is called the extension property for partial automorphisms and has since been generalized to further structures in order to show the small index property and other properties., Sections 5.2 and 5.3.