Visualizing the Henson graph
When visualizing finite graphs, you can simply draw the whole graph. But that doesn’t really work for infinite graphs. What you need to visualize is not so much the graph itself, but the rule by which it is constructed.
If the graph is periodic, such as an infinite grid graph, this distinction may not matter so much: drawing a large enough fragment of the graph makes it obvious how the rest of the graph was constructed. But for a graph like the Rado graph, that doesn’t work. Every finite graph is an induced subgraph of the Rado graph, so you can draw any graph and say that it’s part of the Rado graph. Because it can be anything, such a drawing is uninformative: it tells you nothing about what the rest of the graph looks like. No understanding of the Rado graph is needed to be able to distinguish valid drawings of fragments of the Rado graph (all drawings of finite graphs) from invalid drawings (nothing).
It was for this reason that when I drew the image below in 2009, as an illustration of the Rado graph, what I was really trying to illustrate was one of the standard constructions of the Rado graph, where the vertices are assigned binary numbers and adjacency is determined by an undirected version of the BIT predicate, which tests whether the larger of two given numbers has a one in the position of its binary representation indexed by the smaller of the two numbers.
For the Henson graph, the universal triangle-free graph, that numbering does not work, so we need a different visualization. The Henson graph can be constructed by deleting some of the vertices from the Rado graph, but with a special ordering of the Rado graph. The property the ordering needs to have is: for every finite set \(S\) of vertices, there are infinitely many vertices in the graph that have \(S\) as their set of earlier neighbors. This doesn’t work for the BIT predicate ordering, because in that order there is exactly one vertex that has each finite set of earlier neighbors, not infinitely many. But this special ordering does exist for the Rado graph (and only for the Rado graph). With this special ordering, the construction of the Henson graph is: delete each vertex that is the last of three vertices in a triangle.
But that is not an explicit construction and not something that can be visualized. It does not work to draw a finite fragment of a special ordering of the Rado graph, because every ordering of every finite graph could be such a fragment. Because it could be anything, again, such a drawing tells you nothing.
Instead, here’s an explicit construction that does work: construct the graph in a sequence of layers. In each layer, if there are \(k\) vertices already drawn in previous layers, construct the layer as an independent set of \(2^k\) new vertices, each adjacent to one of the \(2^k\) possible subsets of the previous vertices. Thus, the first layer has one vertex (the only subset of the empty set of previous vertices is the empty set), the next layer has two vertices (the empty set again and the singleton vertex in the first layer), etc. Every finite set of vertices is repeated infinitely many times, once in each layer after the layers containing the vertices in the set. Because the graph has the desired property of having infinitely many vertices whose earlier neighbors are any finite set, it is the Rado graph.
Now, delete all vertices that form the third vertex of a triangle. The triangles are aci and ack, so delete i and k. The result is the Henson graph \(G_3\). (The same construction can be performed with other subscripts, blocking larger cliques but not triangles, but we’ll stick to the triangle-free version of this construction.)
The deleted vertices are exactly the ones whose earlier neighbors include two adjacent vertices, so that they form a triangle. Equivalently, the vertices that were not deleted are the ones whose earlier neighbors form an independent set. By visualizing the graph in this way, we are led to both an explicit construction of the Henson graph that does not involve deletion, and a more general description of the vertex orders that produce this graph: we want an ordered graph such that each vertex has an independent set of neighbors, and such that for each finite independent set \(S\), there are infinitely many vertices that have \(S\) as their set of earlier neighbors. We can construct such a graph in a sequence of layers, where there is one vertex in each layer for each independent set of vertices from earlier layers.
One drawback of this construction is that the layers grow very quickly. Even in the independent set version, layer \(i\) contains a number of vertices whose size grows like a tower of powers of two. That sets up a delicate balance in visualization between choosing enough layers to make the construction clear and not choosing so many that the drawing becomes too cluttered with far too many vertices. This fast growth is related to an earlier post here on efficiency of Rado graph representations: these layered constructions are very inefficient in the sense discussed there. There’s a similar-looking layered construction of (finite) all-but-clique-universal graphs with only single-exponential growth in my paper “Quasipolynomiality of the smallest missing induced subgraph” but unfortunately it doesn’t work for the Rado and Henson graphs: its treatment of all vertices in one layer as equivalent in subsequent layers prevents it from having the required extension properties. Instead, we could limit the growth to a lower asymptotic rate by only allowing sets of size \(\le i\) in layer \(i\), but for the visualizations shown here that wouldn’t change much: only k would be missing from the Rado graph drawing, and I think the result would be more confusing.