[Nauty-list] elements of the automorphism group

[Mathieu Dutour]

About the generation itself, there is a theory of generation, which allow
to iterate over the group elements. It is explained in such texts as
"Permutation group algorithms" by Seress and implemented in such programs
as GAP, magma.

So, depending on what you want, here are some possible solutions.
1> Use GAP (which has an interface to nauty) and get the automorphism
group. Then do
  for eElt in GRP
  do
    ...
  od;

2> do simple generation of all elements without using the tree search.
Much slower but easily programmable in C.

3> Implement the Schreier Sims theory in the language you need.
It is unfortunate that the only implementation I know of permutation
group algorithms are in GAP, magma and there is no C library available.

Anyway, here is a first sketch at how this can be done:
--From the list of generators of G acting on [0...n], we can determine
  easily and efficiently the orbits of elements of [0..n].
--From the list of generators of G, we can determine a list of generators
  of the stabilizer H=G.0 of 0 by G.
  The problem is that the number of generators grows quadratically
--The method is then to get a sequence of stabilizers.
  {1}=Hm \subset Hm-1 \subset ... \subset H1 \subset H0=G.
  and the tree search is then provided.

So, pick your poison! Personally I tend to like GAP, which is pleasant
to use and use C only when speed I have requirements.

  Mathieu


On Wed, Dec 05, 2007 at 06:20:03PM +0100, Juan Felipe Carrasquilla wrote:
>> Dear All,
>> 
>> I am a newcomer in the list. I am trying to use nauty to link it to a
>> quantum monte carlo code to generate the all the symmetries of the
>> lattices we deal with. The lattices ( and the boundary conditions as well)
>> can be pictured using graphs so this is why we think nauty could be very
>> useful.
>> 
>> Nauty provides the information of the automorphism group of a graph in the
>> form of a set of generators, the size of the group, and the orbits of the
>> group. For our application, it would be desirable to have, instead of the
>> generators and the orbit, the full group components. I have little
>> background in group theory but as far as I understand I can generate all
>> the components of the group by using the generating set X and a finite
>> product of elements of it and their inverses. What I do not know is how to
>> generate those combinations of the elements of the generating set with the
>> information provided by nauty, namely the generating set, the orbits of
>> the groups and the size of the group.
>> 
>> Is nauty able to provide the information of the automorphism group by
>> listing all the elements?
>> 
>> If not, is there a systematic way to generate the elements  with the
>> information provided by nauty? (this might not be a good question for this
>> list but if anyone can help me I would be grateful)
>> 
>> Thanking you,
>> 
>> Juan
>> 
>> 
>> ----------------------------------------------------------------
>>   SISSA Webmail https://webmail.sissa.it/
>>   Powered by SquirrelMail http://www.squirrelmail.org/
>> 
>> 
>> _______________________________________________
>> Nauty-list mailing list
>> Nauty-list at cs.anu.edu.au
>> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list