[GAP Forum] Computing "canonical" subsets

Gordon Royle gordon at maths.uwa.edu.au
Wed Jan 12 12:04:13 GMT 2011


Dear Gapsters..

Consider the following generic problem... given a permutation group G acting on a set X, I have a (potentially) large collection of k-subsets of X and wish to keep only one representative of each G-orbit on k-subsets.

GAP can tell me if two k-subsets are equivalent under G using RepresentativeAction and so in principle, I can build up a list by starting with the first one, then testing to see if the second is equivalent to the first and keeping it only if it is not, and so on. This works, but each new one requires one more test than the previous one and things rapidly become unmanageable.

For winnowing large lists of graphs, the standard procedure is not to test them pairwise but rather to compute a "canonically labelled" version of each input graph and then simply throw out the duplicates...

Is there any way of computing a "canonically labelled" version of each k-subset? Or is this well known to be more difficult than computing equivalence?

Thanks

Gordon


More information about the Forum mailing list