Some groups and some graphs

(Spoiler alert: Solutions to last week's exercise coming up.)

Previously we looked at the graphAuts1 function, which lists all symmetries of a graph, and the graphAuts2 function, which lists a set of generators for the symmetry group of a graph: that is, a few symmetries, from which all the rest can be generated as products / sequences.

This time we're going to start looking at some particular graphs.

Recall that the complete graph, k n, is the graph on n vertices which has every possible edge.

k n = graph (vs,es) where
    vs = [1..n]
    es = combinationsOf 2 vs

For example:

> k 5
G [1,2,3,4,5]
[[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],[4,5]]


If we look at the symmetries of this graph:

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

Remember that graphAuts2 tries to find symmetries that take the 1 vertex to the 2, 3, 4, or 5 positions, symmetries that leave 1 where it is and take the 2 vertex to the 3, 4, or 5 positions, symmetries that leave 1 and 2 where they are, and so on. In this case, it seems to have found everything it's looking for.

That's because, for the complete graph, any permutation of the vertices is a symmetry. Recall that a symmetry is a permutation of the vertices that moves edges to edge positions and non-edges to non-edge positions. In the complete graph, every position is an edge position, so there are no non-edges, and every edge moves to an edge position, no matter what we do.

Let's just check. We know that the number of permutations of n objects is n!. The "elts" function lists all the permutations generated by a generating set.

> length $ elts $ graphAuts2 $ k 5
120

So it works (5! = 120). The group of all permutations of [1..n] is called the symmetric group, S n. "graphAuts2" found 10 generators, but in fact we could have generated all the elements from just two generators:

_S n | n >= 3 = [s,t]
     | n == 2 = [t]
     | n == 1 = []
    where s = p [[1..n]]
          t = p [[1,2]]

The two generators are an n-cycle s, which cycles all n positions, and a "transposition" t, which just swaps two positions. Let's check that s and t really do generate all permutations:
> _S 5
[[[1,2,3,4,5]],[[1,2]]]
> length $ elts $ _S 5
120
> map (isGraphAut (k 5)) (_S 5)
[True,True]

What about the complete bipartite graphs kb m n? Recall that these consist of m vertices on the left and n on the right, with every left vertex joined to every right vertex by an edge.

kb' m n = graph (vs,es) where
    vs = map Left [1..m] ++ map Right [1..n]
    es = [ [Left i, Right j] | i <- [1..m], j <- [1..n] ] 

For example:
> kb' 2 3
G [Left 1,Left 2,Right 1,Right 2,Right 3]
[[Left 1,Right 1],[Left 1,Right 2],[Left 1,Right 3],[Left 2,Right 1],[Left 2,Right 2],[Left 2,Right 3]]

> mapM_ print $ graphAuts2 $ kb' 2 3
[[Left 1,Left 2]]
[[Right 1,Right 2]]
[[Right 1,Right 3,Right 2]]
[[Right 2,Right 3]]

This is saying that we can take any left vertex to any other left vertex, and any right vertex to any other right vertex. Moreover, we can do the left and right moves independently of one another. However, we can't take a left vertex to a right vertex - unless m = n.

So on the left side, we have the full symmetric group S m acting on the left vertices, and on the right side we have the full symmetric group S n acting on the right vertices - and they are acting independently of one another. This situation is called the cartesian product of the two groups. In the HaskellForMaths library, there is a "cp" function to construct the cartesian product of two groups H and K:

cp :: (Ord a, Ord b) =>
    [Permutation a] -> [Permutation b] -> [Permutation (Either a b)]
cp hs ks =
    [P $ M.fromList $ map (\(x,x') -> (Left x,Left x')) $ M.toList h | P h <- hs] ++
    [P $ M.fromList $ map (\(y,y') -> (Right y,Right y')) $ M.toList k | P k <- ks] 

(Recall that permutations are implemented using Data.Map - hopefully you can see what's going on here.)
So hs is a list of generators for a group H acting on a, ks is a list of generators for a group K acting on b. What this function does is create a copy of hs in the left part of an Either a b, and a copy of ks in the right part. Taken together, these generate a group which is isomorphic to the cartesian product of H and K.

For example:
> mapM_ print $ _S 2 `cp` _S 3
[[Left 1,Left 2]]
[[Right 1,Right 2,Right 3]]
[[Right 1,Right 2]]

Exercise:
What is wrong with the following alternative definition of cartesian product of groups?

cp2 :: (Ord a, Ord b, Num a, Num b) =>
    [Permutation a] -> [Permutation b] -> [Permutation (a, b)]
cp2 hs ks =
    [P $ M.fromList $ map (\(x,x') -> ((x,1),(x',1))) $ M.toList h | P h <- hs] ++
    [P $ M.fromList $ map (\(y,y') -> ((1,y),(1,y'))) $ M.toList k | P k <- ks] 

(By the way, I hope that the cp and cp2 functions convince you of the beauty of having made our Permutation type polymorphic.)

Anyway, I hope you're beginning to get a feel for how this graph symmetry thing works.
Time to look at some more interesting graphs. This is the Petersen graph:

It's defined as follows:

petersen = graph (vs,es) where
    vs = combinationsOf 2 [1..5]
    es = [ [v1,v2] | [v1,v2] <- combinationsOf 2 vs, disjoint v1 v2] 

The vertices are the 2-subsets of [1..5] (see the labels on the picture), with edges between 2-subsets that are disjoint.

I'll just mention in passing that the 2-subsets of [1..5] have a natural interpretation as the edges of k 5, so that in fact we have:

> petersen == complement (lineGraph' (k 5))
True


Now hopefully you're thinking to yourself "Hmm, from the construction, I wonder whether there is an action of S 5 on the Petersen graph.".

Indeed there is. The action of S 5 on [1..5] induces an action on the 2-subsets of [1..5]. Because the construction is "symmetric" on the 2-subsets (the 2-subsets are all treated the same way), the induced actions are actually symmetries of the Petersen graph.

Here's some code which can be used to calculate the induced action:

action xs f = fromPairs [(x, f x) | x <- xs] 

For example:

> action (combinationsOf 2 [1..5]) (-^ p [[1,2,3,4,5]])
[[[1,2],[2,3],[3,4],[4,5],[1,5]],[[1,3],[2,4],[3,5],[1,4],[2,5]]]

So the 5-cycle [[1,2,3,4,5]], acting on [1..5], induces an action on the 2-subsets of [1..5] which consists of two 5-cycles, for 2-subsets {x,x+1}, and 2-subsets {x,x+2} (mod 5). If you look back at the picture, you'll see that this is an anti-clockwise 2/5 turn. On the other hand:

> action (combinationsOf 2 [1..5]) (-^ p [[1,2]])
[[[1,3],[2,3]],[[1,4],[2,4]],[[1,5],[2,5]]]

If you look at the picture, you'll see that this is a rather more intriguing symmetry of the Petersen graph, which swaps the inner 13,25 edge with the outer 23,15 edge.

(Note: The above code is a slight improvement over the code for this task in v0.1.3, and will be included in the next HaskellForMaths release.)

It turns out that all the symmetries of the Petersen graph are induced by this action of S 5:
> elts (graphAuts2 petersen) == elts [action (combinationsOf 2 [1..5]) (-^ g) | g <- _S 5]
True

That's about it for now. I'll leave you with something to think about.

Exercise:
If you give me a graph g, and show me what "graphAuts2 g" returns, I can tell you at a glance how many symmetries g has. (That is, I can tell you what "length $ elts $ graphAuts2 g" would return, but without running it.) How do I do it?

For example, here's the dodecahedron graph.


> mapM_ print $ graphAuts2 dodecahedron
[[1,2],[3,5],[6,8],[9,15],[10,14],[11,13],[17,20],[18,19]]
[[1,3],[4,5],[6,10],[7,9],[11,15],[12,14],[16,17],[18,20]]
[[1,4],[2,3],[6,12],[7,11],[8,10],[13,15],[16,18],[19,20]]
[[1,5,4,3,2],[6,14,12,10,8],[7,15,13,11,9],[16,20,19,18,17]]
[[1,6,15,20,19,18,11,10,3,2],[4,8,5,7,14,16,13,17,12,9]]
[[1,7,20,18,12,3],[2,6,16,19,11,4],[5,8,15,17,13,10],[9,14]]
[[1,8,3],[4,6,9],[5,7,10],[11,14,16],[12,15,17],[13,20,18]]
[[1,9,6,17,15,18,14,11,5,10],[2,8,7,16,20,19,13,12,4,3]]
[[1,10],[2,3],[4,8],[5,9],[6,11],[7,12],[13,16],[14,17],[15,18],[19,20]]
[[1,11],[2,10],[5,12],[6,18],[7,17],[8,9],[13,14],[15,19]]
[[1,12,9],[2,4,10],[5,11,8],[6,13,17],[7,14,18],[15,19,16]]
[[1,13,6,19,7,18,8,11,2,12],[3,4,5,14,15,20,16,17,9,10]]
[[1,14,20,18,9,3],[2,5,15,19,17,10],[4,6,13,16,11,8],[7,12]]
[[1,15,19,11,3],[2,6,20,18,10],[4,5,14,13,12],[7,16,17,9,8]]
[[1,16,10],[2,7,9],[3,6,17],[4,15,18],[5,20,11],[12,14,19]]
[[1,17,4,7,11],[2,9,3,8,10],[5,16,12,6,18],[13,15,19,14,20]]
[[1,18],[2,11],[3,10],[4,9],[5,17],[6,19],[7,13],[8,12],[14,16],[15,20]]
[[1,19,8,14,17],[2,13,9,5,18],[3,12,10,4,11],[6,20,7,15,16]]
[[1,20,11,2,15,18,3,6,19,10],[4,7,13,9,5,16,12,8,14,17]]
[[2,5],[3,4],[7,15],[8,14],[9,13],[10,12],[16,20],[17,19]]
[[2,6,5],[3,7,14],[4,8,15],[9,20,12],[10,16,13],[11,17,19]]
[[3,8],[4,7],[5,6],[9,10],[11,17],[12,16],[13,20],[14,15]]

I can tell just by looking at that list that there are 120 symmetries in total. How do I do it?