«Chapter 4 Cayley Diagrams Recall that in the previous chapter we deﬁned a group to be a set of actions that satisﬁes the following rules. Rule 1. ...»
Exercise 4.11. Repeat the above exercise, but do it for a square instead of a triangle. You’ll need to make some modiﬁcations to r and s. The resulting group is called D4.
Exercise 4.12. Consider the group from Exercise 3.20. Using “add 1” (or simply 1) as the generator⇤, describe what the Cayley diagram for this group would look like. Draw a chunk of the Cayley diagram. Can you think of another generating set? What will the Cayley diagram look like in this case?
Now that you’ve constructed a few examples for yourself, you should have a pretty healthy understanding of Cayley diagrams. There are still lots of properties to discover and opportunities to gain more intuition. If you weren’t able to complete exercises 3.20 and 4.7, go give them another shot.
⇤ Recall that Rule 2 guarantees that every action is reversible. So, if we have “add 1”, we also have “add 1.”
CHAPTER 4. CAYLEY DIAGRAMSBy the way, Cayley diagrams are named after their inventor Arthur Cayley, a nineteenth century British mathematician. We’ll see his name pop up a couple more times in the course.
Not only are Cayley diagrams visually pleasing, but they provide a map for the group in question. That is, they provide a method for navigating the group. Following sequences of arrows tells us how to do or undo an action. However, each Cayley diagram very much depends on the set of generators that are chosen to generate the group. If we change the generating set, we may end up with a very di↵erent looking Cayley diagram. This was the point of Exercise 4.7. It’s important to drive this point home, so let’s construct an explicit example.
Exercise 4.13. In Exercise 4.10, you constructed the Cayley diagram for the group called D3. In this case, you used the generators r and s. Now, let s 0 be the reﬂection that swaps the corners of the triangle that are in the corners of the hole labeled by 1 and 2.
(a) Justify that s and s 0 generate all of D3. Hint: Is it enough to generate r with s and s 0 ?
(b) Construct the Cayley diagram for D3 using s and s 0 as your generators. Did you get a di↵erent diagram than you did in Exercise 4.10?
Let’s do a few more exercises involving Cayley diagrams.
Exercise 4.14. Consider the Cayley diagram give below.
Describe a group of actions and a set of generators that would yield this Cayley diagram.
We haven’t explicitly deﬁned what a Cayley diagram actually is yet. So, it’s not completely obvious that the diagram in the previous exercise is actually a diagram for a group.
But rest assured; this Cayley diagram truly does correspond to a group. It’s important to point out that we can’t just throw together a digraph willy nilly and expect it to be a Cayley diagram.
Exercise 4.15. Consider the following diagram.
CHAPTER 4. CAYLEY DIAGRAMSExplain why the diagram cannot possibly be a Cayley diagram for a group. How many reasons can you come up with?
Exercise 4.16. Let G be a group of actions and S is a set of generators for G. Suppose we draw the Cayley diagram for G using the actions of S as our arrows and we color the arrows according to which generator they correspond to.
(a) Explain why there must be a sequence of arrows (forwards or backwards) from the vertex labeled e to every other vertex. Do you think this is true for every pair of vertices?
(b) Recall that G must satisfy Rule 1. What restriction does this put on our Cayley diagram?
(c) Since G must satisfy Rule 3, what constraints does this place on the Cayley diagram?
Try to draw a diagram that is almost a Cayley diagram but violates Rule 3.
(d) Since G must satisfy Rule 2, what does this imply about the Cayley diagram? Can you construct a diagram that is almost a Cayley diagram but violates Rule 2? To do this, you may need to violate another one of our rules.
(e) What property does Rule 4 force the Cayley diagram to have? Can you construct a diagram that is almost a Cayley diagram but violates Rule 4?
In the previous exercise, you discovered several properties embodied by all Cayley diagrams. Unfortunately, not every diagram having these properties will yield a Cayley diagram. For example, the diagram below satisﬁes the properties you discovered in Exercise 4.16, but it turns out that this cannot be a diagram for any group (regardless of how we label the vertices).