Countable Random Graph
   HOME

TheInfoList



OR:

In the mathematical field of
graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, the Rado graph, Erdős–Rényi graph, or random graph is a
countably infinite In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...
graph that can be constructed (with
probability one In probability theory, an event is said to happen almost surely (sometimes abbreviated as a.s.) if it happens with probability 1 (or Lebesgue measure 1). In other words, the set of possible exceptions may be non-empty, but it has probability 0. ...
) 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 Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...
, and
Alfréd Rényi Alfréd Rényi (20 March 1921 – 1 February 1970) was a Hungarian mathematician known for his work in probability theory, though he also made contributions in combinatorics, graph theory, and number theory. Life Rényi was born in Budapest to ...
, 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, by symmetrizing the membership relation of the hereditarily finite sets, by applying the
BIT predicate In mathematics and computer science, the BIT predicate or Ackermann coding, sometimes written BIT(''i'', ''j''), is a predicate that tests whether the ''j''th bit of the number ''i'' is 1, when ''i'' is written in binary. History The BIT pred ...
to the
binary representation A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" (one). The base-2 numeral system is a positional notation ...
s of the
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...
s, or as an infinite
Paley graph In mathematics, Paley graphs are dense undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, whic ...
that has edges connecting pairs of
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s congruent to 1 mod 4 that are
quadratic residue In number theory, an integer ''q'' is called a quadratic residue modulo ''n'' if it is congruent to a perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that: :x^2\equiv q \pmod. Otherwise, ''q'' is called a quadratic no ...
s modulo each other. 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 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 In mathematics, the term "almost all" means "all but a negligible amount". More precisely, if X is a set, "almost all elements of X" means "all elements of X but those in a negligible subset of X". The meaning of "negligible" depends on the math ...
random finite graphs, and the sentences that are false for the Rado graph are also false for almost all finite graphs. In
model theory In mathematical logic, model theory is the study of the relationship between formal theories (a collection of sentences in a formal language expressing statements about a mathematical structure), and their models (those structures in which the s ...
, the Rado graph forms an example of a
saturated model In mathematical logic, and particularly in its subfield model theory, a saturated model ''M'' is one that realizes as many complete types as may be "reasonably expected" given its size. For example, an ultrapower model of the hyperreals is \al ...
of an ω-categorical and
complete theory In mathematical logic, a theory is complete if it is consistent and for every closed formula in the theory's language, either that formula or its negation is provable. That is, for every sentence \varphi, the theory T contains the sentence or its ...
.


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 In mathematics, a universal graph is an infinite graph that contains ''every'' finite (or at-most-countable) graph as an induced subgraph. A universal graph of this type was first constructed by Richard Rado and is now called the Rado graph or ...
, 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

and constructed the Rado graph using the
BIT predicate In mathematics and computer science, the BIT predicate or Ackermann coding, sometimes written BIT(''i'', ''j''), is a predicate that tests whether the ''j''th bit of the number ''i'' is 1, when ''i'' is written in binary. History The BIT pred ...
as follows. They identified the vertices of the graph with the
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...
s 0, 1, 2, ... An edge connects vertices x and y in the graph (where x < y) whenever the xth bit of the
binary Binary may refer to: Science and technology Mathematics * Binary number, a representation of numbers using only two digits (0 and 1) * Binary function, a function that takes two arguments * Binary operation, a mathematical operation that t ...
representation of 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 probability theory, an event is said to happen almost surely (sometimes abbreviated as a.s.) if it happens with probability 1 (or Lebesgue measure 1). In other words, the set of possible exceptions may be non-empty, but it has probability 0. ...
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 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 In probability theory, an event is said to happen almost surely (sometimes abbreviated as a.s.) if it happens with probability 1 (or Lebesgue measure 1). In other words, the set of possible exceptions may be non-empty, but it has probability 0. ...
produces the same infinite graph. For any graph generated randomly in this way, the
complement graph In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of a ...
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.


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. The Rado graph may also be formed by a construction resembling that for
Paley graph In mathematics, Paley graphs are dense undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, whic ...
s, taking as the vertices of a graph all the
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
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 In number theory, an integer ''q'' is called a quadratic residue modulo ''n'' if it is congruent to a perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that: :x^2\equiv q \pmod. Otherwise, ''q'' is called a quadratic no ...
modulo the other. By quadratic reciprocity and the restriction of the vertices to primes congruent to 1 mod 4, this is a
symmetric relation A symmetric relation is a type of binary relation. An example is the relation "is equal to", because if ''a'' = ''b'' is true then ''b'' = ''a'' is also true. Formally, a binary relation ''R'' over a set ''X'' is symmetric if: :\forall a, b \in X( ...
, 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 In graph theory, a circulant graph is an undirected graph acted on by a cyclic group of symmetries which takes any vertex to any other vertex. It is sometimes called a cyclic graph, but this term has other meanings. Equivalent definitions Circ ...
, with the integers as its vertices and with an edge between each two integers whose distance (the
absolute value In mathematics, the absolute value or modulus of a real number x, is the non-negative value without regard to its sign. Namely, , x, =x if is a positive number, and , x, =-x if x is negative (in which case negating x makes -x positive), an ...
of their difference) belongs to a particular set S. To construct the Rado graph in this way, S may be chosen randomly, or by choosing the
indicator function In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if is a subset of some set , one has \mathbf_(x)=1 if x\i ...
of S to be the concatenation of all finite binary sequences. The Rado graph can also be constructed as the block intersection graph of an infinite
block design In combinatorial mathematics, a block design is an incidence structure consisting of a set together with a family of subsets known as ''blocks'', chosen such that frequency of the elements satisfies certain conditions making the collection of bl ...
in which the number of points and the size of each block are
countably infinite In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...
. It can also be constructed as the
Fraïssé limit In mathematical logic, specifically in the discipline of model theory, the Fraïssé limit (also called the Fraïssé construction or Fraïssé amalgamation) is a method used to construct (infinite) mathematical structures from their (finite) su ...
of the class of finite graphs.


Properties


Extension

The Rado graph satisfies the following extension property: for every two disjoint finite sets of vertices U and V, there exists a vertex x outside both sets that is connected to all vertices in U, but has no neighbors in V. For instance, with the binary-number definition of the Rado graph, let x=2^ + \sum_ 2^u. 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. With the random-graph definition of the Rado graph, each vertex outside the union of U and V has probability 1/2^ 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 U and V, by the
Chinese remainder theorem In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of thes ...
, the numbers that are quadratic residues modulo every prime in U and nonresidues modulo every prime in V 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 G within the Rado graph, as induced subgraphs. To do so, order the vertices of G, and add vertices in the same order to a partial copy of G within the Rado graph. At each step, the next vertex in G will be adjacent to some set U of vertices in G that are earlier in the ordering of the vertices, and non-adjacent to the remaining set V of earlier vertices in G. By the extension property, the Rado graph will also have a vertex x that is adjacent to all the vertices in the partial copy that correspond to members of U, and non-adjacent to all the vertices in the partial copy that correspond to members of V. Adding x to the partial copy of G 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 In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...
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 G and H be two countable graphs with the extension property, let G_i and H_i be isomorphic finite induced subgraphs of G and H respectively, and let g_i and h_i be the first vertices in an enumeration of the vertices of G and H respectively that do not belong to G_i and H_i. Then, by applying the extension property twice, one can find isomorphic induced subgraphs G_ and H_ that include g_i and h_i 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 In mathematical logic, especially set theory and model theory, the back-and-forth method is a method for showing isomorphism between countably infinite structures satisfying specified conditions. In particular it can be used to prove that * any t ...
, G and H 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.


Symmetry

Applying the back-and-forth construction to any two isomorphic finite subgraphs of the Rado graph extends their isomorphism to an
automorphism In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms ...
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 In set theory, the cardinality of the continuum is the cardinality or "size" of the set of real numbers \mathbb R, sometimes called the continuum. It is an infinite cardinal number and is denoted by \mathfrak c (lowercase fraktur "c") or , \mathb ...
. Every subgroup of this group whose
index Index (or its plural form indices) may refer to: Arts, entertainment, and media Fictional entities * Index (''A Certain Magical Index''), a character in the light novel series ''A Certain Magical Index'' * The Index, an item on a Halo megastru ...
is less than the cardinality of the continuum can be sandwiched between the pointwise stabilizer and the stabilizer of a finite set of vertices. 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.


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

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 U_i and V_i that cannot be extended within each subgraph. But then, the union of the sets U_i and the union of the sets V_i 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, and the
empty graph In the mathematical field of graph theory, the term "null graph" may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph"). Order-zero graph The order-zero graph, , is th ...
. and investigate infinite directed graphs 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.


Model theory and 0-1 laws

used the Rado graph to prove a
zero–one law In probability theory, a zero–one law is a result that states that an event must have probability 0 or 1 and no intermediate value. Sometimes, the statement is that the limit of certain probabilities must be 0 or 1. It may refer to: * Borel–C ...
for
first-order In mathematics and other formal sciences, first-order or first order most often means either: * "linear" (a polynomial of degree at most one), as in first-order approximation and other calculus uses, where it is contrasted with "polynomials of high ...
statements in the
logic of graphs In the mathematical fields of graph theory and finite model theory, the logic of graphs deals with formal specifications of graph properties using sentences of mathematical logic. There are several variations in the types of logical operation that ...
. 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 In mathematics, the term "almost all" means "all but a negligible amount". More precisely, if X is a set, "almost all elements of X" means "all elements of X but those in a negligible subset of X". The meaning of "negligible" depends on the math ...
finite graphs.


First-order properties

The first-order language of graphs is the collection of well-formed sentences in mathematical logic formed from variables representing the vertices of graphs,
universal Universal is the adjective for universe. Universal may also refer to: Companies * NBCUniversal, a media and entertainment company ** Universal Animation Studios, an American Animation studio, and a subsidiary of NBCUniversal ** Universal TV, a t ...
and existential quantifiers,
logical connective In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary co ...
s, and 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 \forall u:\exists v: u\sim v where the \sim symbol indicates the adjacency relation between two vertices. This sentence S is true for some graphs, and false for others; a graph G is said to ''model'' S, written G\models S, if S is true of the vertices and adjacency relation of G. The extension property of the Rado graph may be expressed by a collection of first-order sentences E_, stating that for every choice of i vertices in a set A and j vertices in a set B, all distinct, there exists a vertex adjacent to everything in A and nonadjacent to everything in B. For instance, E_ can be written as \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).


Completeness

proved that the sentences E_, together with additional sentences stating that the adjacency relation is symmetric and antireflexive (that is, that a graph modeling these sentences is undirected and has no self-loops), are the axioms of a
complete theory In mathematical logic, a theory is complete if it is consistent and for every closed formula in the theory's language, either that formula or its negation is provable. That is, for every sentence \varphi, the theory T contains the sentence or its ...
. This means that, for each first-order sentence S, exactly one of S and its negation can be proven from these axioms. Because the Rado graph models the extension axioms, it models all sentences in this theory. In logic, a theory that has only one model (up to isomorphism) with a given infinite
cardinality In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
\lambda is called \lambda-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 ω-categorical. Łoś and Vaught proved in 1954 that when a theory is \lambda–categorical (for some infinite cardinal \lambda) and, in addition, has no finite models, then the theory must be complete. 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 In model theory, a branch of mathematical logic, the Łoś–Vaught test is a criterion for a theory to be complete, unable to be augmented without becoming inconsistent. For theories in classical logic Classical logic (or standard logic or Frege-R ...
.


Finite graphs and computational complexity

As proved, the first-order sentences provable from the extension axioms and modeled by the Rado graph are exactly the sentences true for
almost all In mathematics, the term "almost all" means "all but a negligible amount". More precisely, if X is a set, "almost all elements of X" means "all elements of X but those in a negligible subset of X". The meaning of "negligible" depends on the math ...
random finite graphs. This means that if one chooses an n-vertex graph uniformly at random among all graphs on n labeled vertices, then the probability that such a sentence will be true for the chosen graph approaches one in the limit as n 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 In probability theory, an event is said to happen almost surely (sometimes abbreviated as a.s.) if it happens with probability 1 (or Lebesgue measure 1). In other words, the set of possible exceptions may be non-empty, but it has probability 0. ...
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.; , Theorem 2.4.4, pp. 51–52. 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 n and counting the number of n-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 E_ implies the existence of a (k+1)-vertex clique, but a clique of that size exists with high probability only in random graphs of size exponential in k. 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.


Saturated model

From the
model theoretic In mathematical logic, model theory is the study of the relationship between formal theories (a collection of sentences in a formal language expressing statements about a mathematical structure), and their models (those structures in which the st ...
point of view, the Rado graph is an example of a
saturated model In mathematical logic, and particularly in its subfield model theory, a saturated model ''M'' is one that realizes as many complete types as may be "reasonably expected" given its size. For example, an ultrapower model of the hyperreals is \al ...
. This is just a logical formulation of the property that the Rado graph contains all finite graphs as induced subgraphs. In this context, a
type Type may refer to: Science and technology Computing * Typing, producing text via a keyboard, typewriter, etc. * Data type, collection of values used for computations. * File type * TYPE (DOS command), a command to display contents of a file. * Ty ...
is a set of variables together with a collection of constraints on the values of some or all of the predicates determined by those variables; a complete type is a type that constrains all of the predicates determined by its variables. In the theory of graphs, the variables represent vertices and the predicates are the adjacencies between vertices, so a complete type specifies whether an edge is present or absent between every pair of vertices represented by the given variables. That is, a complete type specifies the subgraph that a particular set of vertex variables induces. A saturated model is a model that realizes all of the types that have a number of variables at most equal to the cardinality of the model. The Rado graph has induced subgraphs of all finite or countably infinite types, so it is saturated.


Related concepts

Although the Rado graph is universal for induced subgraphs, it is not universal for isometric embeddings of graphs, where an isometric embedding is a graph isomorphism which preserves
distance Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...
. The Rado graph has
diameter In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid for ...
two, and so any graph with larger diameter does not embed isometrically into it. 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 In graph theory, the Henson graph is an undirected infinite graph, the unique countable homogeneous graph that does not contain an -vertex clique (graph theory), clique but that does contain all -free finite graphs as induced subgraphs. For instanc ...
s are countable graphs (one for each positive integer i) that do not contain an i-vertex clique, and are universal for i-clique-free graphs. They can be constructed as induced subgraphs of the Rado graph. 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 graphs. 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 requirement that each color class form a matching. For any finite or countably infinite number of colors \chi, there exists a unique countably-infinite \chi-edge-colored graph G_\chi such that every partial isomorphism of a \chi-edge-colored finite graph can be extended to a full isomorphism. With this notation, the Rado graph is just G_1. investigates the automorphism groups of this more general family of graphs. It follows from the classical model theory considerations of constructing a saturated model that under the continuum hypothesis CH, there is a universal graph with
continuum Continuum may refer to: * Continuum (measurement), theories or models that explain gradual transitions from one condition to another without abrupt changes Mathematics * Continuum (set theory), the real line or the corresponding cardinal number ...
many vertices. Of course, under CH, the continuum is equal to \aleph_1, the first uncountable cardinal. uses
forcing Forcing may refer to: Mathematics and science * Forcing (mathematics), a technique for obtaining independence proofs for set theory *Forcing (recursion theory), a modification of Paul Cohen's original set theoretic technique of forcing to deal with ...
to investigate universal graphs with \aleph_1 many vertices and shows that even in the absence of CH, there may exist a universal graph of size \aleph_1. He also investigates analogous questions for higher cardinalities.


Notes


References

* *. *. *. *. *. *. *. *. *. *. *. * *. *. *. *. *. *. *. *. *. *. *. *. *. *. {{refend Individual graphs Random graphs Infinite graphs