Combinatorics

Section 11.5 Random graphs

This section is intended as optional enrichment material. In the current edition, no exercises are included. The main goal of this section is to make you aware of the existence of random graphs, without actually studying their properties for the most part.

There are two commonly-used models of random graphs on \(n\) vertices: the model due to Edgar Nelson Gilbert (1923—2013) (the “Gilbert model”) and the model due to Pál Erdős (1913—1996) and Alfréd Rényi (1921—1970) (the “Erdős-Rényi model”). In each case, we consider \(n\) (the number of vertices) to be fixed, and use probability (randomness) to determine the edges of our graph.

Suppose we have three vertices \(u\text{,}\) \(v\text{,}\) and \(w\text{,}\) and we fix \(p=1/4\text{.}\) For each pair of vertices, we flip a coin twice, and draw an edge between the vertices only if we obtain heads both times. We have three pairs of vertices, so flip the coin \(6\) times, with the first two flips are for \(uv\text{,}\) the next two for \(uw\text{,}\) and the final two are for \(vw\text{.}\) The outcomes on our first attempt are T, T, T, H, T, H. Our result is the empty graph, shown below.

On our second attempt, the outcomes are H, H, T, H, H, T. The result is again shown below.

Under the Gilbert model, the probability of obtaining a given graph that has \(m\) edges (where \(0 \le m \le \binom{n}{2}\)) is \(p^m(1-p)^{\binom{n}{2}-m}\text{.}\) If \(p\) is large, obtaining a graph that has many edges is much more likely than a graph that has few edges; if \(p\) is small, a graph with few edges is more likely. If \(p=1/2\text{,}\) then any given (labelled) graph will be equally likely to arise.

Under the Erdős-Rényi model, since there are \(\binom{\binom{n}{2}}{m}\) (labelled) graphs with \(m\) edges on \(n\) vertices, the probability of choosing a specific graph is \(1/\binom{\binom{n}{2}}{m}.\)

Probability can be applied to graph theory in some very powerful ways, and Paul Erdős was a pioneer in much of this work. In addition to studying random graphs, one of the techniques he applied with great success was non-constructive probabilistic proofs. That sounds big and complicated, but it's actually a bit like something we saw with the Pigeonhole Principle: it's possible to prove that something exists, without being able to find it.

In the case of probabilistic proofs, the basic idea is this: if you can prove that the probability that a graph has a particular property is not \(0\text{,}\) then a graph with that property must exist! Such a proof is “non-constructive” as it does not construct (or tell us how to construct) a graph that has the property.

Although our attention in this course is restricted to finite graphs, random graphs are particularly interesting in the infinite case. If our vertex set is countably infinite and we apply the Gilbert random graph model with any allowed choice of \(p\) (so \(p\) is not \(0\) or \(1\text{,}\) but can be anything in between), then almost certainly the result we obtain will be isomorphic to a specific graph. (“Almost certainly” has a very precise meaning in this context, that boils down to the probability of its occurrence being \(1\text{.}\) In practice this may mean something like the probability of its happening being the limit as \(k\) tends to infinity of \(1-p^k\text{.}\))

The infinite random graph that almost certainly arises from this process is known as the Rado graph, named for Richard Rado (1906—1989), but it also often just called the random graph, due to its omnipresence. It has many very interesting properties. Perhaps some of the most interesting are that:

• every finite graph appears as an induced subgraph of the random graph.
• given any sets \(v_1, \ldots, v_n\) and \(u_1, \ldots, u_m\) of vertices in the random graph, it is possible to find a vertex \(x\) that is adjacent to all of the vertices \(v_1, \ldots, v_n\) and not adjacent to any of the vertices \(u_1, \ldots, u_m\text{.}\)

If we allow an uncountably infinite number of vertices, then in contrast to the countable situation, there are many nonisomorphic random graphs.

Despite the apparent universality of the Rado graph, other random graphs on countably infinite sets of vertices can almost certainly arise if other random models are used. In particular, in a \(2011\) paper, Anthony Bonato (1971—) and Jeannette Janssen (1963—) studied random graphs whose vertices correspond to a dense but countably infinite subset of the real numbers, with one additional condition on the vertex set that is not particularly restrictive, but is too technical to include in this overview. In their model, they fix a distance \(D\) and a probability \(p\) (with \(0 < p< 1\)). For any two vertices \(x\) and \(y\) with \(|x-y| < D\text{,}\) the edge \(xy\) occurs with probability \(p\) (so there are no edges between vertices that are too far apart). Under this model, they were able to show that a specific graph (up to isomorphism) is almost certainly the outcome. However, this graph is easily seen to be distinct from the random graph, since in the random graph any two nonadjacent vertices have a mutual neighbour, whereas in this graph there are vertices that are not joined by a path of length \(n\) for any finite \(n\text{.}\)

In fact, Bonato and Janssen showed that a similar result holds if the vertices are chosen to be dense countably infinite subsets of \(\mathbb R^n\text{,}\) as long as the probability of two vertices being adjacent is determined by their maximum difference in any coordinate (that is, for vertices

we only use our probability to assign an edge if \(|u_i-v_i| < D\) for every \(1 \le i \le n\)). Under this model, for any fixed dimension we again obtain a unique graph (up to isomorphism) that depends only on our choice of the dimension \(n\text{.}\) In contrast, they show that if we decide whether or not to use probability to determine the existence of an edge on the basis of the usual Euclidean distance between the corresponding vertices (instead of by the maximum difference in any coordinate) then even in \(\mathbb R^2\) more than one graph may be obtained.