I will discuss the question
For which countable groups G is the random graph a Cayley graph for G?
But first, how do we identify a homogeneous structure when we have one?
Recognising homogeneous structures
As we saw, a countable homogeneous structure is determined up to isomorphism by its age (the class of finite substructures embeddable in it). But there may be inhomogeneous structures with the same age. There are many countable graphs which contain all finite graphs; only the random graph has this property and is homogeneous.
Let M be a relational structure. We say that M has the lifting property if, whenever A and B are structures in the age of M with A contained in B and |B| = |A|+1, any embedding of A into M can be lifted to an embedding of B.
Theorem: A countable structure is homogeneous if and only if it has the lifting property.
To prove this, suppose first that M is homogeneous and that we are given an embedding of A into M. Since B belongs to the age of M, there is also an embedding of B into M, which restricts to an embedding of A. The isomorphism between the two embedded copies of A extends (by homogeneity) to an automorphism of M; composing this with the given embedding of B, we get another embedding of B which extends the given embedding of A.
Conversely, the lifting property is exactly what we need to make the back-and-forth construction work: this construction requires isomorphisms to be extended to one additional point.
For example, let M be a countable graph whose age contains all finite graphs. The lifting property for M simply asserts that, given a finite subset of M, every possible one-point extension of it can be realised inside M. This means that, given two finite disjoint subsets U and V of M, we can find a vertex z joined to every vertex in U and to no vertex in V. This is precisely the defining property of the random graph.
The random graph as a Cayley graph
A square-root set in a group G is a set of the form
√g = {x∈G:x^{2}=g};
it is principal if g=1 and non-principal otherwise.
We will need to talk about a translate of a square-root set. It doesn’t matter whether we take a left or a right translate, since it is easily seen that h√g = √(hgh^{−1})h.
Let R denote the countable random graph. Here is the theorem I would like to prove:
Conjecture: For a countably infinite group G, the following conditions are equivalent:
- Some Cayley graph for G is isomorphic to R.
- A random Cayley graph for G is isomorphic to R with probability 1.
- G cannot be written as the union of a finite number of non-principal square-root sets and a finite set.
What I can actually prove is not as nice. The first two conditions are indeed equivalent, but the last condition is replaced by something a bit more complicated.
Before I outline the proof, a brief remark. You may be wondering why I don’t dispense with the finite set in the last condition, since a finite set can be captured by finitely many copies of any non-principal square root set. The problem is that there is one countable group (the elementary abelian 2-group) in which every non-principal square root set is empty, since the square of every element is the identity. In any case, the proof is a little smoother if we allow the finite set.
We begin by examining a Cayley graph for G. Remember that, if S is an inverse-closed subset of G not containing the identity, then Cay(G,S) has an edge from x to y if and only if y = sx for some s∈S; in other words, yx^{−1}∈S. So, if we are looking for a vertex z joined to x but not to y, then the elements z satisfying the condition zx^{−1} = yz^{−1} will be ineligible. But if this equality holds, then (zx^{−1})^{2} = yx^{−1}, so z lies in √(yx^{−1})x, a translate of a non-principal square root set. Every translate of a non-principal square root set can be represented in this form.
Now consider the following condition:
- G cannot be written as the union of a finite number of square-root sets of the form
Z(x,y) = √(yx^{−1})x,
where the finite sets of xs and ys occurring are disjoint, together with a finite set.
This is implied by the condition in the conjecture, since we are being more prescriptive about the square root sets required. The theorem asserts that this condition is equivalent to the other two statements.
Clearly the second statement in the conjecture (or theorem) implies the first (this is a non-constructive existence proof).
Suppose that the condition above fails: thus there is a finite set W such that every element of G not in W lies in one of finitely many sets Z(x,y), where the xs lie in a finite set U, and the ys lie in a finite set V, and U and V are disjoint. Our earlier argument shows that, in any Cayley graph for G, a vertex lying in Z(x,y) cannot be joined to x but not y. So the set of witnesses of the lifting property for the finite sets U and V must be contained in the finite set W. So no such graph can be the random graph, since in R the set of witnesses for any pair (U, V) is infinite.
Now suppose that this condition is true. We construct a random Cayley graph for G, by adding inverse pairs of non-identity elements randomly to the connection set S. It will be enough to show that for a given disjoint pair U, V of finite sets, the event that the pair has no witness is null, since a countable union of null sets is null. For this, we toss a fair coin in turn for each inverse pair of non-identity elements to decide its membership in S. It will suffice to show that, after any finite sequence of coin tosses, there is a continuation of the sequence which will produce a witness for U and V.
Suppose that we have decided whether to put each of a finite set T of elements into S. Then, in seeking a witness, we must exclude T, U and V, and the finitely many elements whose edges or non-edges to U and V have already been decided (that is, those of the form tx, where x is in U or V and t∈T); and also the elements in some set Z(x,y), for x∈U and y∈V. By the assumed condition, these exclusions do not exhaust G, so it is still possible that favourable coin tosses will produce a witness. So we are done.
Note that the “important” direction is true, that is, a group satisfying the third condition of the conjecture has the property that a random Cayley graph for it is isomorphic to the random graph almost surely. What remains to be shown is a technical assertion about the random graph itself.
Problem: Is it true that the condition in the conjecture is equivalent to the stronger form in the theorem?
We note from this a conclusion related to Babai’s conjecture about random Cayley graphs. For the wide class of countable groups satisfying the condition, then a random Cayley graph is not a graphical regular representation; for it is isomorphic to the random graph, whose automorphism group is much larger than the group we started with (indeed, is uncountable).
The stronger statement is, in any case, easier to check. For example, consider an abelian group G. Let H be the set of elements of order 1 or 2 in G (the principal square-root set). Then any non-principal square-root set is a coset of H, as is any translate of a non-principal square-root set. So, if H has infinite index in G, then G satisfies our condition, and almost all its Cayley graphs are isomorphic to R.
An example of a group not satisfying the conditions is the infinite dicyclic group. This group is generated by two elements x and y; the element x has infinite order, y has order 4, and y inverts x (that is, y^{−1}xy = x^{−1}). The infinite cyclic subgroup H generated by x has four cosets, with coset representatives y^{i}, for i=0,1,2,3. It is easily checked that Z(1,y^{2}) = √y^{2} consists of the cosets Hy and Hy^{3}, while its translate by y, the set Z(y,y^{3}), consists of the other two cosets. So the group is the union of two translates of a non-principal square-root set. Examining the proof, we see that in a Cayley graph for this group, an element in Hy or in Hy^{3} has the same adjacencies to 1 and y^{2} (either joined to both or joined to neither), while any element in the other two cosets has the same adjacencies to y and y^{3}. Thus, every Cayley graph has the property that there is no vertex joined to 1 and y but not to y^{2} or y^{3}; so such a graph cannot be isomorphic to R.
B-groups
We begin with two classic definitions from permutation group theory.
A permutation group G acting on a set X is primitive if the only G-invariant partitions of X are the partition into singletons and the partition with a single part. A permutation group is 2-transitive if, given any two pairs of distinct elements of X, there is an element of G carrying the first pair to the second.
These definitions can be phrased in terms of relations:
- G is primitive if there is no non-trivial G-invariant equivalence relation;
- G is 2-transitive if there is no non-trivial G-invariant binary relation.
Here a relation is trivial if it is invariant under the whole of the symmetric group on X.
Now a group X is said to be a B-group if every primitive group containing the regular representation of X is 2-transitive. In other words, if we adjoin any permutations to the regular representation to kill all its invariant equivalence relations, then we actually kill all its invariant binary relations (except trivial ones, in each case).
Here B stands for Burnside. We cannot call these groups “Burnside groups”, since this term means finitely generated groups of finite exponent; so Wielandt opted for the term “B-groups”.
Burnside showed that a cyclic group of prime-power but not prime order is a B-group. This was an active area of research; Schur developed the theory of Schur-rings in considering finite B-groups. Like many such areas, it has been severely affected by the Classification of Finite Simple Groups. We now know that, for almost all positive integers n, every group of order n is a B-group. However, we do not have a precise description of the finite non-B-groups. (In fact, even powers of 2 are not among the “almost all” in the preceding statement; the direct product of cyclic groups of order 4 is a non-B-group. Now groups of 2-power order predominate in the enumeration; we cannot yet say that almost all finite groups are B-groups!)
In the infinite case, not surprisingly, things are different. A problem which I would very much like to see solved is:
Problem: Does there exist a countably infinite B-group?
Not a single example is known!
The relevance of the earlier result is that any group which satisfies the condition of the theorem (or indeed, the simpler but stronger condition of the conjecture) is not a B-group. For, if a group has a non-trivial Cayley graph whose automorphism group is primitive, then it is not a B-group; and it is clear that the automorphism group of the random graph is primitive.
Now we can show that no countable abelian group is a B-group. For, let G be a countable abelian group, and H the subgroup of elements of order 1 or 2. If H has infinite index in G, then G satisfies our conditions, and has R as a Cayley graph. On the other hand, if H has finite index, then G has finite exponent, and so can be written as a direct product of countably many finite groups. Thus, we can write G = A×B, where A and B are countably infinite. Now G preserves the “infinite square lattice” whose rows are cosets of A and whose columns are cosets of B; the automorphism group of this structure is primitive but not 2-transitive. (The two obvious partitions, into rows and columns, are interchanged by transposition.)
The work on homogeneous Cayley objects grew from the B-group problem. It is easy to tell whether the automorphism group of a homogeneous structure is primitive but not 2-transitive (for example, it will be primitive unless there is an equivalence relation definable in the structure without parameters). Every time we find such a structure as a Cayley object for a group G, then we know that G is not a B-group. Unfortunately, the random graph seems to be the best source of non-B-groups!
I end with a specific problem which I have not been able to solve.
Problem: Is the infinite generalised dicyclic group a B-group?
Previous |
Thanks… very much enjoying this series. One slightly glaring typo in the question at the beginning though (I suppose it is inevitable when you are both a graph theorist and a group theorist to occasionally forget what G is supposed to be!)
Oh dear, yes.
Etymologically “graph” is a Greek word and “group” a German word, so graphs should be capital Gamma and groups should be fraktur capital G. Trouble is, I never learned to draw Fraktur on the blackboard!