Homogeneous Cayley objects, 1

I have a few things to say about this topic. Mainly these are open problems. I plan to start with an introduction, and then talk about the random graph, the Henson graphs, and n-tuples of total orders, and the problems they pose.

Regular action and Cayley objects

The term group has three different meanings:

  • A group, or abstract group is a set G with a binary operation • satisfying the associative law x•(yz) = (xy)•z, having an identity element 1 satisfying x•1 = 1•x = x, and such that every element x has an inverse x−1 satisfying xx−1 = x−1 = 1. As usual, we normally write the operation as juxtaposition, that is, xy instead of xy.
  • A permutation group, or transformation group, is a set G of permutations of a set X which is closed under composition, contains the identity permutation, and contains the inverse permutation of each of its elements.
  • A symmetry group, or automorphism group, is the set of all permutations of a set X which are isomorphisms of a structure M on X. (The structure can be combinatorial, algebraic, geometric, or topological; an isomorphism is a structure-preserving map whose inverse is also structure-preserving.)

A little thought shows that every symmetry group is a permutation group (the composition of isomorphisms is an isomorphism, and the identity map is an isomorphism of any structure). Also, a permutation group is an abstract group. (Composition of maps is always associative; and although the words “identity” and “inverse” have completely different meanings in the two contexts, it is easy to see that the identity and inverse maps satisfy the requirements for an abstract group.)

The converse implications also hold:

  • Cayley’s Theorem states that every abstract group is isomorphic to a permutation group. For let G be an abstract group. We take the set X to be G itself; for each gG, we take the map πg on G defined by xπg = xg. It follows from the associative law that πgh = πgπh, and it easily follows that the map g→πg is an isomorphism from G to a permutation group on G. This is the regular representation of G.
  • The difficulty in showing that every permutation group is a symmetry group is in choosing the right structure to use. Rather than do this in general, I will explain it just for the regular representation. Let G be a group. For each non-identity element g in G, take a colour c(g). Now form a coloured directed graph on G, with a directed edge of colour g from x to gx, for each x and each non-identity g in G. It is not hard to show that the automorphism group of this Cayley coloured digraph is precisely the regular representation of G.

This has led to several areas of investigation. One is to hold on to the condition that the automorphism group of the structure is precisely the regular representation of G, but to remove the colours and directions from the graph. A graphical regular representation or GRR of a group G is an (undirected) graph on G whose automorphism group is precisely the regular representation og G. A lot of work culminated in the theorem of Chris Godsil that any finite group, except for abelian groups of exponent greater than 2, generalised dicyclic groups, and finitely many more (an explicit list), has a GRR.

Subseequently Laszlo Babai conjectured that, excepting (as we must) the abelian and generalised dicyclic groups, a random G-invariant graph (for the regular representation of a finite group G) is a GRR for G with high probability. This has been proved for some classes of groups. I will say more about this below.

Another line relaxes the condition that the automorphism group of the graph is precisely G. A Cayley graph for G is a graph X on the vertex set G which is invariant under the regular representation of G. It is easily seen that any Cayley graph for G is obtained as follows: Choose a subset S of G with the properties

  • 1∉S;
  • if sS, then s−1S.

Now the edges of the graph are of the form {x,sx}, for sS and xG. This graph is denoted by Cay(G,S).


  • The condition 1∉S ensures that the graph has no loops, and the symmetry condition ensures that the graph is undirected.
  • The graph is connected if and only if S generates G. (Some researchers assume this condition; I will not do so.)
  • Now we can easily define a random Cayley graph for a group G: choose inverse pairs of non-identity elements independently with probability 1/2, and let S be their union. Babai’s conjecture says that, with the exceptions noted earlier, a random Cayley graph for a finite group G has automorphism group precisely G with high probability.

This can now be generalised. A Cayley object for G is an structure on the set G whose automorphism group contains the regular representation of G. Now we can examine Cayley graphs, digraphs, orders, metric spaces, etc.

Homogeneous structures

I will restrict myself to relational structures: such a structure on a set is just a family of relations (or arbitrary arity) on the set. This class is rich enough to include all the examples above. (For metric spaces, for example, take one binary relation ρr for each non-negative real number r; this relation holds between x and y if the distance between x and y is r.

Given a relational structure M, any subset of the underlying set carries an induced substructure, having all instances of the relations for which all arguments lie in the subset. The age of M is the class of all finite structures which are isomorphic to induced substructures of M.

A class of finite structures is the age of a relational structure if and only if it is closed under isomorphism, closed under taking (induced) substructures, and has the joint embedding property: for any two structures A and B in the class, there is a structure C in the class in which both can be embedded. If we add the condition that the class contains (at most) countably many structures up to isomorphism, then we have characterised ages of countable structures.

A structure M is homogeneous if any isomorphism between finite substructures of M can be extended to an automorphism of M. This is the strongest symmetry condition we can reasonably ask of a structure.

Fraïssé’s Theorem asserts that a class of finite structures is the age of a countable homogeneous structure if it has the properties listed above for the age of a countable structure, together with the amalgamation property: given two structures B and C in the class, and an isomorphism f from a substructure A of B into a substructure of C, there is a structure D with embeddings of B and C into D which “agree” on A (that is, an element of A and its image under f are identified). In other wordsd, we can take B and C and “glue them together” along A inside a structure in the class.

Moreover, if these conditions are satisfied, then there is a unique homogeneous structure (up to isomorphism) with the given class as its age. Such a class is called a Fraïssé class, and the countable homogeneous structure is its Fraïssé limit.


  • The Fraïssé limit of the class of all finite graphs is the random graph.
  • The Fraïssé limit of the class of all finite totally ordered sets is the ordered set of rational numbers.

Homogeneous Cayley objects

I will discuss some of these countable homogeneous structures in the rest of this sequence. The main question is:

Given a countable homogeneous structure M, for which groups G is M a Cayley object for G?

It turns out that this phenomenon is quite common, but there are no non-trivial cases where the complete answer is known, and the question throws up some interesting questions.



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 )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s