Puzzle solution

Thank you, Honza, spot on.

In 1964, Richard Rado published a construction of a universal graph, a countable graph which embeds every finite or countable graph as an induced subgraph. His graph turns out to be an explicit example of the Erdős–Rényi “random graph”.

The construction goes like this. (Here we are being logicians, so 0 is a natural number.) Any finite subset S of the natural numbers can be represented as a single number, the sum of the powers 2s for sS. To reverse the construction, take a number n, write it in base 2 (as a sum of powers of 2), and take the set of exponents which occur. (In this way the natural numbers form a model for hereditarily finite set theory, that is, Zermelo–Fraenkel set theory with the negation of the axiom of infinity, so that all sets are finite.

Let S(n) be the finite set corresponding to the number n.

Now the construction of the graph goes like this. Take two numbers n and m. One is smaller than the other; without loss, m < n. Now we join m to n if (and only if) m belongs to the set S(n).

What do we learn from this representation? Maybe not much, since the graph is most usually recognised by its properties. But here is one thing we learn. The graph is homogeneous, that is, any isomorphism between finite subgraphs extends to an automorphism of the graph. Using Rado’s representation, we see that the automorphism can be chosen to be a primitive recursive function (though, unfortunately, this does not mean that there is a simple representation for it: if you think it should, try to find a simple representation for an automorphism which interchanges vertices 0 and 1.)

In 1971, Ward Henson constructed a family of graphs with similar properties. The Henson graph Hn has the properties that it is homogeneous, it contains no copy of the complete graph on n vertices, and it is universal for finite or countable graphs containing no Kn. Later, Lachlan and Woodrow showed that, up to complementation, these graphs and Rado’s are the only “non-trivial” countable homogeneous graphs.

For simplicity I will stick to the case n = 3 here.

Henson found H3 inside Rado’s graph R, by a simple construction. Consider the set of natural numbers n such that n is not the largest vertex of a triangle in R. This is done by taking the natural numbers in turn, and including n in our set if and only if S(n) contains no edge of the graph; that is, for no i and j in S(n) does it happen that i is in S(j). Thus, the vertex set can be found iteratively; this is the set which was given in the puzzle.

Now this is a simple enough construction. If we had a simple formula for the vertex set, then we would have a simple explicit presentation of H3: the vertices would be given by the formula, and the edges would be defined exactly as in Rado’s graph.

But a simple formula of this sort is still lacking …

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , , . Bookmark the permalink.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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

This site uses Akismet to reduce spam. Learn how your comment data is processed.