Strong generating sets for graph symmetries

[New release: HaskellForMaths 0.1.6 here]

Previously in this blog, we've been using two functions for finding generators for the group of symmetries of a graph. Both graphAuts2 and graphAuts3 use depth first search to find a transversal generating sequence - the only difference is that graphAuts3 does more pruning of the search tree, and so is faster.

A transversal generating sequence, remember, means this: If our vertices are labelled 1 to n, then we first try to find a symmetry that takes 1 to 2, then another that takes 1 to 3, and so on up to n; then looking only at those that leave 1 fixed, another which takes 2 to 3, then another which takes 2 to 4, and so on; then looking only at those that fix 1 and 2, another which takes 3 to 4, and so on; and so on. So the answer we get always takes the form of a series of levels - first, a set of symmetries taking 1 to some of [2..n], then a set of symmetries fix 1, and take 2 to some of [3..n], and so on.

Okay, so now suppose that we're doing our depth first search. Suppose that we have already found [[1,2],[3,4]], and [[1,3,2]]. Then in fact we don't need to search for a symmetry taking 1 to 4, because the two symmetries we know already generate one. Specifically:

> p [[1,3,2]] * p [[1,2],[3,4]]
[[1,4,3]]

So the point is that, as it happens, it was already possible to take 1 to 4 by repeated application of the symmetries we had already found to take 1 to 2 and 3.

Given a set of group elements, the orbit of a vertex is defined as those vertices that we can send it to by repeated application of the elements:

orbitV gs x = closure [x] [ (.^ g) | g <- gs ]

(This is using the closure algorithm that we defined previously. Recall that v .^ g means the image of v after action by g.)

This idea enables us to write an even faster graphAuts function. As before, we start by looking for symmetries that send 1 to 2, 1 to 3, and so on. However, this time, we don't bother to look for symmetries sending 1 to a vertex which is already in the orbit of the symmetries we have found.

An example will probably make this clearer. First of all, here is the full transversal generating set of symmetries of the cube:

> mapM_ print $ graphAuts3 $ q 3
[[0,1],[2,3],[4,5],[6,7]]
[[0,2,3,1],[4,6,7,5]]
[[0,3],[4,7]]
[[0,4,6,7,3,1],[2,5]]
[[0,5,3],[2,4,7]]
[[0,6,5,3],[1,2,4,7]]
[[0,7],[1,3],[2,5],[4,6]]
[[1,2],[5,6]]
[[1,4,2],[3,5,6]]
[[2,4],[3,5]]

The list consists of three levels: symmetries moving 0 to 1, 2, 3, 4, 5, 6, 7; symmetries fixing 0 and moving 1 to 2, 4; and a symmetry fixing 0 and 1 and moving 2 to 4. The sequence [0,1,2] is called the base for the TGS.

Now, here's what happens if we skip the search for vertices that are already in the orbit, using a new graphAuts function:

> mapM_ print $ graphAuts $ q 3
[[0,1],[2,3],[4,5],[6,7]]
[[0,2,3,1],[4,6,7,5]]
[[0,4,6,7,3,1],[2,5]]
[[1,2],[5,6]]
[[1,4,2],[3,5,6]]
[[2,4],[3,5]]

We still have three levels, with the same base, [0,1,2]. But in the first level, we haven't needed to find as many symmetries. After we found the 0 to 1 and 0 to 2 symmetries, we didn't need to find a 0 to 3 symmetry, because 3 was already in the orbit of the symmetries we had found. Then, after we had found the 0 to 4 symmetry, we didn't need to find the 0 to 5, 6, 7 symmetries.

> orbitV [ p [[0,1],[2,3],[4,5],[6,7]], p [[0,2,3,1],[4,6,7,5]], p [[0,4,6,7,3,1],[2,5]] ] 0
[0,1,2,3,4,5,6,7]

This new graphAuts function (I won't give the code, as it's really only a minor variation on the graphAuts3 function) is faster still, because we're now pruning the search tree even more.

However, it has lost the nice property of the graphAuts2 and graphAuts3 functions, that the returned list was a transversal generating sequence. Recall that a TGS made it particularly easy to work out the order of the group, or list its elements.

However all is not lost. We can easily reconstruct a TGS from the output of the graphAuts function. Consider that first level in the cube symmetries again. In the TGS, we had symmetries taking 0 to 1, 2, 3, 4, 5, 6, 7. The graphAuts function only returned symmetries taking 0 to 1, 2, 4. That was because it turned out that 3, 5, 6, 7 were already in the orbit of 0 under these symmetries. To reconstruct the TGS, what we need to do is, calculate the orbit of 0 under the 0 to 1, 2, 4 symmetries, but this time, keep track of the group elements as we go. For example, the reason 3 is in the orbit is that:

> p [[0,2,3,1],[4,6,7,5]] * p [[0,1],[2,3],[4,5],[6,7]]
[[0,3],[4,7]]

Here's the code. We find the base "bs" by looking at the minimum supports (the least vertex that is moved) of the inputs. We then sort the inputs into levels, using this base. Finally, for each level, we use a modified version of the closure algorithm, that tracks not only where we've got to in the orbit, but also how we got there.

tgsFromSgs sgs = concatMap transversal bs where
    bs = toListSet $ map minsupp sgs
    transversal b = closure b $ filter ( (b <=) . minsupp ) sgs
    closure b gs = closure' M.empty (M.fromList [(b, 1)]) where
        closure' interior boundary
            | M.null boundary = filter (/=1) $ M.elems interior
            | otherwise =
                 let interior' = M.union interior boundary
                     boundary' = M.fromList [(x .^ g, h*g) | (x,h) <- M.toList boundary, g <- gs] M.\\ interior'
                 in closure' interior' boundary' 

A set of generators from which we can reconstruct a TGS in this way is called a strong generating set, or SGS. (Strictly speaking, an SGS is relative to a base - we've been using the base that is implied by the Ord instance and the minimum supports of the elements.)

In practice, we prefer to work with SGS than TGS, because they're shorter. Since you can so easily reconstruct a TGS from them, they're just as useful.

I should admit that I'm sidestepping a few subtleties here. The take-home message is:

• A strong generating set is a set of generators for a group of a particularly useful form
• The graphAuts function gives us a strong generating set by construction

That means that for symmetries of graphs, we are doing pretty well. We have an efficient algorithm (graphAuts) for finding a strong generating set for the symmetry group.

However, what we would like is, given just any set of generators for a group, to be able to construct a strong generating set. For that, we will need the Schreier-Sims algorithm. Next time, I'll show why this would be so useful, by looking at Rubik's cube.