4
$\begingroup$

I've implemented the Schreier-Sims algorithm. My sources indicate that a next useful step is to use this structure to prune a backtracking search of group elements, which should yield an improvement on exhaustively searching the group. I think I can see how to approach the problem of finding a (nontrivial) graph automorphism via a search of the full group $S_n$, though I haven't done it yet. My question is how to use the stabilizer chain structure to prune a centralizer search and/or a conjugacy test.

For the sake of discussion, all group elements below are permutations of $n$ points and permutations compose right-to-left, the usual convention in mathematical contexts. A stabilizer chain for a group $G$ is a subgroup series

$$ S_n \ge G = G^{(0)} > G^{(1)} > \dots > G^{(m)} = \langle 1 \rangle $$

where for $i=1 \ldots m$, $G^{(i)}$ is the largest subgroup of $G^{(i-1)}$ stabilizing some point $\beta_i$ (distinct for distinct $i$). So every permutation in $G^{(i)}$ has $\beta_i$ as a fixed point, hence it also fixes $\beta_1, \beta_2, \ldots \beta_{i-1}$. As a consequence of this structure, every element of $G$ can be written inductively $g = h_1 h_2 \dots h_m $ where $h_i$ is a coset representatives of $G^{(i)}$ in $G^{(i-1)}$. These coset representatives are readily available because they are elements of a transversal for the orbit of $\beta_i$ under the permutation action of $G^{(i-1)}$, which was computed during Schreier-Sims.

The general idea of backtracking search is to conditionally eliminate the entire coset $\left( h_1 h_2 \ldots h_i \right) G^{(i)}$ from consideration by inspecting the partial product $h_1 h_2 \dots h_i$ for some task-specific property. The partial product fully determines the image of points $\beta_1, \beta_2, \ldots, \beta_i$ under the entire coset because those points are fixed by $G^{(i)}$. In the case of graph automorphism search, the coset may be skipped if $h_{i}$ permutes the $\beta_{i}$-labeled vertex in a way that violates the graph structure: if there is (or is not) an edge between vertices labeled by $\beta_i$ and $\beta_j$, there should (or should not) be an edge between vertices labeled by their image under $h_1 h_2 \ldots h_i$.

I can't really see the corresponding test for a centralizer search, but it must be fairly obvious because I haven't found an explicit description of it. Sympy has an implementation in sympy.combinatorics.perm_groups.PermutationGroup, but I haven't deciphered what exactly it's doing. Something like GAP must also have an implementation, but I'm even less familiar with that language and haven't located it in the source code.

$\endgroup$
  • $\begingroup$ This is too complicated to explain here. You could try Hulpke's notes on computational group theory www.math.colostate.edu/~hulpke/CGT/cgtnotes.pdf - look at the section on backtrack algorithms starting on page 29. For a more detailed treatment try the book by Seress on computation in permutation groups, or the book by Holt, Eick and O'Brien on computational group theory. $\endgroup$ – Derek Holt Feb 3 '18 at 21:00
  • $\begingroup$ I suppose I should clarify that I'm already working off of Alexander Hulpke's notes. I don't see how to generalize the example given on page 31 because it is too small. What general test does one use on the partial base image to determine whether to prune the coset? This seems like a question that can be answered simply using only familiarity with group theory or permutations, even if there may be other more involved and more efficient ways to find the answer. $\endgroup$ – dcrewi Feb 4 '18 at 19:05
  • $\begingroup$ If you are calculating the centralizer of $x$, you know that for any $g \in C_G(g)$, if $\alpha^g=\beta$, then the cycle lengths of $\alpha$ and $\beta$ in $x$ must be the same. Also, you can deduce the images under $g$ of all other points in the cycle of $\alpha$. For example if $x$ has cycles $(1,2,3,4,5)$ and $(6,7,8,9,10)$ and $1^g=6$, then $2^g=7$, $3^g=8$, etc. So if $1$ is a base point then it is a good idea to chose as many of $2,3,4,5$ as base points as possible. $\endgroup$ – Derek Holt Feb 4 '18 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.