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 Wilhelm Ackermann (1937). 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 Ackermann (1937) 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.) Erdős & Rényi (1963) 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. Richard Rado (1964) 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 Ackermann (1937) and Rado (1964) 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 x {\displaystyle x} and y {\displaystyle y} in the graph (where x < y {\displaystyle x<y} ) whenever the x {\displaystyle x} th bit of the binary representation of y {\displaystyle y} 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 p {\displaystyle p} not equal to 0 or 1 is used in place of 1/2. This result, shown by Paul Erdős and Alfréd Rényi (1963), 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.
… excerpt ends here. Continue reading the full article.
