## 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/.)

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in grad school, humor and tagged , , . Bookmark the permalink.

### 3 Responses to The random graph

1. Mark Dominus says:

Excellent. Thanks for this post!

This reminds me of a paper of Janós Pach about “universal” graphs. It is quite easy to produce a countable graph G that has the property that for every finite or countable graph H, H is an induced subgraph of G. The graph that Pach constructed was not the Rado graph, although it seems to me that the Rado graph also has this property.

But Pach showed that there is no graph G that contains every graph H other than Kω, the complete graph on infinitely many vertices. (The proof is pretty easy.) But if I am right about the Rado graph being universal in the sense of the previous paragraph, then by this theorem it must contain a Kω.

Hm, yes, it does. It follows immediately from the extension property, and in the Wikipedia notation of http://en.wikipedia.org/wiki/Rado_graph, the vertices at http://www.research.att.com/~njas/sequences/index.html?q=0,1,3,11,205 form a Kω.

Sorry, just thinking aloud. Thanks again!

2. Mark Dominus says:

P.S. misspelled “János”.