6
$\begingroup$

Suppose I have a graph like this

and a list of its automorphisms. How do I go about getting a set of generators for this group?

  • 0
    A silly answer is that your list (of every element) is a list of generators, just not a very small one. Finding the exact smallest generating set is hard, but finding "small" ones is often pretty easy, and GAP does a good job of this for your group without even asking it nicely.2011-03-03

1 Answers 1

7

Algorithmically, you take the elements one by one and use them to grow a subgroup. You create strong generating sets so that the size of the subgroup is known and so that membership in the subgroup can be tested easily. You only record a new generator when you get an element not in the current subgroup. You can stop early if you notice the subgroup and the list have the same size (as long as you trust the list is correct).

GAP provides a command AsGroup to convert a list of group elements into a group (which can then be asked for small generating sets). In fact, in this example it fairly automatically finds a good generating set.

Since the list is not too long, you can use:

g := AsGroup( List( myListOfImages, PermList ) ); 

This has some performance problems if the list had more like 10,000 elements, but for small groups like this it is instant. It yields:

Group([ (3,6)(5,7)(8,10), (2,5)(3,4)(7,10)(8,9), (1,2)(3,5)(6,7)(8,10) ]) 

If you like the image list format for permutations:

gap> PrintArray( List( GeneratorsOfGroup(g), ListPerm ) ); [ [   1,   2,   6,   4,   7,   3,   5,  10,   9,   8 ],   [   1,   5,   4,   3,   2,   6,  10,   9,   8,   7 ],   [   2,   1,   5,   4,   3,   7,   6,  10,   9,   8 ] ] 

You can also ask GAP (and grape) directly:

LoadPackage("grape"); Petersen := Graph( SymmetricGroup(5), [[1,2]], OnSets, function(x,y) return Intersection(x,y)=[]; end );; AutomorphismGroup(Petersen); 

The vertices are in a different order than yours, but otherwise everything is good.