Conjugacy classes, part 2

Last time we saw that the symmetries of a graph can be divided into conjugacy classes, where the elements of each class are somehow the same symmetry, just viewed from a different angle. This time we're going to look at the conjugacy classes of symmetries of a few simple graphs, to get more of a feel for how this works.

Let's start with the graph of the cube, otherwise known (in graph theory) as q 3. q n has as vertices all points in {0,1}ⁿ, with edges between pairs of vertices which differ in only one position:

q' k = graph (vs,es) where
    vs = sequence $ replicate k [0,1]
    es = [ [u,v] | [u,v] <- combinationsOf 2 vs, hammingDistance u v == 1 ]
    hammingDistance as bs = length $ filter id $ zipWith (/=) as bs 

For example:

> :load Math.Combinatorics.GraphAuts
> q' 3
G [[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]
[[[0,0,0],[0,0,1]],[[0,0,0],[0,1,0]],[[0,0,0],[1,0,0]],[[0,0,1],[0,1,1]],
[[0,0,1],[1,0,1]],[[0,1,0],[0,1,1]],[[0,1,0],[1,1,0]],[[0,1,1],[1,1,1]],
[[1,0,0],[1,0,1]],[[1,0,0],[1,1,0]],[[1,0,1],[1,1,1]],[[1,1,0],[1,1,1]]]

However, this is a bit hard to read, a jumble of 0s, 1s and square brackets, so we normally work over integers instead, by considering the sequences of 0s and 1s as the bits in the binary representation of a number:

> q 3
G [0,1,2,3,4,5,6,7]
[[0,1],[0,2],[0,4],[1,3],[1,5],[2,3],[2,6],[3,7],[4,5],[4,6],[5,7],[6,7]]


Okay, so we would like to investigate the symmetries of the cube, and as we saw last time, what we're really interested in is just the different classes of symmetry, rather than listing every single symmetry.

> mapM_ print $ conjClassReps $ graphAuts2 $ q 3
([],1)
([[0,1],[2,3],[4,5],[6,7]],3)
([[0,1],[2,5],[3,4],[6,7]],6)
([[0,1,3,2],[4,5,7,6]],6)
([[0,1,3,7,6,4],[2,5]],8)
([[0,3],[1,2],[4,7],[5,6]],3)
([[0,3,6,5],[1,2,7,4]],6)
([[0,3,6],[1,7,4]],8)
([[0,3],[4,7]],6)
([[0,7],[1,6],[2,5],[3,4]],1)

What we need to do is look at the representatives of each class, and try to understand what they are doing, so as to be able to give a textual description:

• [] is the identity permutation, which leaves everything where it is
  
• [[0,1],[2,3],[4,5],[6,7]] is a reflection in a plane midway between opposing faces. There are three such elements, because there are three pairs of opposing faces.
• [[0,1],[2,5],[3,4],[6,7]] is a 180 degree rotation about an axis joining the midpoints of opposite edges. There are six elements, because there are six pairs of opposite edges.
• [[0,1,3,2],[4,5,7,6]] is a 90 degree rotation about an axis through the centres of opposing faces. There are six faces (or three pairs of faces, with clockwise and anti-clockwise turns).
• [[0,1,3,7,6,4],[2,5]] - this is an interesting one. There is a 6-cycle, so there's some sort of 60 degree rotation going on. But there is also a 2-cycle, so some sort of reflection or 180 degree rotation. If you think about it, you'll see that what is happening is that you're holding the cube by opposite corners (2 and 5 here), and spinning it by 60 degrees - but at the same time, reflecting it in the plane midway between.
• Exercise: Finish off the list
  

Previously we saw that the automorphism group of the complete graph k n is the symmetric group S n.

The conjugacy classes of S n are particularly easy to understand. Let's look at an example:

> mapM_ print $ conjClassReps $ _S 5
([],1)
([[1,2]],10)
([[1,2],[3,4]],15)
([[1,2],[3,4,5]],20)
([[1,2,3]],20)
([[1,2,3,4]],30)
([[1,2,3,4,5]],24)

k 5 doesn't have an obvious spatial interpretation (unlike the pentagon and the cube that we have considered previously), so we're going to need a more abstract description of the classes.

Let's have a look at one of the classes:
> conjClass (_S 5) (p [[1,2]])
[[[1,2]],[[1,3]],[[1,4]],[[1,5]],[[2,3]],[[2,4]],[[2,5]],[[3,4]],[[3,5]],[[4,5]]]

There might be a slight surprise here. Surely [[1,2]] and [[1,3]] don't belong in the same class, you might think, because 1 and 2 are next to each other, and 1 and 3 aren't. Or to take another example, we have [[1,2,3,4,5]], and [[1,3,5,2,4]] in the same class - surely that can't be right - we saw when looking at c 5 that one is a 1/5 rotation, and the other is a 2/5 rotation.

Well, the first thing to point out is that we can be misled by the spatial representation of a graph. In the picture of k 5, it might look like the relationship between 1 and 2 is not the same as the relationship between 1 and 3. However, from the point of the view of the graph, it is. An alien who saw in graph space rather than in 2-d or 3-d space wouldn't be able to tell a difference.

Another thing to emphasize is that conjugacy classes are relative to the group you're working in. For example, the elements [[1,2,3,4,5]] and [[1,3,5,2,4]] occur in both S 5 and D 10 (the symmetry group of c 5). In S 5, they are in the same conjugacy class, but in D 10, they are not. Specifically, we have:

> p [[1,2,3,4,5]] ~^ p [[2,3,5,4]]
[[1,3,5,2,4]]

[[2,3,5,4]] is an element of S 5, so [[1,2,3,4,5]] and [[1,3,5,2,4]] are conjugate in S 5. However, [[2,3,5,4]] is not an element of D 10, so they are not conjugate in D 10.

We can translate this back to our intuition about conjugate elements "looking the same but from a different angle". We have our alien who sees in graph space. When our alien is sitting in the graph space k 5, then [[2,3,5,4]], being a symmetry of the graph, is a transformation that moves the graph to a different angle. On the other hand, in the graph space c 5, [[2,3,5,4]] is not a symmetry - instead of moving the graph to a different angle, it just crumples the graph up.

Let's look a little more closely at that conjugation operation again:

> p [[1,2,3,4,5]] ~^ p [[2,3,5,4]]
[[1,3,5,2,4]]

Let's compare where we started - [[1,2,3,4,5]] - with where we ended - [[1,3,5,2,4]] - what has changed? Well, the 2 turned into a 3, the 3 turned into a 5, the 5 turned into a 4, and the 4 turned into a 2. So conjugating by [[2,3,5,4]] has the same effect as actually applying [[2,3,5,4]] to each of the numbers in the cycle notation for [[1,2,3,4,5]].

Why is this? Well, remember that:

g ~^ h = h^-1 * g * h

So if h is [[2,3,5,4]], what this says is:

• First, undo [[2,3,5,4]]. That is, put 3 into the 2 position, 5 into the 3 position, and so on.
• Next, do g. But if g says to do something to 2, we'll actually be doing it to 3, which is in the 2 position, and so on.
• Finally, do [[2,3,5,4]]. So put whatever's in the 2 position back into the 3 position, put what's in the 3 position back in the 5 position, and so on.

For example, if g = [[1,2,3,4,5]], then the overall effect on 3 is: put into the 2 position (h^-1), then put into the 3 position (g), then put into the 5 position (h). Notice the way that 3 gets off the merry-go-round at one point, but gets on again at a different point, because someone rearranged the chairs in the middle.

Well anyway, I'm sure if you think about it hard enough, you'll get it.

Getting back to the conjugacy classes of S n, it turns out that a conjugacy class in S n just consists of all elements having the same "cycle shape". For example, the class of [[1,2]] consists of all elements having a single 2-cycle. The class of [[1,2],[3,4]] consists of all elements having two 2-cycles. The class of [[1,2],[3,4,5]] consists of all elements having a 2-cycle and a 3-cycle.

The reason for this should now be obvious. To get from [[1,2],[3,4,5]] to [[a,b],[c,d,e]], you just need to find the permutation that sends 1 to a, 2 to b, 3 to c, 4 to d, and 5 to e. Since S 5 contains all permutations of [1..5], this permutation must be among them.

Hope that all made sense.