Group generators for graph symmetries

Last time we had a first attempt at a function to find the symmetries of a graph. This time we're going to make a minor improvement. (There is still a major improvement to come, but not this week.)

Our graphAuts1 function from last time listed all the symmetries of a graph. When we come to look at highly symmetric graphs, that is going to be a long list (thousands or even millions long in some cases). But if you do one symmetry of a graph followed by another (say a reflection followed by a rotation), the result is again a symmetry. What if we could find just a few symmetries of the graph, from which all the others could be generated as sequences of actions?

As an example, let's look at the symmetries of a square (or the graph c 4):

There are eight symmetries in all. However, we need just two of them to generate all the rest: the 90 degree clockwise rotation - a; and the reflection in the vertical axis - b. It is easy to see that doing the 180 (respectively 270) degree rotation is the same as doing the 90 degree rotation two (respectively three) times. This is written as a*a, or a^2. Not quite so easy to see is that the reflection in the horizontal axis is the same as doing the 180 degree rotation followed by the reflection in the vertical axis - written a^2 * b. (The starting position, or "do nothing", in the top left is labelled 1, because if you do nothing then do x, or do x then do nothing, that is the same as just doing x - so it acts like a 1: 1*x = x = x*1.)

You can confirm this within GHCi:

> :load Math.Algebra.Group.PermutationGroup
> let a = p [[1,2,3,4]]
> let b = p [[1,2],[3,4]]
> a^2 * b
[[1,4],[2,3]]
> 1 * a
[[1,2,3,4]]

Naturally, if someone gives us a set of permutations, such as [a,b] above, it would be good to be able to list all the elements that they generate. In Math.Algebra.Group.PermutationGroup, the "elts" function does just this:


import qualified Data.List as L
import qualified Data.Set as S

elts gs = elts' S.empty (S.singleton 1) where
   elts' interior boundary
       | S.null boundary = S.toList interior
       | otherwise =
           let interior' = S.union interior boundary
               boundary' = S.fromList [h * g | h <- S.toList boundary, g <- gs] S.\\ interior'
           in elts' interior' boundary' 

(This "closure" algorithm turns out to be useful for all sorts of things, so in the library code it's actually factored out into a separate function. However, for the specific problem of listing elements of permutation groups, we will in fact come up with a more efficient algorithm in due course.)

For example, with a and b as before:

> mapM_ print $ elts [a,b]
[]
[[1,2],[3,4]]
[[1,2,3,4]]
[[1,3],[2,4]]
[[1,3]]
[[1,4,3,2]]
[[1,4],[2,3]]
[[2,4]]

You can check that these are the eight symmetries shown in the diagram above.

It's much more convenient to work with a few generators than with hundreds or thousands of elements, so in the HaskellForMaths library we always represent a permutation group as a list of generators.

Okay, so how does this help us with graph symmetries? Well, the idea is that we'll still use depth-first search, but instead of searching for all symmetries, we'll search for just one symmetry that takes 1 to 2, one symmetry that takes 1 to 3, and so on, one symmetry that fixes 1, and takes 2 to 3, one symmetry that fixes 1, and takes 2 to 4, and so on, and so on. The ones that we find will generate all symmetries of the graph.

Here's the code:

graphAuts2 (G vs es) = graphAuts' [] vs where
   graphAuts' us (v:vs) =
       let uus = zip us us
       in concat [take 1 $ dfs ((v,w):uus) vs (v : L.delete w vs) | w <- vs, isCompatible (v,w) uus]
          ++ graphAuts' (v:us) vs
    graphAuts' _ [] = []
    dfs xys (x:xs) ys =
        concat [dfs ((x,y):xys) xs (L.delete y ys) | y <- ys, isCompatible (x,y) xys]
    dfs xys [] [] = [fromPairs xys]
    isCompatible (x,y) xys = and [([x',x] `S.member` es') == (L.sort [y,y'] `S.member` es') | (x',y') <- xys]
    es' = S.fromList es 

The bottom half of this function is just the same as graphAuts1 - it is only the graphAuts' part that is new. (Notice that the "take 1", together with lazy evaluation, means that we're actually searching far less of the tree now.)

Let's try it on our old favourite, the pentagon, c 5:

> mapM_ print $ graphAuts2 $ c 5
[[1,2],[3,5]]
[[1,3],[4,5]]
[[1,4],[2,3]]
[[1,5,4,3,2]]
[[2,5],[3,4]]

The claim is that these five symmetries generate all the rest. Let's make sure:

> mapM_ print $ elts $ graphAuts2 $ c 5
[]
[[1,2],[3,5]]
[[1,2,3,4,5]]
[[1,3,5,2,4]]
[[1,3],[4,5]]
[[1,4],[2,3]]
[[1,4,2,5,3]]
[[1,5,4,3,2]]
[[1,5],[2,4]]
[[2,5],[3,4]]

These are the same 10 symmetries that we found last time using graphAuts1 (though listed in a different order).

That's it for now.

Exercise:
(I meant to put this in last time, but forgot)
Find the symmetries of the following graphs, and explain your findings:

• k 5, the complete graph on 5 vertices
• kb 2 3, the complete bipartite graph on 2 and 3 vertices
• kb 3 3, the complete bipartite graph on 3 and 3 vertices