Friday, 26 June 2009

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 5G [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 5120`
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 5120> 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 3G [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?

1. can you tell us at a glance how many symmetries g has if we show you what "graphAuts g" returns ?

2. scheman: Not quite at a glance, but it's still fairly easy. So in the later installments, I explained that graphAuts2 and graphAuts3 return "transversal generating sets", while graphAuts returns a "strong generating set". In both cases, the first thing you need to do is split the generating set into levels: the auts that move 1, those that fix 1 but move 2, those that fix 1 and 2 but move 3, and so on. For example, here's graphAuts dodecahedron, split into levels:

[[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,6,15,20,19,18,11,10,3,2],[4,8,5,7,14,16,13,17,12,9]]

[[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]]

Now, in each level, we need to figure out how many vertices are in the orbit of the base vertex.
In the first level, the base vertex is 1. The third of the three auts has a cycle of 10 vertices which can be reached from 1. We just need to see whether we can reach the other 10-cycle. Well, we can, using the first two auts, eg 1 -> 3 (second aut), 3 -> 5 (first aut), and 5 puts us into the second 10-cycle in the third aut.
In the second level, the base vertex is 2. The orbit is [2,5,6]. (You can check that neither aut in the second level can take 2 outside this orbit.)
In the third level, the orbit is [3,8].
So we get 20*3*2 = 120, as expected.

3. thanks.
by the way, is it safe to design a permutation-transformed graph by

appliedTo :: (Ord a) => Permutation a -> Graph a -> Graph a
per `appliedTo` g = let (G vs es) = g in graph (Data.List.sort \$ map (flip (.^) per) vs, Data.List.sort \$ map (flip (-^) per) es)

and is there already a function which does that ?

4. scheman:
Yes, that code looks safe to me, and seems to work fine. Incidentally, you can replace "(flip (.^) per)" with "(.^ per)".
I don't currently have a function to do that. I'm curious to know what you want to use it for. (My guess is that you're searching for non-isomorphic graphs - if so, I have some code in the labs that might interest you.)

5. my goal is to study http://en.wikipedia.org/wiki/Pólya_enumeration_theorem
with Haskell. For the moment, I have developped a symbolic library to manipulate multivariate polynomials (deriving from Num) for the computation of the cycle index functions Z and I'm browsing your library in search for useful complements.

6. Ah, well in that case, you might be interested to know:
- HaskellForMaths has code for multivariate polynomials, in Math.Algebra.Commutative.MPoly
- I did write code for Polya counting in an earlier version of the HaskellForMaths code, which is described at http://www.polyomino.f2s.com/david/haskell/polyacounting.html
- I have ported the core of it to HaskellForMaths, but not yet published.

But it's always more fun to work out the code for yourself - so good luck.

7. Great, thanks!