Groups and Cayley Graphs
The eighth group theory lecture
We left off last time discussing group actions.
We noted that any group has a natural action on a topological space—we will now show how to do it, but we need two things before that:
the notion of generators of a group, and
the Cayley graph of a group with a set of generators.
The first part is fairly easy.
Definition: Let X be a subset of a group G. Let SX be the set of all subgroups of G that contain X. The subgroup generated by X is
that is, it is the intersection of all subgroups of G that contain X.
Is this definitely a subgroup? Yes, that follows from a more general observation.
Lemma: Let S be any set of subgroups of a group G. Then
is a subgroup.
Proof: I leave this to the reader. □
Okay. But how should one think about this subgroup? What elements does it consist of?
Well, if you think about it, it is the smallest subgroup of G that contains everything in X—indeed, it is a subgroup, and by construction it is contained in any subgroup that contains all of X. So that must mean that for any elements x1, x2,… xn of X, and any integers k1, k2,… kn,
must be an element of ⟨X⟩. Conversely, every element in ⟨X⟩ must be of that form. Why? Because the collection of all such elements is a subgroup! (Check that a product of two elements of such form and the inverse of an element of such a form is also of the same form.) Since that subgroup contains all of X, ⟨X⟩ is contained inside of it. Therefore, they are actually one and the same.
Definition: Let X be a subset of a group G. We say that X generates G (and its elements are generators) if ⟨X⟩=G. We say that X is a minimal set of generators if there is no proper subset Y of X such that ⟨X⟩=G.
Some examples:
Any cyclic group is generated by {g}, where g is the generator.
Any cyclic group is generated by {g2,g3}, where g is the generator. (I leave proving this as an exercise to the reader!)
{R, T} generate D4—this is evident from the fact that we wrote every element in D4 as products of R and T.
S4=Sym({1,2,3,4}) is generated by the elements (1↦2, 2↦3, 3↦1, 4↦4) and (1↦1, 2↦2, 3↦4, 4↦3)1. (This is a straightforward but uninteresting computation.)
Examples 1, 3, and 4 are always minimal: if you remove even one element, the group that is generated is smaller. Example 2 is minimal for the infinite cyclic group, and for any cyclic group the order of whose generator is divisible by 6. But, for instance, you can check that ℤ/5ℤ is generated by both 2 and 3.
One thing this tells you is that generators are not quite like a basis in linear algebra. It is somewhat similar, because every vector in a vector space is a linear combination of the basis elements; likewise, every element of a group is some product of the generators. In linear algebra, we even say that a basis is a minimal generating set. But there is a crucial difference: while a vector space may have infinitely many different bases, they all have the same number of elements, and you can relate one to the other by an invertible linear map.
Not so for groups! Even the maximally simple example that is the infinite cyclic group admits minimal sets of generators of different sizes!
I mention this because it will be wise to remember in what follows that a group with a particular choice of generators is really a more structured object than just a group—we have made a particular (and not necessarily natural) choice in selecting some concrete set of generators. I’ll show an example in a second that will clarify what I mean. But first, let’s introduce Cayley graphs.
Definition: The Cayley graph of a group G with respect to a set of generators X is the directed graph whose vertices are the elements of G and such that there is an arrow between two vertices g and h if and only if there exists some x in X such that h=xg.
Honestly, it’s easier to understand this definition with some pictures.
Let’s start with the maximally simple case of the group ℤ generated by 1. The vertices will be …,-3, -2, -1, 0, 1, 2…, and for every n, there is an arrow n→n+1.
Let’s do something a little harder: ℤ generated by 2 and 3. The vertices are the same, but now we have different arrows. (Which we color code for convenience.)
Notice: these are two different graphs, even though it is the same group. This demonstrates what I said earlier: a group with generators is a more structured object. Cayley graphs are invariants of groups with generators; they are not invariants of groups. In particular, if you show that two groups have different Cayley graphs, it doesn’t automatically follow that they are not isomorphic.
Let’s do a more complicated example: we’ll draw the Cayley graph of D4, generated by R and T.
You might notice that Cayley graphs are very symmetric graphs. One obvious sense in which this is true is that for every vertex, there is the same number of incoming arrows, and the same number of outgoing arrows. This is immediate from the definition—there is one such arrow in both sets for each element in X, and no more.
But one can draw far less symmetric graphs that have this same property.
So, what is special about Cayley graphs? Here is what we are going to show: G acts on its Cayley graph such that if v→w are two vertices connected by an arrow, then g.v→g.w are also two vertices connected by an arrow. Furthermore, this action is faithful and transitive.
Definition: The action of a group G on a set X is called transitive if for every x, y in X, there exists g in G such that g.x=y.
Let’s put aside exactly what this action is—let’s just suppose that we can find such a thing. Why will it demonstrate that the Cayley graph is very symmetric? Because every vertex has to look “the same”—there exists a transformation (v↦g.v) that will move one vertex to the other, while preserving the connections in the graph: if there is an arrow between two arrows prior to the transformation, there is an arrow between them after the transformation, and vice versa.
Okay. Let’s try to build this action. The most obvious approach is to just multiply on the left: given g, h in G, define g.h=gh. This does define an action on G—but it doesn’t preserve the graph connections! Why? Remember that we have arrows h→xh. So, we need an arrow g.h→g.(xh). But that will only happen if there exists some y in X such that g.xh=gxh=y(g.h)=ygh. Or, canceling by h, we need gx=yg, or y=gxg-1. It could happen that gxg-1 is also an element of X, but there is no reason to expect that to happen. (For instance, we took R to be a generator of D4 above, but TRT-1=R3 wasn’t one of the generators.)
So, what is the next most obvious thing? How about multiplying on the right? Given g, h in G, define g.h=hg. This avoids the prior problem: if h→xh is an arrow, so is g.h→g.(xh), since this is just hg→xhg. Unfortunately, it isn’t (usually) an action! Why? Because if g1, g2, h are elements of G, then g1.(g2.h)=(g2.h)g1=hg2g1, which isn’t generally the same thing as (g1g2).h=hg1g2.2
Curses! Let’s try one more time. Multiplying on the right was a good idea, but we need to somehow reverse the order of elements. We can accomplish this if we remember that (gh)-1=h-1g-1. So, define g.h=hg-1. Then arrows are preserved and this is an action! We have accomplished the first part of what we wanted to do.
That said, we’re not quite done: we specifically wanted to show that we can think of G as acting by isometries, and we haven’t defined any type of notion of distance for this graph. Thankfully, there’s an easy way to do that.
Specifically, for every arrow g→xg in the graph, add a copy of the unit interval [0,1]—call it eg,xg. Consider first their union,
There’s a perfectly good notion of distance defined on each individual interval, but they are all disjoint from each other. We fix this by identifying endpoints. Specifically, 0∈eg,h represents the same point as 0∈eg,k and the same point as 1∈ek,g; similarly, 1∈eg,h represents the same point as 0∈eh,k and the same point as 1∈ek,h. Call the resulting equivalence relation ~ and define T to be the result of identifying points in Tpre using this equivalence relation. These points where we are identifying are precisely the original vertices of the Cayley graph; the intervals correspond to the arrows.
A picture would likely be very welcome here.
We define the distance between two points in this space to be the minimal net distance that one would need to travel along these intervals from one point to the other.
How to define the action of G on this space? Simple: send each t∈eh,k to t∈ehg-1,kg-1! What is this doing? It moves the vertices of the Cayley graph precisely as it did before, and all of the corresponding intervals come along for the ride, so to speak. Checking that this defines an isometry is not complicated but a little tedious, so we shall skip it.
And there you have it: we produced a fairly simple geometric object on which the group acts via isometries. Thus, every group is isomorphic to a subgroup of an isometry group.
There are a number of different directions where we could now take this. One is to study Cayley graphs of groups—the fact that they are so intrinsically symmetric is interesting and useful. After all, we showed in an earlier article how such graphs can aid in building processor networks.
We know that for the Cayley graph there is a nice group action on it—we could generalize this, and for any given graph, ask what non-trivial group actions exist on it. Another way to phrase this is that we could study the symmetries of the graph. For example, if there exists a transitive action, we say that the graph is symmetric.
Alternatively, given a group, we could try to find a nice geometric space or a nice graph on which it acts, and from this deduce some properties of the group. There are entire books dedicated to various iterations of this approach. For example, Serre’s book Trees is really about groups that act on trees (i.e. connected graphs without any cycles).
