# The Not-Very-Random-At-All Graph

This is a guest post by Gabriel Gendler. As such, any views expressed in this post do not reflect the views of Complex Projective 4-Space or of Adam P. Goucher.

In a recent post Adam P. Goucher recommended that readers adopt the Petersen graph as their favourite graph, if they had not chosen one already. This post is designed to promote an alternative favourite graph – the Rado graph.

## Definition

We start with the following, seemingly tame, definition. Define the countably infinite graph $R$ with vertex set $V(R) = v_0, v_1, v_2 \ldots$; the edge set is $E(R)$, and for $i if and only if in the binary expansion of $j$, the digit $i$ from the right is 1. So, for example, $v_0 \sim v_k$ for odd $k$ and $v_1 \sim v_k$ for $k \equiv 2$ or $3 \pmod 4$.

## The extension property

First, we observe a useful but not immediately interesting property: for any finite disjoint sets of vertices $V, W \in V(R)$, there exists a vertex $x \notin V \bigcup W$ such that $x \sim v \forall v \in V$ and $\nexists w \in W$ with $x \sim w$. The proof is constructive: let $x = v_t$ where $t = k \cdot 2^j + \sum_{v_i \in V} 2^i$ for $k$ and large enough $j$ both in $\mathbb{N}$.

## Induced subgraphs

Now we get our first impressive result. Every graph $G$ with $V(G)$ countable is an induced subgraph of $R$. For, supposing the vertices of $G$ are labelled $g_0, g_1, g_2 \ldots$, we require an injective function $f: V(G) \mapsto V(R)$ with $g_i \sim g_j \iff f(g_i) \sim f(g_j)$. Let $f(g_0) = v_0$ as a base case, with the inductive hypothesis that $f$ defined on $g_0 \ldots g_n$ obeys the rule. Then for the inductive step we can find $f(g_{n+1}) \in R$ adjacent to precisely the correct vertices due to the extension property.

## Uniqueness

Next things start to get weird, because it turns out that all countable graphs with the extension property are isomorphic. We will prove this by letting $R$ and $S$ be two rival countable graphs with the extension property, and finding $f$ an isomorphism between them. We label the vertices of $R$ and $S$ in the normal way and let $f(r_0) = s_0$. Then supposing inductively that $f$ is legal and defined on $r_0 \ldots r_n$, and $f^{-1}$ is defined on $s_0 \ldots s_n$, we set values for $f(r_{n+1})$ and $f^{-1}(s_{n+1})$ using the extension property if they haven’t already been set. Hence $R \cong S$. We can also start with an isomorphism between any two induced subgraphs of $R$ and build up the full isomorphism from there, so we find that the graph is symmetric and ultrahomogeneous.

That was quite momentous. You may have seen it coming, but just like global warming that doesn’t stop this from being a big deal. As a consequence the weirdness becomes endemic.

## Damaging the graph

Suppose $R'$ is obtained from $R$ by deleting finitely many vertices and adding or deleting finitely many edges. Then $R \cong R'$. This is a corollary of uniqueness; it is very easy to show that $R'$ has the extension property (notice that in the proof of the extension property $k$ can be any integer so there are infinitely many legal $x$).

That’s really weird. If the graph is subjected to GBH (or indeed initiated into a Cambridge drinking society) it retains its shape.

## Tearing the graph into pieces

Equally weird is the following: If $V(R)$ is partitioned into finitely many subsets $A_1, A_2, A_3 \ldots$ then at least one of the corresponding induced subgraphs is isomorphic to $R$. This follows immediately from the case of a partition into two sets. For sets $A$ and $B$, suppose $A$ is not the Rado Graph. Then there are subsets $V_1, W_1 \subset A$ such that every $x$ extending $V_1, W_1$ is in $B$. Now for any subsets $V_2, W_2 \subset B$, there is an $x$ that extends $V_1 \bigcup V_2, W_1 \bigcup W_2$, and $x \in B$, so $B$ has the extension property. Hence either $A$ or $B \cong R$, so in the general case, for some $k$, $A_k \cong R$.

Similarly, if the edges are $k$-coloured for finite $k$, then there exists an induced subgraph which is a 2-coloured Rado graph. The proof of this makes up the better part of a paper by Sauer and Pouzet which costs £30, so I won’t reproduce it here. However I will point out that this only needs to be proved for $k=3$ for the same reason as above.

## The Random Graph

Perhaps you’re sufficiently weirded out already. Perhaps you’ve found all the weirdness so far rather run-of-the-mill. Either way, I think you’ll agree that the next realisation is about as weird as they come.

We start with an empty, countably infinite graph. We pick any $0 < p < 1$ and we go through each pair of vertices, constructing an edge between them with probability $p$. The graph we get, independent of $p$, is almost always (i.e. with probability 1) the Rado graph. This is actually easy to prove, using extension and uniqueness; for any set of vertices $V$ and $W$, and some vertex $x$ not in $V$ or $W$, the probability that $x \sim v \forall v \in V$ but $\nexists w \in W$ with $x \sim w$ is positive, so taken over all possible $x$ it is true with probability 1. Since $U$ and $V$ are finite, the number of pairs of subsets is countable, and the intersection of countably many events each with probability 1 is 1, as required.

At this point, the weirdness is so intense that it threatens to destroy the universe as we know it. Things fall apart at the seams. It turns out that the moon is made of cheese; China withdraws unilaterally from Tibet and voluntarily cedes all authority to Taipei. The Israeli government and the Palestinian Authority sign a peace treaty implementing a one-state solution, and the new country is known as the Federal Republic of Integral Bananas. Americans vote unilaterally to ban the ownership of firearms in a referendum, and scientists discover a cure for cancer whose active ingredient is powdered chocolate. Finally, every member of the IMO team gives up maths and enrols at Oxford for an undergraduate degree in History of Art. Why? Because the random graph on $\aleph_0$ vertices is in fact the not-very-random-at-all graph.

## Alternative Constructions

Now that the Rado graph has ripped the universe apart it can sit back and just show off for a bit. Here are two alternative constructions of $R$; both can be verified using the extension property and are set as an exercise for the reader.
1. Let the vertex set be all primes $p \equiv 1 \pmod 4$. Put $p \sim q \iff \left(\frac{p}{q}\right) = 1$. To verify this you need to understand the basics of quadratic reciprocity and Dirichlet’s theorem.
2. Let $S \subset \mathbb{N}$ be universal; that is, writing $S$ as a string of 0s and 1s in the natural way, every finite string of 0s and 1s can be found in $S$. Then let the vertex set be $\mathbb{Z}$ and put $a \sim b \iff |a-b| \in S$. This one can be proved without any further knowledge.

Everything we’ve seen has been quite easy to prove. That’s what I like about the Rado graph; the definition is such that everything else just falls into place. To convince yourself of this, why not find a few simple properties of the Rado graph, such as its chromatic number, its diameter and its complement? Does there exist a Hamiltonian path through every vertex? In a cops and robbers game where the robber takes it in turns with n cops to move to an adjacent vertex (all the cops move at once), who wins? Everything seems to come straight out of the definition of the Rado graph.

A favourite graph is most useful for testing hypotheses. As such, the Rado graph is an excellent choice of favourite graph because of three features that make it a good candidate for answering hypotheses in the negative. These are:
• It is easy to work with. The immense symmetry, the extension property, the subgraph property and the uniqueness of the Rado graph make it very easy to prove things about it. Therefore it will ordinarily be easy to check whether a hypothesis is true for the Rado graph (see previous paragraph).
• It has strange properties. This makes it feasible that the Rado graph should provide a much better answer to a problem than any other graph.
• It is unusual. Suppose you were to bump into your friends as they struggle to prove or disprove some graph-theoretic hypothesis, and the Rado graph provides a counterexample. You can look forward to several minutes of sincere respect for such an elegant yet obscure solution. On the other hand, if your favourite graph is the complete graph on three vertices, and that provides a counterexample, then it’s probable that your friends will already have answered their hypothesis by the time you arrive. Moreover, if you are in time to use $K3$ as a counterexample, your solution will be met not with awe or respect, but with disappointment and embarrassment. The same goes for any exams; if a well-known counterexample exists, the hypothesis is unlikely to be set as a question, whereas it’s not unlikely that the Rado graph should provide a counterexample.

## “But I’ve already got a favourite graph!”

### Sources

http://www.math.unt.edu/~mpc0061/logicgroup/randomgraph.pdf
http://mabit.org.hu/~p_erdos/1963-04.pdf
This entry was posted in Uncategorized. Bookmark the permalink.

### 10 Responses to The Not-Very-Random-At-All Graph

1. Andrew Carlotti says:

Gabriel, what am I supposed to do if the problem concerns finite graphs only?

• ggendler says:

Of course, I can’t answer your second question. Regarding your first, I suppose that will always be a problem; for example, if your favourite graph is the Petersen graph you will be disappointed if the question is about planar graphs. No graph can possibly be applicable in every situation.

• apgoucher says:

I, however, can answer your second question: yes, and it was by Bryn Garrod. I think that Gabriel’s article has more detail, though, about the Rado graph; Garrod’s talk also alluded to the fact that there are lots of uncountable random graphs.

Also, I agree that no graph is applicable to all situations. Most of the false solutions in the FST 2013 graph theory question made erroneous assumptions about planar graphs, which fail for the octahedral graph and (even more spectacularly) fail for the icosahedral graph.

2. apgoucher says:

Great article, Gabriel!

By the way, my condolences go out to those people whose favourite graph is the 57-regular Moore graph, not knowing whether or not it actually exists.

• Maria says:

I second your opinion on the article. 🙂

Aren’t you just sending out condolences to yourself here though…?

• apgoucher says:

No, my favourite is the Petersen graph, as I alluded to in the article about the Hoffman-Singleton graph.

• Maria says: