[GAP Forum] Computing "canonical" subsets

[Leonard Soicher]

Dear GAP-Forum, 

I must point out that this SmallestImageSet function, which determines
the lex-least set in the G-orbit of a subset S of X (where G is a
permutation group on the finite set X) was designed and written by
Steve Linton. This extremely useful function (which does not need to
compute the G-orbit of S) is used internally within GRAPE, and is not
documented. 

For more information, see pkg/grape/lib/smallestimage.g in your GAP
distribution, and also the article:

Steve Linton, Finding the smallest image of a set,
Proceedings of ISSAC '04, ACM, New York, 2004.  
 
I am hoping that, in due course, Steve will either make this excellent
function (and certain variants he has devised) into a package or part
of the main distribution of GAP.

You may also be interested in: 

Enumerating Set Orbits, by Christian Pech and Sven Reichard, in
Algorithmic Algebraic Combinatorics and Gröbner Bases, Springer, 2009,
Part 1, pp. 137-150.

and in:

On classifying objects with specified groups of automorphisms, friendly
subgroups, and Sylow tower groups, by Leonard H. Soicher; Research Report,
2008, available at http://designtheory.org/library/preprints/friendly.pdf

Regards,
Leonard Soicher

On Wed, Jan 12, 2011 at 01:21:43PM +0100, Mathieu Dutour wrote:
> As far as I know, once you have a backtracking algorithm
> for equivalence/stabilizer, then you have also an algorithm
> for canonical representative.
> 
> But GAP does not provides such functionalities ...
> 
> However, for the special action "OnSets", there is a function
> "SmallestImageSet" available from the GRAPE package that does
> the job.
> 
>   Mathieu
> 
> On Wed, Jan 12, 2011 at 08:04:13PM +0800, Gordon Royle wrote:
> >> 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
> >> _______________________________________________
> >> Forum mailing list
> >> Forum at mail.gap-system.org
> >> http://mail.gap-system.org/mailman/listinfo/forum
> 
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum