The universal countable graph

The following cute theory was mentioned yesterday briefly by Bela Bollobas in a talk at a short Probabilistic Combinatorics course in Cambridge. After a bit of reflection I have decided not to post any proofs, partly because they are reasonably easy and recommended to the reader, but mainly because most of them are based on very simple ideas that look significantly more complicated when put into text or notation, undermining the idea I want to get across that this is a nice cute little piece of graph theory.

We say that a graph has the -splitting property if its order is greater than and for any two disjoint -subsets there is some other vertex which is connected by an edge to all the vertices in , and none of the vertices in .

It turns out, perhaps surprisingly, that this fairly general sounding property gives rise to the following fairly specific sounding results:

1. If two countable graphs both have the -splitting property for all then they are isomorphic (i.e. there is only one countable graph, up to isomorphism, with this property – call it the universal countable graph).
2. A random graph on a countable infinity of vertices is isomorphic to the universal countable graph with probability 1.
3. Any countable graph is a subgraph of the universal countable graph.

I leave these all for the reader to prove. While initially surprising, this kind of result seems, with a bit of reflection, almost typical of the behaviour of a lot of countable sets with a structure. For example, one might like to apply similar methods (in fact, maybe the equivalent facts for digraphs are directly applicable) in showing that certain large classes of subsets of the rational numbers are all order isomorphic.

Advertisement