In our previous post, we provided a literary prologue to the study of universal structures, objects that, in a sense, “contain” all other objects of the same type. Today, we return to the world of mathematics to look at a fascinating concrete example of such a universal structure.

The mathematical objects we will be working with are graphs, which we briefly introduced in our Ultrafilters series. Recall that a graph is a set of vertices and a set of edges, where each edge connects two distinct vertices. For example:


A graph G is often represented as a pair (V,E), where V is the set of vertices and E is the set of edges. An edge is represented by a set containing the two vertices it connects. If G_1 = (V_1, E_1) and G_2 = (V_2, E_2) are two graphs, then we say that G_1 embeds into G_2 if there is a function f:V_1 \rightarrow V_2 such that:

  • for all u,v \in V_1, if u \neq v, then f(u) \neq f(v);
  • for all u,v \in V_1, if \{u,v\} \in E_1, then \{f(u), f(v)\} \in E_2;
  • for all u,v \in V_1, if \{f(u), f(v)\} \in E_2, then \{u,v\} \in E_1;

One can think of the statement “G_1 embeds into G_2” as saying that “G_2 contains a copy of G_1.” To really understand this idea, try the following exercise.

Exercise: Every graph with three vertices embeds into the graph pictured above.

In light of this exercise, we might be tempted to say that the graph we have drawn above is universal for graphs with three vertices. However, we are cheating a little bit, since our graph has more than three vertices itself. We would really like for a universal object to itself be a member of the class for which it is universal; otherwise, finding universal objects is too easy! A bit of thought should convince you that, with this more stringent definition of “universal,” no graph that is universal for a meaningful class of graphs can be finite (the word “meaningful” here is just meant to rule out whatever trivial examples you can think of).

We therefore will waste no time trying to find finite universal graphs and will instead move on to the next step: graphs with a countable infinity of vertices. And here we will succeed: we will find a graph G with countably many vertices such that, for every graph H with countably many vertices, H embeds into G. What’s more, we will succeed with a wonderfully interesting graph: the random graph.

One commonly cited criterion for an idea or an object to possess mathematical beauty is that it arise independently in a variety of different contexts, in a variety of guises that are only revealed to be identical upon close inspection. By this accounting, I would say that the random graph is quite beautiful indeed. Let us give just a few descriptions of this graph.

1: Hereditarily finite setsFor a set x, the transitive closure of x is, roughly, the set consisting of all elements of x, all elements of elements of x, all elements of elements of elements of x, and so on. It is quite possible that a set x is finite but its transitive closure is infinite (consider, for example, the set whose one element is the set of all natural numbers). A set is called hereditarily finite if its transitive closure is finite. Assuming that all sets are built up from the empty set, one can prove that there are only countably many hereditarily finite sets. Moreover, if n is a natural numbers and x_1, x_2, \ldots, x_n are hereditarily finite sets, then \{x_1, x_2, \ldots, x_n\} is a hereditarily finite set. Now form a graph G = (V,E) by letting V be the set of all hereditarily finite sets and, for all x,y \in V, letting \{x,y\} \in E if and only if either x \in y or y \in x.

2: Binary expansion. We typically write natural numbers in base 10, or decimal, notation, but one could just as well write them in base 2, or binary, notation, using only 0s and 1s. I will assume the reader is at least passingly familiar with this. As a brief refresher, recall that, in binary notation, 1 is 1, 2 is 10, 3 is 11, 4 is 100, 5 is 101, and so on. We define a graph G = (V,E) such that V is the set of natural numbers. If m < n are natural numbers, then we put an edge between m and n if and only if the m^{\mathrm{th}} digit (from the right, starting with 0) in the binary expansion of n is 1. For example, the number 10 in binary is 1010. Therefore, there is no edge between 0 and 10 or 2 and 10 but there is an edge between 1 and 10 and between 3 and 10. If 4 \leq m < 10, then there is no edge between m and 10 because the binary expansion of 10 only has 4 digits.

The first nine vertices of the binary expansion graph. Illustration by David Eppstein.

3: Coin flipping. We will define a graph G = (V,E) probabilistically, where V is the set of natural numbers. For each pair of natural numbers m < n, we will flip a fair coin. If the coin lands heads, we put an edge between m and n. If it lands tails, we do not put an edge between m and n.

4: Quadratic residues. If p and q are natural numbers, we say that p is a quadratic residue modulo q if there is a natural number x such that x^2 - p is divisible by q. We define a graph G = (V,E) such that V is the set of all prime numbers that leave a remainder of 1 when divided by 4. It is an elementary fact of number theory that there are infinitely many such prime numbers. If p < q are two elements of V, then we put an edge between p and q if and only if p is a quadratic residue modulo q or q is a quadratic residue modulo p.

5: Fraïssé limit. Let G be the Fraïssé limit of the class of finite graphs. I am not going to explain this further; I just wanted to use the phrase “Fraïssé limit.”

One of the almost miraculous aspects of our story is that all five of these graphs are the same, and we shall refer to all of them as “the random graph.” Before we go any further, though, I should explain what I mean by “the same,” since these graphs are not literally “the same” (some of them don’t even have the same sets of vertices). By “the same” we mean isomorphic, or “structurally the same,” in the way in which we would say that any two graphs with three vertices and edges between all three vertices are “the same.” More precisely, if G_1 = (V_1, E_1) and G_2 = (V_2, E_2) we say that G_1 and G_2 are “the same” (or isomorphic) if there is a one-to-one correspondence (i.e., a bijection) f:V_1 \rightarrow V_2 such that, for all x,y \in V_1, we have \{x,y\} \in E_1 if and only if \{f(x), f(y)\} \in E_2. The point is that the way in which we label the vertices of a graph is immaterial to the actual structural properties of the graph, which are what we care about.

Now, how can we show that all of these graphs are the same? We show that all of the graphs have a very special property, and that all countable graphs with this property are isomorphic. This property is called the extension property.

Definition: A graph G = (V,E) satisfies the extension property if, for all finite subsets U_1, U_2 \subseteq V with U_1 \cap U_2 = \emptyset, there is a vertex v \in V such that:

  • v \not\in U_1 \cup U_2;
  • for all u \in U_1, we have \{u,v\} \in E;
  • for all u \in U_2, we have \{u,v\} \not\in E.

I will leave the verification that all five of our graphs have the extension property as an exercise. For graphs 1 and 2, this is pretty easy. For graph 3, since the definition of the graph is probabilistic, it is conceivable (just ask Rosencrantz and Guildenstern) that every coin flip somehow comes up heads, in which case the graph would obviously not satisfy the extension property. However, the graph will satisfy the extension property with probability 1, so we can be almost sure. The fact that graph 4 satisfies the extension property follows from the Chinese Remainder Theorem and Dirichlet’s theorem about primes in arithmetic progressions, two somewhat non-trivial theorems from number theory.

Theorem: Suppose G_1 = (V_1, E_1) and G_2 = (V_2, E_2) are two countably infinite graphs with the extension property. Then G_1 and G_2 are isomorphic.

Proof sketch: Since G_1 and G_2 are countable, we can enumerate V_1 as \{u_0, u_1, u_2, \ldots \} and V_2 as \{v_0, v_1, v_2, \ldots \}. We will construct an isomorphism f:V_1 \rightarrow V_2 in infinitely many steps by defining f on more and more elements of V_1.

Suppose n is a natural number. We now describe Step n of the construction. Assume that we have already defined f on finitely many elements of V_1 in such a way that f is thus far an isomorphism, i.e., for all pairs u \neq v on which f is thus far defined, we have f(u) \neq f(v) and \{u,v\} \in E_1 if and only if \{f(u), f(v)\} \in E_2. Suppose moreover that, for all m < n, f is defined on u_m and there is u \in V_1 such that f is defined on u and f(u) = v_m.

We now extend f so that it is defined on u_n. If it happens to be the case that it is already defined on u_n, then we have nothing to do. Otherwise, let U be the set of vertices on which f is thus far defined. Let U_1 be the set of vertices in U to which u_n is connected by an edge, and let U_2 be the set of vertices in U to which u_n is not connected. Let W_1 = \{f(u) \mid u \in U_1\} and W_2 = \{f(u) \mid u \in U_2\}. Since G_2 satisfies the extension property, we can find v \in V_2 such that:

  • v \not\in W_1 \cup W_2;
  • for all w \in W_1, we have \{w,v\} \in E_2;
  • for all w \in W_2, we have \{w,v\} \not\in E_2.

Let f(u_n) = v. Next, we extend f so that v_n is in its image. If there is already u \in V_1 such that f(u) = v_n, then there is nothing to do. Otherwise, let W be the set of w \in V_2 such that, for some u \in V_1, we have f(u) = w. Let W_1 = \{w \in W \mid \{v_n, w\} \in E\} and W_2 = \{w \in W \mid \{v_n, w\} \not\in E\}. Let U_1 = \{u \in V_1 \mid f(u) \in W_1\} and U_2 = \{u \in V_1 \mid f(u) \in W_2\}. Since G_1 satisfies the extension property, we can find u \in V_1 such that:

  • u \not\in U_1 \cup U_2;
  • for all v \in U_1, we have \{u,v\} \in E_1;
  • for all v \in U_2, we have \{u,v\} \not\in E_1.

Let f(u) = v_n. This completes Step n of the construction. Continuing through all of the steps, one for each natural number, we find that we have constructed a full isomorphism from G_1 to G_2, thus completing the proof of the theorem.

The theorem shows that we are justified in referring to the random graph rather than random graph. Up to isomorphism (and with probability 1), all of the graphs we have called “the random graph” are the same! Essentially the same proof as that given above shows that every countable graph embeds into the random graph (Exercise: Do it!). Thus, the random graph can truly be said to be universal for the class of countable graphs.

P.S. To what extent do these ideas generalize to higher infinities? Assuming some assumptions about cardinal arithmetic, they generalize quite straightforwardly. If \kappa is an infinite cardinal and \kappa^{<\kappa} = \kappa, then it is meaningful to talk about the “random graph of size \kappa,” and this graph will be universal for graphs of size \kappa. However, the assumption \kappa^{<\kappa} = \kappa is not necessarily true for uncountable cardinals. In fact, it is consistent with the axioms of set theory that there are no universal graphs of size \aleph_1. The question of the existence of universal graphs becomes especially interesting at cardinals of the form \mu^+, where \mu is a singular cardinal; much work has been done even in the last few years on this topic.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s