The countable random graph

Flip a coin to determine the edge relations between vertices in a countably infinite set. The result is a random graph, yet almost surely it is exactly the same up to isomorphism every time.

A graph is a relational structure ⟨V, ~ ⟩ consisting of a set V of objects called vertices together with a symmetric irreflexive relation ~ on that set, called the edge relation.

One can conceive of a graph as a collection of dots with the edges drawn connecting them, as shown in the instance here. The concept of a directed graph drops the symmetry requirement on the edge relation.

Graph theory is a huge and fascinating subject, containing many beautiful theorems, and there are many elementary accounts of it, such as my brief introduction to the subject in my book, Proof and the Art of Mathematics. In this text, therefore, let me not reproduce that introduction, but rather touch upon just one theme in graph theory that happens to illustrate several central model-theoretic concepts.

Let me also mention that there are several distinct notions of graph in mathematics, even within the subject of graph theory. Sometimes, for example, mathematicians want to allow instances of reflexivity into their graphs, so that a vertex a could have an edge to itself, and sometimes they also want to allow multiple edges from a to b, which means that edges are treated as objects rather than as relation instances. In these more general contexts, the graphs I have defined here are called simple graphs. When the focus is solely on simple graphs, however, then it is common practice just to call them graphs as I have done.

The topic I should like to discuss here is the countable random graph, a certain countable graph that gets its name on account of a fascinating mathematical fact. Namely, give yourself countably many nodes and then for every possible edge between any two of them, flip a coin to determine whether the edge is present or absent—you will thereby produce a random graph of some kind, in all likelihood it exhibits some diverse complicated patterns of connectivity. The amazing fact, however, is that almost surely, that is, with probability one, you will get exactly the same graph up to isomorphism every time. It is amazing.

Let me convince you of this.