Homogeneous Cayley objects, 3

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 Cn be the class of finite graphs not containing the complete graph Kn on n vertices as an induced subgraph. It is easy to see that Cn 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 Hn whose age is Cn; that is, Hn contains no Kn but contains every finite Kn-free graph.

The graphs Hn are Henson’s graphs.

The graph Hn 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 H3 is a Cayley graph for the infinite cyclic group, but that Hn is not if n>3. This hints at a fundamental difference between H3 and the others.

H3 as a Cayley graph

For H3, we can follow the approach we used for the random graph. There is a condition on a countable group X which is sufficient for H3 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−1xb−1x = 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−1xb−1xc−1x = 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,zS 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 Hn 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−1Sg = S for all elements g.

Theorem: For n > 3, the graph Hn 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 Hn, with n > 3. Choose g1,…gn−2 inducing a complete graph. Then choose hG joined to the identity but not to any gi−1gj for i ≠ j. Then the set of elements gi and gih 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, g1−1k, gn−2−1k carry a complete graph (using the assumed normality of S).

Previous | Next

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 )

Google photo

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