«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. ...»
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. There is a predeﬁned list of actions that never changes.
Rule 2. Every action is reversible.
Rule 3. Every action is deterministic.
Rule 4. Any sequence of consecutive actions is also an action.
It is important to point out that this is an intuitive starting point and does not constitute the o cial deﬁnition of a group. We’ll continue to postpone a rigorous deﬁnition in this chapter and instead we will focus on developing more intuition about what groups are and what they “look like.” To get started, let’s continue thinking about the game Spinpossible (see Chapter 3).
In Exercise 3.3, we discovered that there are a total of 29 · 9! = 185, 794, 560 possible scrambled Spinpossible boards. Now, imagine we wanted to write a solution manual that would describe how to solve all these boards. There are likely many possible ways to construct such a solution manual, but here is one way.
The manual will consist of 185, 794, 560 pages such that each page lists a unique scrambling of the 3 ⇥ 3 board. Don’t forget that one of these scramblings is the solved board. Let’s make this page 1. Also, imagine that the book is arranged in such a way that it isn’t too di cult to look up a given scrambled board. On each page below the scrambled board is a table that lists all possible spins. Next to each spin, the table indicates whether doing that particular spin will result in a board that is either closer to being solved or farther. In addition, the page number that corresponds to the resulting board is listed next to each spin.
In most cases, there will be many spins that take us closer to the solved board. Given a scrambled board, a solution would consist of following one possible sequence of pages through the book that takes us from the scrambled board to the solved board. There could be many such sequences. If we could construct such a solution manual, we would have an atlas or map for the game Spinpossible. We could always say, “We are here,” and “The solution is down one of these paths.”
CHAPTER 4. CAYLEY DIAGRAMSNote that even if we make a wrong turn (i.e., follow a page that takes us farther away from the solution), we can still get back on track by following page numbers that take us closer to the solved board. In fact, we can always ﬂip back to the page we were on before taking a wrong turn. This page will be listed on our “wrong turn page” since doing the same spin twice has the net e↵ect of doing nothing. If you were to actually do this, the number of pages we would need to visit would be longer than an optimal solution, but we’d get to the solved board nonetheless.
Let’s get a little more concrete. Consider the game Spinpossible, except let’s simplify it a little. Instead of playing on the 3 ⇥ 3 board, let’s play on a 1 ⇥ 2 board consisting of a single row with tiles labeled 1 and 2. We’ll refer to this simpliﬁed game as Spin1⇥2.
The rules of the game are what you would expect we are restricted to spins involving just the tiles in positions 1 and 2 of the original board. A scrambling of Spin1⇥2 consists of any rearrangement of the tiles 1 and 2, where any of the tiles can be right-side-up or up-side-down.
Exercise 4.1. First, convince yourself that Spin1⇥2 satisﬁes our four rules of a group.
(a) How many scrambled boards are there for Spin1⇥2 ? Don’t forget to include the solved board.
(b) How many possible spins are there for Spin1⇥2 ?
Let’s try to make a map for Spin1⇥2, but instead of writing a solution manual, we will draw a picture of the group called a Cayley diagram. The ﬁrst thing we’ll do is draw each of the scramblings that we found in the previous exercise. It doesn’t matter how we arrange all of these drawings, as long as there is some space between them. These little drawings will form the vertices of our Cayley diagram. Now, for each scrambling, ﬁgure out what happens when we do each of our allowable spins. For each of these spins, we’ll draw an arrow from the initial scrambled board to the resulting board. Don’t worry about whether doing each of these spins is a good idea or not. In fact, ﬁgure out what happens when we do our allowable spins to the solved board, as well. In this case, each of our scrambled boards will have 3 arrows heading out towards 3 distinct boards. Do you see why?
In order for us to keep straight what each arrow represents, let’s color our arrows, so that doing a particular type of spin is always the same color. For example, we could color the arrows that toggle the tile in the ﬁrst position as green. Recall that doing the same spin twice has the net e↵ect of doing nothing, so we should just make all of our arrows point in both directions.
To make sure you are keeping up to speed, consider the following scrambled board.
This board is one of our 8 possible scrambled boards in Spin1⇥2. We have three possible spins we can do to this board: toggle position 1, toggle position 2, or spin the whole board. Each of these spins has a corresponding two-way arrow that takes us to three di↵erent scrambled boards. The ﬁgure below depicts the chunk of the Cayley Diagram involved the board above. (I’ll replace my hand drawn version later.)
CHAPTER 4. CAYLEY DIAGRAMSNotice we have three di↵erent colored arrows. Can you see what each of the colors corresponds to? If we include the rest of the scrambled boards and all possible spins, we obtain the complete Cayley diagram for Spin1⇥3. (I’ll replace my hand drawn version later.) In this case, the spins that correspond to the three arrow colors are the generators of Spin1⇥2. What this means is that we can obtain all possible scramblings/unscramblings by using just these 3 spins. In other words, each of the scramblings corresponds to a word in these three spins. The question remains as to whether we want each board to correspond to a word that unscrambles to the solve board or scrambles the solved board. This might seem counter to how you want it to be, but we’ll adopt the convention that each board corresponds to words that scramble the solved board into the desired scrambled board.
Let t1 be the spin that toggles position 1, t2 be the spin that toggles position 2, and s1 be the spin that rotates the full board. Recall that when we write down words, we should apply the actions from right to left (like function composition).
Consider the following scrambled board.
CHAPTER 4. CAYLEY DIAGRAMSLooking at our Cayley diagram for Spin1⇥2, we see that one way to get to this board from the solved board is to follow a blue arrow followed by a red arrow. This corresponds to the word s1 t2. However, it also corresponds to the word t2 s1 t2 t1 even though this is not an optimal solution.
Exercise 4.2. Given a word that corresponds to a scrambled board in the Cayley diagram for Spin1⇥2, how could we obtain a solution to the scrambled board?
Exercise 4.3. Using the Cayley diagram for Spin1⇥2, ﬁnd three distinct words that correspond to the following scrambled board. Don’t worry about whether your word is of optimal length or not.
Exercise 4.4. Consider the Cayley diagram for Spin1⇥2, but remove all the red arrows.
This corresponds to forbidding the spin that rotates the full 1 ⇥ 2 board. Can we obtain all of the scrambled boards from the solved board using only blue and green arrows?
Exercise 4.5. Repeat the previous exercise, but this time remove only the green arrows.
What about the blue arrows?
In general, a Cayley diagram for a group G is a digraph having the set of actions of G as its vertices and the directed edges (i.e., arrows) correspond to the generators of the group. Recall that the generators are a potentially smaller set of actions from which you can derive all the actions of the group. The way you can derive new actions is by forming words in the generators. Rule 2 guarantees that every action is reversible, so we also allow the use of a generator’s reversal in our words.
The arrows follow the direction of the action that it corresponds to. If a generator is its own reversal, then the arrows corresponding to that generator are two-way arrows. It is always true that following an arrow backwards corresponds to a generator’s reversal.
We need a way to tell our arrow types apart. One way to do this is to color them. Another way would be to label the arrows by their corresponding generator.
Remember that in any group there is always a do-nothing action. One of the vertices should be labeled as the do-nothing action. From this point forward, unless someone says otherwise, let’s use e to denote our do-nothing action for a group. Each vertex is labeled with a word that corresponds to the sequence of arrows that we can follow from the do-nothing action to the particular vertex. Since there are possibly many sequences of arrows that could take us from the do-nothing vertex to another, each vertex could be labeled with many di↵erent words.
In the Cayley diagram for Spin1⇥2, our vertices were fancy pictures of scrambled 1 ⇥ 2 Spinpossible boards. This wasn’t necessary, but is convenient and appealing for aesthetic reasons. Also, we never actually labeled the vertices with the corresponding words. However, these are easy to obtain by following the sequence of arrows. Of course, in order to
CHAPTER 4. CAYLEY DIAGRAMSdo this, we need to know that the vertex that is the solved board corresponds to the donothing action.
The next two exercises may be too
for you at the moment. Give them a shot and if you can’t do them now, come back to them after you’ve constructed a few Cayley diagrams.
Exercise 4.6. Assume G is 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. Assume that each vertex is labeled with a word in the generators or their reversals. If the arrows are not labeled, how can you tell which generator they correspond to?
Exercise 4.7. Assume G is a group. Suppose that S and S 0 are two di↵erent sets that generate G. If you draw the Cayley diagram for G using S and then draw the Cayley diagram for G using S 0, what features of the two graphs are the same and which are potentially di↵erent?
Let’s build a few more Cayley diagrams to further our intuition.
Exercise 4.8. Consider the group consisting of the actions that rearranges two coins, say a penny and a nickel. Let’s assume we start with the penny on the left and the nickel on the right. Let’s call this group S2.
(a) Write down all possible actions using verbal descriptions. Hint: There aren’t that many of them.
(b) Let s be the action that swaps the left and right coins. Does s generate S2 ? That is, can we write all of the actions of S2 as words in s (or its reversal)?
(c) Decide on a simple generating set for S2 and draw a Cayley diagram for S2 using your generating set. Label all the vertices and arrows appropriately. Recall that above we said that we will use e to denote the do-nothing action unless someone says otherwise.
Exercise 4.9. Consider a square puzzle piece that ﬁts perfectly into a square hole. Let R4 be the group of actions consisting of rotating the square by an appropriate amount so that it ﬁts back into the hole.
(a) Write down all possible actions using verbal descriptions. Are there lots of ways to describe each of your actions?
(b) Let r be the action that rotates the puzzle piece by 90 clockwise. Does r generate R4 ? If so, write down all of the actions of R4 as words in r.
(c) Which of your words above is the reversal of r?
(d) Draw the Cayley diagram for R4 using r as the generator. Be sure to label the vertices and arrows. Are your arrows one-way or two-way arrows?
CHAPTER 4. CAYLEY DIAGRAMSExercise 4.10. Consider a puzzle piece like the one in the previous exercise, except this time, let’s assume that the piece and the hole are an equilateral triangle. Let D3 be the group of actions that allow the triangle to ﬁt back in the hole. In addition to rotations, we will also allow the triangle to be ﬂipped over. To give us a common starting point, let’s assume the triangle and hole are positioned so that a base of the triangle is down. Also, let’s label both the points of the hole and the points of the triangle with the numbers 1, 2, and 3. Assume the labeling on the hole starts with 1 on top and then continues around in the obvious way going clockwise. Label the puzzle piece in the same way and let’s assume that the triangle starts in the position that has the labels matching (i.e., the point of the triangle labeled 1 is in the corner of the hole labeled 1, etc.).
(a) How many actions are there? Can you describe them? One way to do this would be to indicate where the labels of the triangle are in the hole.
(b) Let r be rotation by 120 in the clockwise direction. Does r generate D3 ?
(c) What is the reversal of r? Can you write it as a word in r?
(d) Let s be the ﬂip (or we could call it a reﬂection) that swaps the corners of the puzzle piece that are in the positions of the hole labeled by 2 and 3 (this leaves the corner in position 1 of the hole in the same spot). Does s generate D3 ?
(e) What is the reversal of s? Can you write it as a word?
(f) Can we generate all of D3 using both r and s? If so, write all the actions of D3 as words in r and s (or their reversals).
(g) Draw the Cayley diagram for D3 using r and s as your arrows. Hints: One of your arrow types is one-way and the other is two-way. I suggest putting half the vertices in a circle and then the other half in a concentric circle outside your ﬁrst half. Label one of the vertices on the inner circle as e and ﬁrst think about applying consecutive actions of r. Try to stay on the inner circle of vertices as you do this. Now, starting at e, apply s and go to one of the vertices in the outer circle. Try to label the remaining vertices using both r and s. There are multiple ways to do it.