Permutation Group Notes

These notes explain some important algorithms for computing with permutation groups. They build up, chapter by chapter, to an efficient algorithm for intersecting two permutation groups — a problem with no easy answer, which combines a surprising amount of mathematics and programming.

Along the way we cover two important supporting ideas: stabiliser chains (the basic data structure for computing with permutation groups) and graph isomorphism in the style of McKay’s nauty (the backtrack search here directly inspires what we need for group intersection).

These notes come with no promises of correctness; comments and requests for extensions are welcome.

Chapters

1. Introduction — groups via puzzles.
2. Permutations in Practice — cycle notation, the ball group in GAP, orbits, stabilisers.
3. Stabiliser Chains — Schreier vectors and the main data structure for computing with permutation groups.
4. Ordered Partitions — data structures for partition backtracking.
5. Graph Isomorphism — a McKay-style graph isomorphism tester.
6. Intersection — basic backtracking, search reduction, and making it fast.
7. Appendix — building GAP, testing, profiling.