Rado graph
Encyclopedia
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
field of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the Rado graph, also known as the random graph or the Erdős–Renyi graph, is the unique (up to
Up to
In mathematics, the phrase "up to x" means "disregarding a possible difference in x".For instance, when calculating an indefinite integral, one could say that the solution is f "up to addition by a constant," meaning it differs from f, if at all, only by some constant.It indicates that...
isomorphism
Graph isomorphism
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f \colon V \to V \,\!such that any two vertices u and v of G are adjacent in G if and only if ƒ and ƒ are adjacent in H...
) countable graph R such that for any finite graph G and any vertex v of G, any embedding of G − v as an induced subgraph of R can be extended to an embedding of G into R. As a result, the Rado graph contains all finite and countably infinite graphs as induced subgraphs.
History
The Rado graph was introduced by , although the symmetry properties of the same graph, constructed in a different way, had already been studied by .Construction via binary numbers
constructs the Rado graph as follows. He identifies the vertices of the graph with the natural numberNatural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s 0, 1, 2, ...
An edge xy exists in the graph whenever either the xth bit of the binary
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
representation of y is nonzero (in this case
), or, symmetrically, if the yth bit of the binary representation of x is nonzero (in this case 
). Thus, for instance, the neighbors of vertex 0 consist of all odd-numbered vertices, while the neighbors of vertex 1 consist of vertex 0 (the only vertex whose bit in the binary representation of 1 is nonzero) and all vertices with numbers congruent to 2 or 3 modulo 4.Finding isomorphic subgraphs
The Rado graph satisfies the following extension property: for any finite disjoint sets of vertices U and V, there exists a vertex x connected to everything in U, and to nothing in V.For instance, let
Then the nonzero bits in the binary representation of x cause it to be adjacent to everything in U. However, x has no nonzero bits in its binary representation corresponding to vertices in V, and x is so large that the xth bit of every element of V is zero. Thus, x is not adjacent to any vertex in V.
This idea of finding vertices adjacent to everything in one subset and nonadjacent to everything in a second subset can be used to build up isomorphic copies of any finite or countably infinite graph G, one vertex at a time. For, let Gi denote the subgraph of G induced by its first i vertices, and suppose that Gi has already been identified as an induced subgraph of a subset S of the vertices of the Rado graph. Let v be the next vertex of G, let U be the neighbors of v in Gi, and let V be the non-neighbors of v in Gi. If x is a vertex of the Rado graph that is adjacent to every vertex in U and nonadjacent to every vertex in V, then S ∪ {x} induces a subgraph isomorphic to Gi + 1.
By induction, starting from the 0-vertex subgraph, every finite or countably infinite
Countable set
In mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A set that is not countable is called uncountable. The term was originated by Georg Cantor...
graph is an induced subgraph of the Rado graph.
Uniqueness
The Rado graph is, up to graph isomorphismGraph isomorphism
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f \colon V \to V \,\!such that any two vertices u and v of G are adjacent in G if and only if ƒ and ƒ are adjacent in H...
, the only countable graph with the extension property. For, let G and H be two graphs with the extension property, let Gi and Hi be isomorphic induced subgraphs of G and H respectively, and let gi and hi be the first vertices in an enumeration of the vertices of G and H respectively that do not belong to Gi and Hi. Then, by applying the extension property twice, one can find isomorphic induced subgraphs Gi + 1 and Hi + 1 that include gi and hi 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 G and H. Thus, by the back-and-forth method, G and H must be isomorphic.
By applying the same construction to two isomorphic subgraphs of the Rado graph, it can be shown that the Rado graph is ultrahomogeneous: any isomorphism between any two induced subgraphs of the Rado graph extends to an automorphism
Graph automorphism
In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity....
of the entire Rado graph. 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
Symmetric graph
In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphismsuch that...
.
Robustness against finite changes
If a graph G is formed from the Rado graph by deleting any finite number of edges or vertices, or adding a finite number of edges, the change does not affect the extension property of the graph: for any pair of sets U and V it is still possible to find a vertex in the modified graph that is adjacent to everything in U and nonadjacent to everything in V, by adding the modified parts of G to V and applying the extension property in the unmodified Rado graph. Therefore, any finite modification of this type results in a graph that is isomorphic to the Rado graph.Partition property
For any partition of the vertices of the Rado graph into two sets A and B, or more generally for any partition into finitely many subsets, at least one of the subgraphs induced by one of the partition sets is isomorphic to the whole Rado graph. gives the following short proof: if none of the parts induces a subgraph isomorphic to the Rado graph, they all fail to have the extension property, and one can find pairs of sets Ui and Vi that cannot be extended within each subgraph. But then, the union of the sets Ui and the union of the sets Vi would form a set that could not be extended in the whole graph, contradicting the Rado graph's extension property. This property of being isomorphic to one of the induced subgraphs of any partition is held by only three countably infinite undirected graphs: the Rado graph, the complete graphComplete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
, and the empty graph. and investigate infinite directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
s with the same partition property; all are formed by choosing orientations for the edges of the complete graph or the Rado graph.
A related result concerns edge partitions instead of vertex partitions: for every partition of the edges of the Rado graph into finitely many sets, there is a subgraph isomorphic to the whole Rado graph that uses at most two of the colors. However, there may not necessarily exist an isomorphic subgraph that uses only one color of edges.
Alternative constructions
One may form an infinite graph in the Erdős–Rényi modelErdos–Rényi model
In graph theory, the Erdős–Rényi model, named for Paul Erdős and Alfréd Rényi, is either of two models for generating random graphs, including one that sets an edge between each pair of nodes with equal probability, independently of the other edges...
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 has the extension property, and is therefore isomorphic to the Rado graph. This construction also works if any fixed probability p not equal to 0 or 1 is used in place of 1/2. This result, shown by Paul Erdős
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
and Alfréd Rényi
Alfréd Rényi
Alfréd Rényi was a Hungarian mathematician who made contributions in combinatorics, graph theory, number theory but mostly in probability theory.-Life:...
in 1963, justifies the definite article
Definite Article
Definite Article is the title of British comedian Eddie Izzard's 1996 performance released on VHS. It was recorded on different nights at the Shaftesbury Theatre...
in the common alternative name “the random graph” for the Rado graph: for finite graphs, repeatedly drawing a graph from the Erdős–Rényi model will often lead to different graphs, but for countably infinite graphs the model almost always
Almost Always
"Almost Always" is a popular song. It was recorded by Joni James in 1953. The recording was released by MGM as catalog number 11470. The song was only on the Billboard magazine charts for one week, reaching #18 on May 9, 1953. The flip side was "Is It Any Wonder?"...
produces the same graph. Since one obtains the same random process by inverting all choices, the Rado graph is self-complementary
Self-complementary graph
A self-complementary graph is a graph which is isomorphic to its complement. The simplest non-trivial self-complementary graphs are the 4-vertex path graph and the 5-vertex cycle graph....
.
As describes, the Rado graph may also be formed by a construction resembling that for Paley graph
Paley graph
In mathematics, and specifically graph theory, Paley graphs, named after Raymond Paley, are dense undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ in a quadratic residue. The Paley graphs form an infinite family of conference...
s. Take as the vertices of a graph all the prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
s that are congruent to 1 modulo 4, and connect two vertices by an edge whenever one of the two numbers is a quadratic residue modulo the other (by quadratic reciprocity
Quadratic reciprocity
In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic which gives conditions for the solvability of quadratic equations modulo prime numbers...
and the restriction of the vertices to primes congruent to 1 mod 4, this is a symmetric relation
Symmetric relation
In mathematics, a binary relation R over a set X is symmetric if it holds for all a and b in X that if a is related to b then b is related to a.In mathematical notation, this is:...
, so it defines an undirected graph). Then, for any sets U and V, by the Chinese remainder theorem
Chinese remainder theorem
The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...
, the numbers that are quadratic resides modulo every prime in U and nonresidues modulo every prime in V form a periodic sequence, so by Dirichlet's theorem
Dirichlet's theorem on arithmetic progressions
In number theory, Dirichlet's theorem, also called the Dirichlet prime number theorem, states that for any two positive coprime integers a and d, there are infinitely many primes of the form a + nd, where n ≥ 0. In other words, there are infinitely many primes which are...
on primes in arithmetic progressions this number-theoretic graph has the extension property.
Related concepts
Although the Rado graph is universal for induced subgraphs, it is not universal for isometric embeddingsIsometry
In mathematics, an isometry is a distance-preserving map between metric spaces. Geometric figures which can be related by an isometry are called congruent.Isometries are often used in constructions where one space is embedded in another space...
of graphs: it has diameter two, and so any graph with larger diameter does not embed isometrically into it. has investigated universal graphs for isometric embedding; he finds a family of universal graphs, one for each possible finite graph diameter. The graph in his family with diameter two is the Rado graph.
The universality property of the Rado graph can be extended to edge-colored graphs; that is, graphs in which the edges have been assigned to different color classes, but without the usual edge coloring
Edge coloring
In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several...
requirement that each color class form a matching. For any finite or countably infinite number of colors χ, there exists a unique countably-infinite χ-edge-colored graph Gχ such that every partial isomorphism of a χ-edge-colored finite graph can be extended to a full isomorphism. With this notation, the Rado graph is just G1. investigates the automorphism groups of this more general family of graphs.
From the model theoretic
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
point of view, the Rado graph is an example of a saturated model
Saturated model
In mathematical logic, and particularly in its subfield model theory, a saturated model M is one which realizes as many complete types as may be "reasonably expected" given its size...
.
investigates universal graphs for transfinite numbers of vertices.