# Efficiently computing Orbital Graphs

## by Markus Pfeiffer

## Orbital Graphs

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

Computing the orbital graph for a given pair (\alpha, \beta) is a simple orbit computation, but what if we want to compute the set of all orbital graphs up to isomorphism?

## Naive computation

In GAP we can naively compute the all orbital graphs with the following code.

1 2 3 4 5 6 7 | OrbitalGraphs := function(G) local basepairs; basepairs := Arrangements([1..LargestMovedPoint(G)], 2); return List(basepairs, bp -> DigraphByEdges(Orbit(G, bp, OnTuples))); end; |

Even for fairly tame groups acting on 100 points this will get us 9900 graphs, and 1000 points will give us 999000, many of which will be isomorphic to each other. For example

1 2 3 4 5 | gap> og := OrbitalGraphs(PrimitiveGroup(100,2));; gap> time; 169626 gap> Length(og); 9900 |

## Cleverer construction

Let’s do some neat group theory. Things are computed fastest if one doesn’t compute them at all, so let’s avoid computing all that superflous junk.

The main idea behind the slightly cleverer algorithm is that two orbital graphs \Gamma_{(\alpha, \beta)} and \Gamma_{(\gamma, \delta)} are isomorphic iff there is an element \sigma \in G such that (\alpha, \beta)^\sigma = (\gamma, \delta).This would of course need a short proof To compute one representative per orbit, we first compute the orbits of G on \Omega and then for each of those orbits the orbits of a point stabilizer of one point in the orbit. The resulting code looks like this

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | OrbitalGraphs := function(G) local orbits, omega, o, oo, graphs; omega := [1..LargestMovedPoint(G)]; orbits := Orbits(G, omega); graphs := []; for o in orbits do for oo in Orbits(Stabilizer(G, o[1], omega)) do Add(graphs, Orbit(G, [o[1], oo[1]], OnTuples)); od; od; return graphs; end; |

This cuts down the computation time enough so that we can deal with groups acting on 1000 points or more, but we can still do better, as we can save ourselves the computation of the orbits of G on \Omega^2.

We do this because we know that for any basepair (\alpha, \beta) the orbit under G acting on pairs consists of pairs where the first entry is in the orbit of \alpha under G, and the second point is in the orbit of \beta under the point stabilizer of \alpha in G, conjugated by the element of G that takes \alpha to its image in its orbit.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | OrbitalGraphs := function(G) local orbits, omega, o, oo, graph, graphs; omega := [1..LargestMovedPoint(G)]; orbits := Orbits(G, omega); graphs := []; graph := List(omega, x -> []); for o in orbits do for oo in Orbits(Stabilizer(G, o[1], omega)) do graph := List(omega, x -> []); graph{o} := List(o, pt -> OnTuples(oo, RepresentativeAction(G, o[1], pt))); Add(graphs, Digraph(graph)); od; od; return graphs; end; |

Slightly more advanced versions of orbital graph computations could filter out irrelevant orbital graphs early. I will leave this as an exercise for the reader (at least for now).

The ideas above have been employed in [1] to efficiently compute orbital graphs.

## Bibliography

[1] | New refiners for permutation group search, Journal of Symbolic Computation 92, pp. 70–92, 2019 , |