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 2^s for s∈S. 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 H_n 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 K_n. 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 H₃ 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 H₃: 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 …