22
$\begingroup$

When working with large numbers of graphs, a canonical labelling routine is essential as, after the initial cost of canonically labelling each graph, it permits isomorphism checks to be replaced with identity checks.

Currently I am working with large numbers of transitive permutation groups; the degree is small (40ish) but the size of group can be large, and my programs are gumming up due to having to perform large numbers of - not exactly isomorphism - but conjugacy checks. (I need to check each pair of groups to see if they are conjugate in the symmetric group.)

This process would be considerably easier if there was a known way of finding a canonical conjugate of the incoming permutation groups...

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ the question of finding a canonical form of the centraliser ring of a permutation group is already non-trivial to me. I do not know anything better than trying all the orderings of orbitals, canonising each edge-coloured graph you get this way, and pick the maximal. (if the orbitals are "different" in some way, e.g. have different subdegrees, you might use it to restrict to, say, ordering the orbitals wrt subdegrees) The centraliser ring in a canonical form would give you a natural fingerprint for conjugacy. $\endgroup$
    – Dima Pasechnik
    Commented Mar 4, 2012 at 4:46
  • $\begingroup$ I'd also look into what actually happens when you check the conjugacy with your software (GAP? Magma?). Maybe it's doing something dumb... $\endgroup$
    – Dima Pasechnik
    Commented Mar 4, 2012 at 4:50
  • $\begingroup$ Dima, I'm using Magma, but I do not know of any way to determine (directly) whether it is doing anything dumb. I will try and do some experiments and see whether it is doing certain obvious things. $\endgroup$
    – Gordon Royle
    Commented Mar 6, 2012 at 8:02
  • $\begingroup$ Do you actually need canonization, or would a complete invariant suffice for your purposes? Although the two are computationally equivalent for graph isomorphism (there is a polynomial-time canonical labelling algorithm for graphs iff there is a poly-time complete invariant), this seems not to be true in general. So a complete invariant might be easier to find. $\endgroup$
    – Joshua Grochow
    Commented Jul 2, 2013 at 20:28

4 Answers 4

Reset to default
12
$\begingroup$

A quick way to obtain canonical conjugates of permutation groups would of course be nice, but hoping for that may be a bit too optimistic. Rather than trying to go that route, in your situation I would try to reduce the number of pairs of groups to be tested for conjugacy -- and my guess is in practice you can usually obtain quite a big reduction. Concretely, I would compute for each of the groups invariants like the following:

  • group order,

  • primitivity / degree of transitivity,

  • number, sizes, orders of representatives and cycle structures of representatives of conjugacy classes.

The time required for computing these invariants is no longer quadratic, but linear in the number of groups. Finally, only pairs of groups for which all invariants coincide need to be tested for conjugacy.

To give a rough idea of how good the mentioned invariants are in separating non-conjugate groups: the invariants distinguish all non-conjugate transitive permutation groups of degree less than $12$, and among the $301$ non-conjugate transitive permutation groups of degree $12$, there are only $2$ pairs of groups for which the invariants coincide.

Improve this answer
$\endgroup$
10
$\begingroup$

Babai, Codenotti, and Qiao (ICALP 2012 from Babai's homepage, also in Codenotti's thesis) show how to test permutational isomorphism (=conjugacy - but this might be another good phrase to search with) of permutation groups in time that is polynomial in the order of the groups and simply exponential ($c^n$ for fixed $c$) in the size of the permutation domain. From a theoretical perspective, I believe this is the best known.

In the transitive case, the runtime is still simply exponential in the degree but only linear in the order, and in this amount of time they can in fact list all of the permutational isomorphisms. Listing the permutational isomorphisms allows you to pick a canonical labelling by, e.g., lexicographic order. (And $|G|2^{40}$ is way better than the naive bound of $|G|40!$: $2^{40} \approx 10^{12}$, while $40! \approx 10^{48}$.)

Now theoretical bounds on algorithms may not tell you anything about efficiency in practice. (Depending on how large your transitive groups are, even the linear factor of $|G|$ might be too much for you.) It is at least reasonable to think that their algorithm is not only theoretically more efficient but also more efficient in practice than the naive algorithm(s). And of course one can always hope that it will work for your instances anyways, or perhaps with a few additional heuristics.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, conjugate permutation groups are often said to be "isomorphic as permutation groups". $\endgroup$
    – Harry Altman
    Commented Aug 16, 2012 at 19:44
8
$\begingroup$

This seems to be one of the biggest holes in the practical isomorphism arsenal. Various non-trivial possibilities come to mind, but their efficiency relies a lot on a more basic question. Define (and efficiently compute) a total order on labelled finite permutation groups. Thus, for any two permutation groups $G_1,G_2$ given by permutation generators, determine whether $G_1\lt G_2$, $G_1=G_2$ or $G_1\gt G_2$, where $G_1=G_2$ iff they are exactly the same (not just isomorphic) and the order obeys the transitivity law. This is possible in principle: compute the entire groups and compare them lexicographically. But naturally we don't want to compute the entire groups.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Just to mention that it is possible to compare permutation groups in GAP using the < operator or GeneratorsSmallest which gives (from the manual): "two groups via lexicographic comparison of their sorted element lists yields the same relation as lexicographic comparison of their smallest generating sets." $\endgroup$
    – James Mitchell
    Commented Apr 25, 2015 at 17:52
  • $\begingroup$ That's interesting; I need to think about the consequences. $\endgroup$
    – Brendan McKay
    Commented Apr 26, 2015 at 2:28
2
$\begingroup$

In GAP, for transitive permutation groups of degree at most 30 one can use TransitiveIdentification(G) from the package TransGrp by Alexander Hulpke. This gives the index of the (unique!) permutation group in the library that is conjugate to the given permutation group and it is apparently quite fast. See section 13 of

Hulpke, Alexander, Constructing transitive permutation groups., J. Symb. Comput. 39, No. 1, 1-30 (2005). ZBL1131.20003 MR2168238.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It would be wonderful if something similar would be available for all permutation groups! $\endgroup$
    – Martin Rubey
    Commented May 24, 2022 at 10:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .