Given a set of vertices , a random graph is given by deciding, independently with probability , whether each unordered pair of vertices should be joined by an edge or not. Following Peter Cameron’s book, Permutation Groups, we prove here that there exists a countable graph (unique up to isomorphism) such that each random countable graph is isomorphic to with probability . Moreover, we shall see that the existence of such a graph implies a 0-1 law for first-order properties of finite graphs.
Definition: We say that a graph has the property if for all disjoint finite subsets of vertices there exists a vertex joined to every vertex of and to no vertex of .
The two following lemmas show that, up to isomorphism, there exists only one countable graph satisfying property : the so-called Rado graph, denoted .
Lemma 1: Two countable graphs satisfying property are isomorphic.
Proof. Let be two countable graphs satisfying property . For convenience, let and be an enumeration of and respectively.
Let be the empty morphism. Then, by induction:
1) If is odd: Let be the first vertex in the enumeration of not in the domain of . If (resp. ) denotes the set of vertices of joined (resp. not joined) to by an edge, according to property , there exists a vertex joined by an edge to any vertex of and to no vertex of . Therefore, can be extended to by setting .
2) If is even: Let be the first vertex in the enumeration of not in the range of . If (resp. ) denotes the set of vertices of joined (resp. not joined) to by an edge, according to property , there exists a vertex joined by an edge to any vertex of and to no vertex of . Therefore, can be extended to by setting .
Finally, defines an isomorphism between and .
It is worth noticing that the previous proof gives an isomorphism as soon as is an isomorphism between two subgraphs. Therefore, we have:
Property 1: is homogenous, ie. every isomorphism between two finite induced subgraphs can be extented to an automorphism of .
Moreover, using only the first step of our induction, we have:
Property 2: is universal, ie. every at most countable graph is isomorphic to a subgraph of .
In fact, it can be shown that is the only countable, universal and homogenous graph (up to isomorphism); see Peter Cameron’s book for more details.
Lemma 2: A countable random graph has property with probability .
Proof. Because there exist only countably many pairs of finite subsets of vertices , it is sufficient to show that the event that the property for and fixed fails has probability zero. But the probability that a point be joined by an edge to any vertex of and to no vertex of is , where . Therefore,
In particular, lemma 2 shows that there exists a countable graph satisfying property , justifying our definition of . We deduce the following theorem from lemmas 1 and 2:
Theorem 1: A countable random graph is isomorphic to with probability .
From now on, let us consider graph theory from model theory viewpoint, that is we view a graph as a model of the theory
over the langage . Here, the relation means that the vertices and are joined by an edge; therefore, in the graphs are unoriented and do not contain loops. It is worth noticing that a graph satisfies property if and only if it satisfies the first-order sentence
for all , where
Therefore, is a first-order property. We now are able to deduce a 0-1 law for finite graphs:
Definition: A property is true in almost all finite graphs if the proportion of graphs of cardinality satisfying the given property tends to as .
Theorem 2: Let be a sentence in the first-order langage of graph theory. If (resp. if ) then is true (resp. false) in almost all finite graphs. In particular, a first-ordre sentence is either true in almost all finite graphs or false in almost all finite graphs.
Proof. Suppose that . By our previous remark, the sentence can be logically deduced from the sentences , ie. . Then, it is a consequence of compactness theorem that can be logically deduced from only finitely many sentences . Therefore, it is sufficient to prove that each fails in a random graph of cardinality with probability such that .
Clearly, is smaller than the product of the number of choices of a subset of vertices by the probability that the other vertices are not correctly joined (so that be not satisfied), that is
If , then and is true in almost all finite graphs.
It can be unsatisfactory that we only give a non-constructive proof for the existence of ; to conclude, we give an explicit construction:
Let be the set of vertices; two integers are joined by an edge if and only if the -th digit (from right to left) of , written in binary, is one. Then, the constructed graph has property : Let be two finite disjoint subsets of vertices and be such that for all . Now, let be the binary number , where , and for every , if and otherwise (in particular, if ). Then is joined by an edge to every vertex of and to no vertex of .