In this post, I will consider Henson’s graphs as Cayley graphs.
Henson’s graphs
Recall from the first post of the series the conditions for a class of finite relational structures to be a Fraïssé class, that is, the class of finite structures embeddable in a countable homogeneous structure.
Let C_{n} be the class of finite graphs not containing the complete graph K_{n} on n vertices as an induced subgraph. It is easy to see that C_{n} is a Fraïssé class: it is closed under isomorphism and under taking induced subgraphs, and contains only countably many different graphs; and for the joint embedding and amalgamation properties, we combine two graphs by including no edges which are not present in the original graphs, so that no complete graph can be formed which was not already there.
Hence there is a unique (up to isomorphism) countable homogeneous graph H_{n} whose age is C_{n}; that is, H_{n} contains no K_{n} but contains every finite K_{n}-free graph.
The graphs H_{n} are Henson’s graphs.
The graph H_{n} is recognised by the property that, if U and V are finite disjoint sets of vertices, where U contains no complete graph of size n−1, then there is a vertex z joined to everything in U and to nothing in V.
The theorem of Lachlan and Woodrow asserts that, apart from “trivial examples” (the disjoint union of complete graphs of the same size, and its complement), the only countable homogeneous graphs are Henson’s graph, its complement, and the random graph.
Henson showed that H_{3} is a Cayley graph for the infinite cyclic group, but that H_{n} is not if n>3. This hints at a fundamental difference between H_{3} and the others.
H_{3} as a Cayley graph
For H_{3}, we can follow the approach we used for the random graph. There is a condition on a countable group X which is sufficient for H_{3} to be a Cayley graph for X. It is a bit more restrictive than the analogous condition for R: it asserts that X should not be the disjoint union of certain sets together with a finite set. The sets required in the condition are
- S(a,b), the set of elements x satisfying a^{−1}xb^{−1}x = 1 with a ≠ b (this is a translate of a non-principal square-root set);
- S(a,b,c), the set of elements x satisfying a^{−1}xb^{−1}xc^{−1}x = 1;
- C(a,b), the set of elements conjugating a to b.
If X is abelian, we can assume that the third type does not occur.
Let us look more closely at the case when X is the infinite cyclic group Z. In this case, the connection set is S∪(−S), where the set S consists of positive integers. The Cayley graph Cay(Z,S∪(−S)) is triangle-free if and only if S is sum-free, that is, does not contain two numbers and their sum. (For x,y,z∈S with z = x+y would give rise to a triangle {0,x,z} in the Cayley graph. This fact explains my interest in random sum-free sets (of which more elsewhere).
Other Henson graphs
Problem: Is H_{n} ever a Cayley graph for n > 3?
The best I can do is the following. I defined a Cayley graph to have edges from x to sx, where s belongs to the connection set; this makes the graph invariant under right translation by group elements. (It should be noted that some authors reverse the order, so that the graph is invariant under left translation.)
A Cayley graph Cay(G,S) is said to be normal if it is invariant under both right and left translation. Equivalently, the Cayley graph is normal if the connection set is a normal subset of G (in the sense that g^{−1}Sg = S for all elements g.
Theorem: For n > 3, the graph H_{n} is not a normal Cayley graph. In particular, it is not a Cayley graph for any countable abelian group.
The proof is a simple modification of Henson’s. Suppose that S is a normal subset of G and that Cay(G,S) is isomorphic to H_{n}, with n > 3. Choose g_{1},…g_{n−2} inducing a complete graph. Then choose h∈G joined to the identity but not to any g_{i}^{−1}g_{j} for i ≠ j. Then the set of elements g_{i} and g_{i}h carries a subgraph containing no complete graph of size n−1 (it consists of two complete graphs of size n−2 with a 1-factor joining them. So there is a vertex k joined to everything in this set.
Then it is routine to show that the n vertices 1, h, g_{1}^{−1}k, g_{n−2}^{−1}k carry a complete graph (using the assumed normality of S).