The random graph

Today in my finite model theory class we learned about the Rado graph, which is a graph (unique up to isomorphism among countable graphs) with the extension property: given any two disjoint finite sets of vertices \(U\) and \(V\), there exists some other vertex \(w\) which is adjacent to every vertex in \(U\) and none of the vertices in \(V\).

This graph has some rather astonishing properties. Here’s one: consider starting with \(n\) vertices and picking each edge with probability \(1/2\). Clearly, there are \(2^{\binom n 2}\) different graphs you can get, each with equal probability; this defines a uniform random distribution over simple graphs with \(n\) vertices. What if you start with a countably infinite number of vertices instead? The surprising answer is that with probability 1 you get the Rado graph. Yes indeed, the Rado graph is extremely random. It is so random that it is also called “THE random graph”.

SimpleGraph getRandomGraph()
{
    return radoGraph;  // chosen by fair coin flips.
                       // guaranteed to be random.
}

(See http://xkcd.com/221/.)