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?
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?
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.