Given a set of vertices X, a random graph is given by deciding, independently with probability 1/2, 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 R (unique up to isomorphism) such that each random countable graph is isomorphic to R with probability 1. 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 \Gamma has the property \mathcal{P} if for all disjoint finite subsets of vertices U,V there exists a vertex z \notin U \cup V joined to every vertex of U and to no vertex of V.

The two following lemmas show that, up to isomorphism, there exists only one countable graph satisfying property \mathcal{P}: the so-called Rado graph, denoted R.

Lemma 1: Two countable graphs satisfying property \mathcal{P} are isomorphic.

Proof. Let \Gamma_1, \Gamma_2 be two countable graphs satisfying property \mathcal{P}. For convenience, let (f_1,f_2, \dots) and (g_1,g_2, \dots) be an enumeration of \Gamma_1 and \Gamma_2 respectively.

Let \varphi_0 : \emptyset \to \Gamma_2 be the empty morphism. Then, by induction:

1) If n is odd: Let f be the first vertex in the enumeration of \Gamma_1 not in the domain S_{n-1} of \varphi_{n-1}. If U (resp. V) denotes the set of vertices of S_{n-1} joined (resp. not joined) to f by an edge, according to property \mathcal{P}, there exists a vertex z \notin \varphi_{n-1}(U) \cup \varphi_{n-1}(V) = \varphi_{n-1}(S_{n-1}) joined by an edge to any vertex of \varphi_{n-1}(U) and to no vertex of \varphi_{n-1}(V). Therefore, \varphi_{n-1} can be extended to \varphi_n : S_{n-1} \cup \{f\} \to \Gamma_2 by setting \varphi_n(f)=z.

2) If n is even: Let g be the first vertex in the enumeration of \Gamma_2 not in the range R_{n-1} of \varphi_{n-1}. If U (resp. V) denotes the set of vertices of R_{n-1} joined (resp. not joined) to g by an edge, according to property \mathcal{P}, there exists a vertex z \notin \varphi_{n-1}^{-1}(V) \cup \varphi_{n-1}^{-1}(U)= \varphi_{n-1}^{-1}(R_{n-1}) joined by an edge to any vertex of \varphi_{n-1}^{-1}(U) and to no vertex of \varphi_{n-1}^{-1}(V). Therefore, \varphi_{n-1} can be extended to \varphi_n : S_{n-1} \cup \{z\} \to R_{n-1} \cup \{g \} by setting \varphi_n(z)=g.

Finally, \varphi := \bigcup\limits_{n \geq 0} \varphi_n defines an isomorphism between \Gamma_1 and \Gamma_2. \square

It is worth noticing that the previous proof gives an isomorphism as soon as \varphi_0 is an isomorphism between two subgraphs. Therefore, we have:

Property 1: R is homogenous, ie. every isomorphism between two finite induced subgraphs can be extented to an automorphism of R.

Moreover, using only the first step of our induction, we have:

Property 2: R is universal, ie. every at most countable graph is isomorphic to a subgraph of R.

In fact, it can be shown that R 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 \mathcal{P} with probability 1.

Proof. Because there exist only countably many pairs of finite subsets of vertices (U,V), it is sufficient to show that the event that the property \mathcal{P} for U and V fixed fails has probability p zero. But the probability that a point z \notin U \cup V be joined by an edge to any vertex of U and to no vertex of V is 1/2^k, where k= |U \cup V|. Therefore,

\displaystyle p = \lim\limits_{n \to + \infty} \left( 1- \frac{1}{2^k} \right)^n =0. \square

In particular, lemma 2 shows that there exists a countable graph satisfying property \mathcal{P}, justifying our definition of R. We deduce the following theorem from lemmas 1 and 2:

Theorem 1: A countable random graph is isomorphic to R with probability 1.

From now on, let us consider graph theory from model theory viewpoint, that is we view a graph as a model of the theory

\mathcal{T}_{\text{graph}} = \left\{ \forall x, \neg (x \sim x) ; \forall x,y (x \sim y \Leftrightarrow y \sim x) \right\}

over the langage \mathcal{L}= \{ \sim, =\}. Here, the relation x \sim y means that the vertices x and y are joined by an edge; therefore, in \mathcal{T}_{\text{graph}} the graphs are unoriented and do not contain loops. It is worth noticing that a graph satisfies property \mathcal{P} if and only if it satisfies the first-order sentence

\Phi_{m,n} = \forall x_1, \dots, x_m \forall y_1, \dots, y_n \exists z \Phi_{m,n} ( \overline{x} , \overline{y},z)

for all m,n \geq 1, where

\Phi_{mn} (\overline{x}, \overline{y},z) = \left[ \bigwedge\limits_{i,n} (x_i \neq y_j ) \Rightarrow \left( \bigwedge\limits_{i,j} (z \neq x_i,y_j ) \wedge \bigwedge\limits_i (z \sim x_i ) \wedge \bigwedge\limits_{j} \neg (z \sim y_j) \right) \right].

Therefore, \mathcal{P} 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 n satisfying the given property tends to 1 as n \to + \infty.

Theorem 2: Let \sigma be a sentence in the first-order langage of graph theory. If R \models \sigma (resp. if R \not\models \sigma) then \sigma 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 R \models \sigma. By our previous remark, the sentence \sigma can be logically deduced from the sentences \Phi_{m,n}, ie. \{\Phi_{m,n}, m,n \geq 1 \} \vdash \sigma. Then, it is a consequence of compactness theorem that \sigma can be logically deduced from only finitely many sentences \Phi_{m,n}. Therefore, it is sufficient to prove that each \Phi_{m,n} fails in a random graph of cardinality k with probability p_k such that p_k \underset{k \to + \infty}{\longrightarrow} 0.

Clearly, p_k is smaller than the product of the number of choices of a subset of m+n vertices by the probability that the other vertices are not correctly joined (so that \Phi_{m,n} be not satisfied), that is

\displaystyle p_k \leq C_{k}^{m+n} \left( 1- \frac{1}{2^{m+n}} \right)^{k-m-n} \underset{k \to + \infty}{\longrightarrow} 0.

If R \not\models \sigma, then R \models \neg \sigma and \neg \sigma is true in almost all finite graphs. \square

It can be unsatisfactory that we only give a non-constructive proof for the existence of R; to conclude, we give an explicit construction:

Let \mathbb{N} be the set of vertices; two integers n < m are joined by an edge if and only if the n-th digit (from right to left) of m, written in binary, is one. Then, the constructed graph has property \mathcal{P}: Let U, V be two finite disjoint subsets of vertices and p \geq 1 be such that 2^p>x for all x \in U \cup V. Now, let z be the binary number \epsilon_p \cdots \epsilon_0, where \epsilon_p=1, and for every 0 \leq i \leq p-1, \epsilon_i=1 if i \in U and 0 otherwise (in particular, if i \in V). Then z \notin U \cup V is joined by an edge to every vertex of U and to no vertex of V.

 

Advertisements