# All you need is graphs (to compute orbital closures in GAP).

## 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

Let’s first lay down what I am computing. I have referred to Orbital Graphs before.

Suppose that \Omega = \{1..n\} for some n \in \mathbb{N} and G \leq S_{\Omega}.

We consider all

\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 using the package digraphs, and optionally ferret, one can naively compute the group \mathcal{OC}\left(G\right) as follows

1 2 3 4 5 6 | OrbitalClosure := function(G) local ogs, ogauts; ogs := OrbitalGraphs(G); ogauts := List(ogs, AutomorphismGroup); return Intersection(ogauts); end; |

The code above becomes unbearably slow if we maliciously produce examples of groups with a decent number of orbital graphs, such as direct products of isomorphic groups or even a wreath product.

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, where the edges represent which orbital graph it belongs to, 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 when one calls `OrbitalClosure(G)`

.

The following table shows the computation time (in milliseconds) for the orbital closure of D_{32} \wr D_{2n} for n \in \{4 \ldots 11\}. The second column contains the number of distinct orbital graphs.

n | #orbital graphs | intersect | edge-coloured |

4 | 10 | 588.818 | 7.810 |

5 | 10 | 876.719 | 9.932 |

6 | 11 | 2311.209 | 15.972 |

7 | 11 | 103966.205 | 21.423 |

8 | 12 | 301819.541 | 34.307 |

9 | 12 | 445608.635 | 34.193 |

10 | 13 | 824163.351 | 42.039 |

11 | 13 | 1657053.153 | 65.100 |

As a disclaimer it should be said that this comparison is to a degree probably unfair, as GAP spends a

## Even more sophistication?

In a future post I will be looking at Johannes Hahn’s suggested pull request for the orbitalgraphs package to improve performance more by avoiding more graphs.