View source for Rado graph

{{short description|Infinite graph containing all countable graphs}}
[[File:Rado graph.svg|thumb|upright=1.35|The Rado graph, as numbered by {{harvtxt|Ackermann|1937}} and {{harvtxt|Rado|1964}}.]]
In the [[Mathematics|mathematical]] field of [[Graph theory|graph theory]], the '''Rado graph''', '''Erdős–Rényi graph''', or '''random graph''' is a [[Countable set|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 [[Biography:Richard Rado|Richard Rado]], [[Biography:Paul Erdős|Paul Erdős]], and [[Biography:Alfréd Rényi|Alfréd Rényi]], mathematicians who studied it in the early 1960s; it appears even earlier in the work of {{harvs|first=Wilhelm|last=Ackermann|year=1937|txt}}. The Rado graph can also be constructed non-randomly, by symmetrizing the membership relation of the [[Hereditarily finite set|hereditarily finite set]]s, by applying the [[BIT predicate]] to the binary representations of the [[Natural number|natural number]]s, or as an infinite [[Paley graph]] that has edges connecting pairs of [[Prime number|prime number]]s congruent to 1 mod 4 that are [[Quadratic residue|quadratic residue]]s modulo each other.

Every finite or countably infinite graph is an [[Induced subgraph|induced subgraph]] of the Rado graph, and can be found as an induced subgraph by a [[Greedy algorithm|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|first-order logic]] sentences that are true of the Rado graph are also true of [[Almost all|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|model theory]], the Rado graph is an example of the unique countable model of an [[Omega-categorical theory|ω-categorical theory]].

==History==
The Rado graph was first constructed by {{harvtxt|Ackermann|1937}} in two ways, with vertices either the [[Hereditarily finite set|hereditarily finite set]]s or the natural numbers. (Strictly speaking Ackermann described a [[Directed graph|directed graph]], and the Rado graph is the corresponding undirected graph given by forgetting the directions on the edges.) {{harvtxt|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. {{harvs|first=Richard|last=Rado|txt|year=1964}} rediscovered the Rado graph as a [[Universal graph|universal graph]], and gave an explicit construction of it with vertex set the natural numbers. Rado's construction is essentially equivalent to one of Ackermann's constructions.

==Constructions==
===Binary numbers===
{{harvtxt|Ackermann|1937}} and {{harvtxt|Rado|1964}} constructed the Rado graph using the [[BIT predicate]] as follows. They identified the vertices of the graph with the [[Natural number|natural number]]s 0, 1, 2, ...
An edge connects vertices <math>x</math> and <math>y</math> in the graph (where <math>x < y</math>) whenever the <math>x</math>th bit of the binary representation of <math>y</math> 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.<ref>{{harvtxt|Ackermann|1937}}; {{harvtxt|Rado|1964}}.</ref>

===Random graph===
The Rado graph arises [[Almost surely|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 <math>p</math> not equal to 0 or 1 is used in place of 1/2.<ref name="binary-extension">See {{harvtxt|Cameron|1997}}, Fact 1 and its proof.</ref>

This result, shown by {{harvs|first1=Paul|last1=Erdős|last2=Rényi|first2=Alfréd|year=1963|txt}}, 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.{{sfnp|Erdős|Rényi|1963}}

For any graph generated randomly in this way, the [[Complement graph|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|self-complementary graph]].<ref>{{harvtxt|Cameron|1997}}, Proposition 5.</ref>

===Other constructions===
In one of Ackermann's original 1937 constructions, the vertices of the Rado graph are indexed by the hereditarily finite sets, and there is an edge between two vertices exactly when one of the corresponding finite sets is a member of the other. 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.<ref>{{harvtxt|Cameron|1997}}, Theorem 2.</ref>

The Rado graph may also be formed by a construction resembling that for [[Paley graph]]s, taking as the vertices of a graph all the [[Prime number|prime number]]s that are congruent to 1 modulo 4, and connecting two vertices by an edge whenever one of the two numbers is a [[Quadratic residue|quadratic residue]] modulo the other. By [[Quadratic reciprocity|quadratic reciprocity]] and the restriction of the vertices to primes congruent to 1 mod 4, this is a [[Symmetric relation|symmetric relation]], so it defines an undirected graph, which turns out to be isomorphic to the Rado graph.<ref name=paley/>

Another construction of the Rado graph shows that it is an infinite [[Circulant graph|circulant graph]], with the integers as its vertices and with an edge between each two integers whose distance (the [[Absolute value|absolute value]] of their difference) belongs to a particular set <math>S</math>. To construct the Rado graph in this way, <math>S</math> may be chosen randomly, or by choosing the [[Indicator function|indicator function]] of <math>S</math> to be the concatenation of all finite binary sequences.<ref>{{harvtxt|Cameron|1997}}, Section 1.2.</ref>

The Rado graph can also be constructed as the block [[Intersection graph|intersection graph]] of an infinite [[Block design|block design]] in which the number of points and the size of each block are countably infinite.<ref>{{harvtxt|Horsley|Pike|Sanaei|2011}}</ref> It can also be constructed as the [[Fraïssé limit]] of the class of finite graphs.{{sfnp|Hodges|1997|p=350}}

==Properties==
===Extension===
[[File:Rado extension.svg|thumb|upright=1.35|The extension property of the Rado graph: for every two disjoint finite sets of vertices <math>U</math> and <math>V</math>, there exists another vertex <math>x</math> connected to everything in <math>U</math>, and to nothing in <math>V</math>]]
The Rado graph satisfies the following extension property: for every two disjoint finite sets of vertices <math>U</math> and <math>V</math>, there exists a vertex <math>x</math> outside both sets that is connected to all vertices in <math>U</math>, but has no neighbors in <math>V</math>.<ref name="binary-extension"/>
For instance, with the binary-number definition of the Rado graph, let
<math display=block>x=2^{1+\max(U\cup V)} + \sum_{u\in U} 2^u.</math>
Then the nonzero bits in the binary representation of <math>x</math> cause it to be adjacent to everything in <math>U</math>. However, <math>x</math> has no nonzero bits in its binary representation corresponding to vertices in <math>V</math>, and <math>x</math> is so large that the <math>x</math>th bit of every element of <math>V</math> is zero. Thus, <math>x</math> is not adjacent to any vertex in <math>V</math>.<ref>Essentially the same construction, described in set-theoretic terms rather than using binary numbers, is given as Theorem 2 of {{harvtxt|Cameron|1997}}.</ref>

With the random-graph definition of the Rado graph, each vertex outside the union of <math>U</math> and <math>V</math> has probability <math>1/2^{|U|+|V|}</math> 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.<ref name="binary-extension"/> With the Paley graph definition, for any sets <math>U</math> and <math>V</math>, by the [[Chinese remainder theorem]], the numbers that are quadratic residues modulo every prime in <math>U</math> and nonresidues modulo every prime in <math>V</math> form a periodic sequence, so by [[Dirichlet's theorem on arithmetic progressions|Dirichlet's theorem]] on primes in arithmetic progressions this number-theoretic graph has the extension property.<ref name=paley>{{harvs|last=Cameron|year=1997|year2=2001|txt}}</ref>

===Induced subgraphs===
The extension property can be used to build up isomorphic copies of any finite or countably infinite graph <math>G</math> within the Rado graph, as [[Induced subgraph|induced subgraph]]s.
To do so, order the vertices of <math>G</math>, and add vertices in the same order to a partial copy of <math>G</math> within the Rado graph.
At each step, the next vertex in <math>G</math> will be adjacent to some set <math>U</math> of vertices in <math>G</math> that are earlier in the ordering of the vertices,
and non-adjacent to the remaining set <math>V</math> of earlier vertices in <math>G</math>.
By the extension property, the Rado graph will also have a vertex <math>x</math> that is adjacent to all the vertices in the partial copy that correspond to members of <math>U</math>,
and non-adjacent to all the vertices in the partial copy that correspond to members of <math>V</math>. Adding <math>x</math> to the partial copy of <math>G</math> produces a larger partial copy, with one more vertex.<ref name=induced>{{harvtxt|Cameron|1997}}, Proposition 6.</ref>

This method forms the basis for a proof by induction, with the 0-vertex subgraph as its base case, that every finite or [[Countable set|countably infinite]] graph is an induced subgraph of the Rado graph.<ref name=induced/>

===Uniqueness===
The Rado graph is, up to [[Graph isomorphism|graph isomorphism]], the only countable graph with the extension property. For example, let <math>G</math> and <math>H</math> be two countable graphs with the extension property, let <math>G_i</math> and <math>H_i</math> be isomorphic finite induced subgraphs of <math>G</math> and <math>H</math> respectively, and let <math>g_i</math> and <math>h_i</math> be the first vertices in an enumeration of the vertices of <math>G</math> and <math>H</math> respectively that do not belong to <math>G_i</math> and <math>H_i</math>. Then, by applying the extension property twice, one can find isomorphic induced subgraphs <math>G_{i+1}</math> and <math>H_{i+1}</math> that include <math>g_i</math> and <math>h_i</math> 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 <math>G</math> and <math>H</math>. Thus, by the [[Back-and-forth method|back-and-forth method]], <math>G</math> and <math>H</math> must be isomorphic.<ref name="cam">{{harvtxt|Cameron|2001}}.</ref>
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.<ref>{{harvtxt|Cameron|1997}}, Fact 2.</ref>

===Symmetry group===
Applying the back-and-forth construction to any two isomorphic finite subgraphs of the Rado graph extends their isomorphism to an [[Graph automorphism|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 ''[[Homogeneous graph|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|symmetric graph]].<ref name="cam"/>

The automorphism group of the Rado graph is a [[Simple group|simple group]], whose number of elements is the [[Cardinality of the continuum|cardinality of the continuum]]. Every [[Subgroup|subgroup]] of this group whose [[Index of a subgroup|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.<ref name = "cam2">{{harvtxt|Cameron|1997}}, Section 1.8: The automorphism group.</ref> The statement about pointwise stabilizers is called the small index property,<ref name= "cam2"/> and proving it required showing that for every finite graph <math>X</math>, there is a finite graph <math>Z</math> containing <math>X</math> as an induced subgraph such that every isomorphism between induced subgraphs of <math>X</math> extends to an automorphism of <math>Z</math>.<ref>{{harvtxt|Hrushovski|1992}}</ref> 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.<ref>{{harvtxt|Macpherson|2011}}, Sections 5.2 and 5.3.</ref>

The construction of the Rado graph as an infinite circulant graph shows that its symmetry group includes automorphisms that generate a transitive infinite cyclic group. The difference set of this construction (the set of distances in the integers between adjacent vertices) can be constrained to include the difference 1, without affecting the correctness of this construction, from which it follows that the Rado graph contains an infinite [[Hamiltonian path]] whose symmetries are a subgroup of the symmetries of the whole graph.{{sfnp|Henson|1971}}

===Robustness against finite changes===
If a graph <math>G</math> 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 <math>U</math> and <math>V</math> it is still possible to find a vertex in the modified graph that is adjacent to everything in <math>U</math> and nonadjacent to everything in <math>V</math>, by adding the modified parts of <math>G</math> to <math>V</math> 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.<ref>{{harvtxt|Cameron|1997}}, Section 1.3: Indestructibility.</ref>

===Partitions===
For any partition of the vertices of the Rado graph into two sets <math>A</math> and <math>B</math>, 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. {{harvtxt|Cameron|2001}} 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 <math>U_i</math> and <math>V_i</math> that cannot be extended within each subgraph. But then, the union of the sets <math>U_i</math> and the union of the sets <math>V_i</math> 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 graph|complete graph]], and the empty graph.<ref>{{harvtxt|Cameron|1990}}; {{harvtxt|Diestel|Leader|Scott|Thomassé|2007}}.</ref> {{harvtxt|Bonato|Cameron|Delić|2000}} and {{harvtxt|Diestel|Leader|Scott|Thomassé|2007}} investigate infinite [[Directed graph|directed graph]]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.<ref>{{harvtxt|Pouzet|Sauer|1996}}.</ref> More generally, for every finite graph <math>A</math> there is a number <math>d_A</math> (called the big Ramsey degree of <math>A</math> in the Rado graph) such that for every partition of the copies of <math>A</math> in the Rado graph into finitely many sets, there is an induced subgraph isomorphic to the whole Rado graph that uses at most <math>d_A</math> of the colors.<ref>{{harvtxt|Sauer|2006}}</ref><ref>{{harvtxt|Dobrinen|2021}}</ref>

==Model theory and 0-1 laws==
{{harvtxt|Fagin|1976}} used the Rado graph to prove a [[Zero–one law|zero–one law]] for [[First-order logic|first-order]] statements in the [[Logic of graphs|logic of graphs]]. When a logical statement of this type is true or false for the Rado graph, it is also true or false (respectively) for [[Almost all|almost all]] finite graphs.

===First-order properties===
The first-order language of graphs is the collection of well-formed [[Philosophy:Sentence (mathematical logic)|sentences in mathematical logic]] formed from variables representing the vertices of graphs, [[Universal quantification|universal]] and [[Existential quantification|existential quantifiers]], [[Logical connective|logical connective]]s, and [[Predicate (mathematical logic)|predicates]] for equality and adjacency of vertices. For instance, the condition that a graph does not have any isolated vertices may be expressed by the sentence
<math display=block>\forall u:\exists v: u\sim v</math>
where the <math>\sim</math> symbol indicates the adjacency relation between two vertices.<ref>{{harvtxt|Spencer|2001}}, Section 1.2, "What Is a First Order Theory?", [https://books.google.com/books?id=ZJfsCAAAQBAJ&pg=PA15 pp.&nbsp;15–17].</ref>
This sentence <math>S</math> is true for some graphs, and false for others; a graph <math>G</math> is said to ''model'' <math>S</math>, written <math>G\models S</math>, if <math>S</math> is true of the vertices and adjacency relation of <math>G</math>.<ref>See, e.g., {{harvtxt|Grandjean|1983}}, p. 184.</ref>

The extension property of the Rado graph may be expressed by a collection of first-order sentences <math>E_{i,j}</math>, stating that for every choice of <math>i</math> vertices in a set <math>A</math> and <math>j</math> vertices in a set <math>B</math>, all distinct, there exists a vertex adjacent to everything in <math>A</math> and nonadjacent to everything in <math>B</math>.<ref>{{harvtxt|Spencer|2001}}, Section 1.3, "Extension Statements and Rooted Graphs", [https://books.google.com/books?id=ZJfsCAAAQBAJ&pg=PA17 pp.&nbsp;17–18].</ref> For instance, <math>E_{1,1}</math> can be written as
<math display=block>\forall a:\forall b:a\ne b\rightarrow\exists c:c\ne a\wedge c\ne b\wedge c\sim a\wedge\lnot(c\sim b).</math>

===Completeness===
{{harvtxt|Gaifman|1964}} proved that the sentences  <math>E_{i,j}</math>, together with additional sentences stating that the adjacency relation is [[Symmetric relation|symmetric]] and [[Reflexive relation|antireflexive]] (that is, that a graph modeling these sentences is undirected and has no self-loops), are the axioms of a [[Complete theory|complete theory]]. This means that, for each first-order sentence <math>S</math>, exactly one of <math>S</math> and its negation can be proven from these axioms.
Because the Rado graph models the extension axioms, it models all sentences in this theory.<ref>{{harvtxt|Gaifman|1964}}; {{harvtxt|Marker|2002}}, Theorem&nbsp;2.4.2, p.&nbsp;50.</ref>

In logic, a theory that has only one model (up to isomorphism) with a given infinite [[Cardinality|cardinality]] <math>\lambda</math> is called [[Morley's categoricity theorem|<math>\lambda</math>-categorical]]. The fact that the Rado graph is the unique countable graph with the extension property implies that it is also the unique countable model for its theory. This uniqueness property of the Rado graph can be expressed by saying that the theory of the Rado graph is [[Omega-categorical theory|ω-categorical]]. [[Biography:Jerzy Łoś|Łoś]] and Vaught proved in 1954 that when a theory is <math>\lambda</math>–categorical (for some infinite cardinal <math>\lambda</math>) and, in addition, has no finite models, then the theory must be complete.<ref>{{harvtxt|Łoś|1954}}; {{harvtxt|Vaught|1954}}; {{harvtxt|Enderton|1972}}, [https://books.google.com/books?id=LHjNCgAAQBAJ&pg=PA147 p.&nbsp;147].</ref> Therefore, Gaifman's theorem that the theory of the Rado graph is complete follows from the uniqueness of the Rado graph by the [[Łoś–Vaught test]].<ref>{{harvtxt|Marker|2002}}, Theorem&nbsp;2.2.6, p.&nbsp;42.</ref>

===Finite graphs and computational complexity===
As {{harvtxt|Fagin|1976}} proved, the first-order sentences provable from the extension axioms and modeled by the Rado graph are exactly the sentences true for almost all random finite graphs. This means that if one chooses an <math>n</math>-vertex graph uniformly at random among all graphs on <math>n</math> labeled vertices, then the probability that such a sentence will be true for the chosen graph approaches one in the limit as <math>n</math> approaches infinity. Symmetrically, the sentences that are not modeled by the Rado graph are false for almost all random finite graphs. It follows that every first-order sentence is either almost always true or almost always false for random finite graphs, and these two possibilities can be distinguished by determining whether the Rado graph models the sentence. Fagin's proof uses the [[Compactness theorem|compactness theorem]].<ref>{{harvtxt|Fagin|1976}}; {{harvtxt|Marker|2002}}, Theorem&nbsp;2.4.4, pp.&nbsp;51–52.</ref> Based on this equivalence, the theory of sentences modeled by the Rado graph has been called "the theory of the random graph" or "the almost sure theory of graphs".

Because of this 0-1 law, it is possible to test whether any particular first-order sentence is modeled by the Rado graph in a finite amount of time, by choosing a large enough value of <math>n</math> and counting the number of <math>n</math>-vertex graphs that model the sentence. However, here, "large enough" is at least exponential in the size of the sentence. For instance the extension axiom <math>E_{k,0}</math> implies the existence of a <math>(k+1)</math>-vertex [[Clique (graph theory)|clique]], but a clique of that size exists with high probability only in random graphs of size exponential in <math>k</math>.
It is unlikely that determining whether the Rado graph models a given sentence can be done more quickly than exponential time, as the problem is [[PSPACE-complete]].{{sfnp|Grandjean|1983}}

===Other model-theoretic properties===
The Rado graph is ultrahomogeneous, and thus is the [[Fraïssé limit]] of its class of finite substructures, i.e. the class of finite graphs.<ref>{{harvtxt|Macpherson|2011}}, Theorem 2.1.3, Example 2.2.1.</ref> Given that it is also in a finite relational language, ultrahomogeneity is equivalent to its theory having [[Quantifier elimination|quantifier elimination]] and being ω-categorical.<ref>{{harvtxt|Macpherson|2011}}, Corollary 3.1.3, Proposition 3.1.6.</ref> As the Rado graph is thus the countable model of a countable ω-categorical theory, it is both [[Prime model|prime]] and [[Saturated model|saturated]].<ref>{{harvtxt|Rothmaler|2000}}, Theorem 13.3.1, Theorem 13.2.1.</ref><ref>{{harvtxt|McNulty|2016}}, p.71 and p.75.</ref>

The theory of the Rado graph is a prototypical example of a theory with the [[NIP (model theory)|independence property]], and of a simple theory that is not [[Stable theory|stable]].<ref>{{harvtxt|Baldwin|2018}}</ref>

==Related concepts==
Although the Rado graph is universal for induced subgraphs, it is not universal for [[Isometry|isometric embeddings]] of graphs,
where an isometric embedding is a graph isomorphism which preserves [[Distance (graph theory)|distance]]. The Rado graph has [[Diameter (graph theory)|diameter]] two, and so any graph with larger diameter does not embed isometrically into it. {{harvs|last=Moss|year=1989|year2=1991|txt}} has described a family of universal graphs for isometric embedding, one for each possible finite graph diameter; the graph in his family with diameter two is the Rado graph.

The [[Henson graph]]s are countable graphs (one for each positive integer <math>i</math>) that do not contain an <math>i</math>-vertex [[Clique (graph theory)|clique]], and are universal for <math>i</math>-clique-free graphs. They can be constructed as induced subgraphs of the Rado graph.{{sfnp|Henson|1971}} The Rado graph, the Henson graphs and their complements, disjoint unions of countably infinite cliques and their complements, and infinite disjoint unions of isomorphic finite cliques and their complements are the only possible countably infinite [[Homogeneous graph|homogeneous graph]]s.{{sfnp|Lachlan|Woodrow|1980}}

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]] requirement that each color class form a [[Matching (graph theory)|matching]]. For any finite or countably infinite number of colors <math>\chi</math>, there exists a unique countably-infinite <math>\chi</math>-edge-colored graph <math>G_\chi</math> such that every partial isomorphism of a <math>\chi</math>-edge-colored finite graph can be extended to a full isomorphism. With this notation, the Rado graph is just <math>G_1</math>. {{harvtxt|Truss|1985}} investigates the automorphism groups of this more general family of graphs.

While the Rado graph is countable universal for the class of all graphs, not all graph classes have a countable universal graph. For example, there is no countable graph omitting the 4-cycle as a subgraph that contains all other such countable graphs as (not necessarily induced) subgraphs.<ref>{{harvtxt|Cherlin|2011}}, Fact 1.3</ref>

It follows from the classical model theory considerations of constructing a saturated model that under the [[Continuum hypothesis|continuum hypothesis]] CH, there is a universal graph with [[Cardinality of the continuum|continuum]] many vertices. Of course, under CH, the continuum is equal to <math>\aleph_1</math>, the [[Aleph number|first uncountable cardinal]]. {{harvs|last=Shelah|year=1984|year2=1990|txt}} uses [[Forcing (mathematics)|forcing]] to investigate universal graphs with <math>\aleph_1</math> many vertices and shows that even in the absence of CH, there may exist a universal graph of size <math>\aleph_1</math>. He also investigates analogous questions for higher cardinalities.

==Notes==
{{reflist|30em}}

==References==
{{refbegin|30em}}
*{{citation|journal=[[Mathematische Annalen]]
|year=1937|volume= 114|issue =1|pages= 305–315
|title=Die Widerspruchsfreiheit der allgemeinen Mengenlehre
*{{citation
 | doi = 10.4153/CMB-2000-047-6 | doi-access = free
 | last1 = Bonato | first1 = Anthony
 | last3 = Delić | first3 = Dejan
 | mr = 1793941
 | issue = 4
 | journal = [[Canadian Mathematical Bulletin]]
 | pages = 397–405
 | title = Tournaments and orders with the pigeonhole property
 | volume = 43
 | year = 2000}}.
*{{citation
 | last = Baldwin | first = John T.
 | doi = 10.1017/9781316987216 
 | isbn = 978-1-107-18921-8
 | mr = 3793636
 | publisher = Cambridge University Press
 | title = Model theory and the philosophy of mathematical practice: formalization without foundationalism
 | year = 2018| s2cid = 126311148
 }}.
*{{citation
 | mr = 1066691
 | isbn = 0-521-38836-8
 | location = Cambridge
 | publisher = Cambridge University Press
 | series = London Mathematical Society Lecture Note Series
 | title = Oligomorphic permutation groups
 | volume = 152
 | year = 1990}}.
*{{citation
 | contribution = The random graph
 | mr = 1425227
 | location = Berlin
 | pages = 333–351
 | publisher = Springer
 | series = [[Algorithms and Combinatorics]]
 | title = The mathematics of Paul Erdős, II
 | volume = 14
 | arxiv = 1301.7544
 | year = 1997| bibcode = 2013arXiv1301.7544C
 }}.
*{{citation
 | contribution = The random graph revisited
 | contribution-url = http://www.euro-math-soc.eu/ECM/ECM2000.1/Main/ECM2000.1.0267.0274.pdf
 | doi = 10.1007/978-3-0348-8268-2_15
 | mr = 1905324
 | location = Basel
 | pages = 267–274
 | publisher = Birkhäuser
 | series = Progr. Math.
 | title = European Congress of Mathematics, Vol. I (Barcelona, 2000)
 | volume = 201
 | year = 2001}}.
*{{citation
 | last = Cherlin | first = Gregory 
 | doi = 10.1016/j.disc.2011.03.014
 | mr = 2800977
 | issue = 15
 | journal = Discrete Mathematics
 | pages = 1543–1584
 | title = Forbidden substructures and combinatorial dichotomies: WQO and universality
 | volume = 311
 | year = 2011
 }}.
*{{citation
 | last1 = Diestel | first1 = Reinhard
 | last3 = Scott | first3 = Alex
 | last4 = Thomassé | first4 = Stéphan
 | doi = 10.1090/S0002-9947-06-04086-4
 | mr = 2276626
 | issue = 5
 | journal = [[Organization:Transactions of the American Mathematical Society|Transactions of the American Mathematical Society]]
 | pages = 2395–2405
 | title = Partitions and orientations of the Rado graph
 | volume = 359
 | year = 2007| doi-access = free
 }}.
*{{Cite arXiv 
 | eprint = 2110.00655v1 
 | last1 = Dobrinen | first1 = Natasha
 | title = Ramsey theory of homogeneous structures: current trends and open problems
 | year = 2021
 | class = math.LO | mode = cs2
 }}.
*{{citation
 | mr = 0337470
 | publisher = Academic Press, New York-London
 | title = A mathematical introduction to logic
 | year = 1972}}.
*{{citation
 | doi = 10.1007/BF01895716 | doi-access=free
 | mr = 0156334
 | journal = [[Acta Mathematica Hungarica|Acta Mathematica Academiae Scientiarum Hungaricae]]
 | pages = 295–315
 | title = Asymmetric graphs
 | volume = 14
 | year = 1963| issue = 3–4 }}.
*{{citation
 | last = Fagin | first = Ronald
 | issue = 1
 | journal = The Journal of Symbolic Logic
 | mr = 0476480
 | pages = 50–58
 | title = Probabilities on finite models
 | url = http://researcher.ibm.com/researcher/files/us-fagin/jsl76.pdf
 | volume = 41
 | year = 1976
 | doi=10.1017/s0022481200051756
 | jstor=2272945| s2cid = 2563318
 }}.
*{{citation
 | last = Gaifman | first = Haim
 | doi = 10.1007/BF02759729 | doi-access=free
 | journal = [[Israel Journal of Mathematics]]
 | mr = 0175755
 | pages = 1–18
 | title = Concerning measures in first order calculi
 | volume = 2
 | year = 1964}}.
*{{citation
 | last = Grandjean | first = Étienne
 | doi = 10.1016/S0019-9958(83)80043-6
 | issue = 2–3
 | journal = Information and Control
 | mr = 742707
 | pages = 180–204
 | title = Complexity of the first-order theory of almost all finite structures
 | volume = 57
 | year = 1983| doi-access = free
 }}.
*{{citation
 | last = Henson | first = C. Ward
 | journal = [[Pacific Journal of Mathematics]]
 | mr = 0304242
 | pages = 69–83
 | title = A family of countable homogeneous graphs
 | volume = 38
 | year = 1971
 | doi=10.2140/pjm.1971.38.69| doi-access = free
 }}.
*{{citation|title=A Shorter Model Theory|last=Hodges|first=Wilfrid|date=1997|publisher=Cambridge University Press|isbn=0-521-58713-1|oclc=468298248}}
*{{citation
 | last1 = Horsley | first1 = Daniel
 | last2 = Pike | first2 = David A.
 | last3 = Sanaei | first3 = Asiyeh
 | doi = 10.1002/jcd.20283
 | issue = 4
 | journal = Journal of Combinatorial Designs
 | mr = 2838911
 | pages = 317–327
 | title = Existential closure of block intersection graphs of infinite designs having infinite block size
 | volume = 19
 | year = 2011| s2cid = 120707836
 }}.
*{{citation
 | last1 = Hrushovski | first1 = Ehud
 | doi = 10.1007/BF01305233
 | issue = 4
 | journal = [[Combinatorica]]
 | mr = 1194731
 | pages = 411–416
 | title = Extending partial isomorphisms of graphs
 | volume = 12
 | year = 1992
 | s2cid = 19939702
 }}.
*{{citation
 | last1 = Lachlan | first1 = A. H.
 | last2 = Woodrow | first2 = Robert E.
 | doi = 10.2307/1999974
 | issue = 1
 | journal = [[Organization:Transactions of the American Mathematical Society|Transactions of the American Mathematical Society]]
 | mr = 583847
 | pages = 51–94
 | title = Countable ultrahomogeneous undirected graphs
 | volume = 262
 | year = 1980| jstor = 1999974
 | doi-access = free
 }}.
*{{citation
 | journal = Colloquium Math.
 | mr = 0061561
 | pages = 58–62
 | title = On the categoricity in power of elementary deductive systems and some related problems
 | volume = 3
 | year = 1954| doi = 10.4064/cm-3-1-58-62 | doi-access = free
 }}.
*{{citation
 | journal = Discrete Mathematics
 | issue = 15
 | mr = 2800979
 | pages = 1599–1634
 | title = A survey of homogeneous structures
 | volume = 311
 | year = 2011| doi = 10.1016/j.disc.2011.01.024 | doi-access = free
 }}.
*{{citation
 | last = Marker | first = David
 | isbn = 0-387-98760-6
 | mr = 1924282
 | publisher = Springer-Verlag, New York
 | series = Graduate Texts in Mathematics
 | title = Model theory
 | volume = 217
 | year = 2002}}.
*{{citation
 | last = McNulty | first = George F.
 | pages = 71–75
 | title = Elementary Model Theory
 | url = https://people.math.sc.edu/mcnulty/762/modeltheory.pdf
 | year = 2016
 | access-date = 5 April 2023
 }}.
*{{citation
 | last = Moss | first = Lawrence S.
 | mr = 1059159
 | issue = 1
 | journal = Polska Akademia Nauk. Fundamenta Mathematicae
 | pages = 25–37
 | title = Existence and nonexistence of universal graphs
 | volume = 133
 | year = 1989| doi = 10.4064/fm-133-1-25-37
 | doi-access = free
 }}.
*{{citation
 | last = Moss | first = Lawrence S.
 | contribution = The universal graphs of fixed finite diameter
 | mr = 1170834
 | location = New York
 | pages = 923–937
 | publisher = Wiley
 | series = Wiley-Intersci. Publ.
 | title = Graph theory, combinatorics, and applications. Vol. 2 (Kalamazoo, MI, 1988)
 | year = 1991}}.
*{{citation
 | last1 = Pouzet | first1 = Maurice
 | last2 = Sauer | first2 = Norbert
 | doi = 10.1007/BF01271269
 | mr = 1433638
 | issue = 4
 | journal = [[Combinatorica]]
 | pages = 505–520
 | title = Edge partitions of the Rado graph
 | volume = 16
 | year = 1996| s2cid = 206793062
 }}.
*{{citation|first=Richard|last=Rado|url=http://matwbn.icm.edu.pl/ksiazki/aa/aa9/aa9133.pdf|title=Universal graphs and universal functions|journal=Acta Arith.|year=1964|volume=9|issue=4 |pages=331–340|doi=10.4064/aa-9-4-331-340 }}.
*{{citation
 | last = Rothmaler | first = Philipp
 | isbn = 90-5699-287-2
 | mr = 1800596
 | series = Algebra, logic and applications
 | publisher = Gordon and Breach Science Publishers
 | title = Introduction to model theory
 | volume = 15
 | year = 2000
 }}.
*{{citation
 | last1 = Sauer | first1 = Norbert
 | doi = 10.1007/s00493-006-0015-0
 | mr = 2223636
 | issue = 2
 | journal = [[Combinatorica]]
 | pages = 231–253
 | title = Coloring subgraphs of the Rado graph
 | volume = 26
 | year = 2006
 | s2cid = 19251747
 }}.
*{{citation
 | doi = 10.1016/0168-0072(84)90042-3
 | mr = 739914
 | issue = 1
 | journal = [[Annals of Pure and Applied Logic]]
 | pages = 75–87
 | title = On universal graphs without instances of CH
 | volume = 26
 | year = 1984| doi-access = free
 }}.
*{{citation
 | doi = 10.1007/BF02807219 | doi-access=free
 | mr = 1057268
 | issue = 1
 | journal = [[Israel Journal of Mathematics]]
 | pages = 69–81
 | title = Universal graphs without instances of CH: revisited
 | volume = 70
 | year = 1990}}.
*{{citation
 | doi = 10.1007/978-3-662-04538-1
 | isbn = 3-540-41654-4
 | mr = 1847951
 | publisher = Springer-Verlag, Berlin
 | series = Algorithms and Combinatorics
 | title = The Strange Logic of Random Graphs
 | title-link = The Strange Logic of Random Graphs
 | volume = 22
 | year = 2001| s2cid = 118026950 }}.
*{{citation
 | doi = 10.1017/S0305004100063428
 | mr = 795890
 | issue = 2
 | journal = [[Organization:Mathematical Proceedings of the Cambridge Philosophical Society|Mathematical Proceedings of the Cambridge Philosophical Society]]
 | pages = 213–245
 | title = The group of the countable universal graph
 | volume = 98
 | year = 1985| bibcode = 1985MPCPS..98..213T
 | s2cid = 122772888 }}.
*{{citation
 | journal = [[Indagationes Mathematicae]]
 | mr = 0063993
 | pages = 467–472
 | title = Applications to the Löwenheim-Skolem-Tarski theorem to problems of completeness and decidability
 | volume = 16
 | year = 1954| doi = 10.1016/S1385-7258(54)50058-2 }}.
{{refend}}

[[Category:Individual graphs]]
[[Category:Random graphs]]
[[Category:Infinite graphs]]

{{Sourceattribution|Rado graph}}