# Efficiently computing Orbital Graphs

## by Markus Pfeiffer

Finishing some long overdue work, I was recently benchmarking different ways to compute orbital closures of permutation groups.

## Orbital Closures, and what others call them

Lets first lay down what I am computing.

Suppose that (as per usual) \Omega = \{1..n\} for some n \in \mathbb{N} and G \leq S_{\Omega}.
If we pick two distinct numbers \alpha, \beta \in \Omega, then the graph
\Gamma_{(\alpha,\beta)} = \left<\Omega, \left(\alpha, \beta\right)^G\right> is the

If we now take

\mathcal{OC}(G) = \bigcap\limits_{(\alpha,\beta) \in \Omega^2} \operatorname{Aut}(\Gamma_{(\alpha,\beta)})

of GWhich necessarily contains G, but might be bigger.

## Naive computations

In GAP we could naively compute the group \mathcal{OC}\left(G\right) as follows

1 2 3 4 5 6 7 8 9 10 11 | OrbitalGraphs := function(G) local basepairs; basepairs := Arrangements([1..LargestMovedPoint(G)], 2); return List(basepairs, bp -> DigraphByEdges(Orbit(G, bp, OnTuples))); end; og := OrbitalGraphs(G); ogauts := List(og, AutomorphismGroup); oc := Intersection(ogauts) |

The code above is already unbearably slow for fairly small examples. Our method for computing orbital graphs is not very efficient. In a separate post I describe how we use some basic group theory to make the computation of orbital graphs a lot faster by not computing many graphs that turn out to be isomorphic to a graph that we already computed.

Once we use the more efficient way of computing orbital graphs, and if we happen to use groups with very few distinct orbital graphsit is clear from the algorithm described in ... which type of group that is, we get away with this approach for quite some time.

Trying to compute the orbital closure of G = D_{32} \wr D_{32} makes the wait already quite painful.

Exploring what takes so long in this computation yields some insight: We compute the automorphism group of each orbital graph separately, intersecting the results. Group intersection is a hard problem, though it is no harder than graph automorphism finding.

## Cleverer construction

A slightly cleverer way of computing the orbital closure is not to compute a truckload of graphs, their automorphism groups, and intersecting them, but to just compute one graph with coloured edges, and handing that to a graph automorphism solver. This should of course yield the same result, but using a very efficient graph automorphism finder works a lot better.thanks go to Finn Smith for adding code to the GAP package digraphs to compute automorphisms of edge-coloured digraphs

## Benchmarks in GAP with Digraphs and ferret

Putting this together I did some benchmark comparisons using GAP 4.11, digraphs, and ferret and found that the edge-coloured method is up to a factor of 1000 faster. Hence the new default method in the orbitalgraphs package is using the edge-coloured graph method as a default.

## Sophisticated Algorithms

Write something about Johannes Hahn’s algorithm