Efficiently computing Orbital Graphs

by Markus Pfeiffer

Or­bital 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 orbital graph of G with base pair (\alpha, \beta).

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 com­pu­ta­tion

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

1
2
3
4
5
6
7
Or­bital­Graphs := func­tion(G)
  lo­cal base­pairs;

  base­pairs := Arrange­ments([1..Largest­Moved­Point(G)], 2);

  re­turn List(base­pairs, bp -> Di­graph­By­Edges(Or­bit(G, bp, On­Tu­ples)));
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 := Or­bital­Graphs(Prim­i­tive­Group(100,2));;
gap> time;
169626
gap> Length(og);
9900

Clev­er­er con­struc­tion

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
Or­bital­Graphs := func­tion(G)
    lo­cal or­bits, omega, o, oo, graphs;

    omega := [1..Largest­Moved­Point(G)];

    or­bits := Or­bits(G, omega);
    graphs := [];

    for o in or­bits do
        for oo in Or­bits(Sta­bi­liz­er(G, o[1], omega)) do
            Add(graphs, Or­bit(G, [o[1], oo[1]], On­Tu­ples));
        od;
    od;
    re­turn 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
Or­bital­Graphs := func­tion(G)
    lo­cal or­bits, omega, o, oo, graph, graphs;

    omega := [1..Largest­Moved­Point(G)];

    or­bits := Or­bits(G, omega);
    graphs := [];

    graph := List(omega, x -> []);
    for o in or­bits do
        for oo in Or­bits(Sta­bi­liz­er(G, o[1], omega)) do
           graph := List(omega, x -> []);
           graph{o} := List(o, pt -> On­Tu­ples(oo, Rep­re­sen­ta­tive­Ac­tion(G, o[1], pt)));
           Add(graphs, Di­graph(graph));
        od;
    od;
    re­turn 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.

Bib­li­og­ra­phy

[1]Christo­pher Jef­fer­son and Markus Pfeif­fer and Re­bec­ca Waldeck­er, New re­fin­ers for per­mu­ta­tion group search, Jour­nal of Sym­bol­ic Com­pu­ta­tion 92, pp. 70–92, 2019