Frequently Asked Questions

GAP is suited very well for computing in combinatorial structures and permutation groups. A small but nevertheless illustrative example given by Stefan Kohl in an answer to a letter to 'gap-support' is the investigation of the automorphism group of a graph whose vertices are the cards of a card game called Duo with edges between any two cards that 'fit together'.

The game `Duo' consists of 4^3 = 64 `normal' cards each showing a triple (colour, shape, number), where there are four possible colours, shapes and numbers (any possible combination occurs exactly once) and 3*4 = 12 jokers each showing either a colour, a shape or a number. Two `normal' cards fit together if and only if they coincide in two of their symbols. E.g. (red, square, 1) and (green, square, 1) fit together, but (red, square, 1) and (red, triangle, 3) do not. A joker fits together with a `normal' card if one of the three symbols of the latter is the joker's, e.g. the (blue) joker fits together with (blue, triangle, 4). Two jokers never fit together.

Although this may look a bit complicate, formulating it in the GAP language is quite easy. For constructing the graph we use the GAP package GRAPE by Leonard Soicher:

gap> LoadPackage("grape"); # Construct the Duo graph with 4^3 + 12 = 76 vertices:
gap> vertices := Concatenation(List(Tuples([0..3],3),t->t+[0,4,8]),
>                              List([0..11],i->[i]));
gap> TrivialAction := function ( x, g ) return x; end;;
gap> Relation := function ( x, y )
>      return Length(Intersection(x,y)) = 2
>             or    (Length(x) = 1 or Length(y) = 1)
>                and Length(Intersection(x,y)) = 1 and x <> y;
>    end;;
gap> Gamma := Graph(Group(()),vertices,TrivialAction,Relation,true);;

We compute the automorphism group, again using GRAPE:

gap> G := AutGroupGraph(Gamma);
<permutation group with 9 generators>
gap> time; # time in ms
20
gap> DegreeAction(G); # Check: we really have 4^3 + 3*4 = 76 vertices.
76

The automorphism group acts transitively both on the `normal' cards and on the jokers, but a `normal' card cannot be mapped onto a joker or vice versa:

gap> orb := Orbits(G,[1..76]); # Compute the orbits on the set of vertices.
[ [ 1, 2, 3, 5, 4, 9, 17, 6, 13, 33, 10, 18, 7, 49, 14, 34, 11, 19, 21, 8,
       50, 15, 35, 37, 12, 20, 25, 22, 51, 53, 16, 36, 41, 38, 29, 26, 23, 52,
       57, 54, 45, 42, 39, 30, 27, 24, 61, 58, 55, 46, 43, 40, 31, 28, 62, 59,
       56, 47, 44, 32, 63, 60, 48, 64 ],
   [ 65, 69, 73, 74, 75, 70, 76, 71, 66, 72, 67, 68 ] ]
gap> List(orb,Length);
[ 64, 12 ]

The action of the automorphism group on the `normal' cards is primitive, but the one on the jokers is not:

gap> G1 := Action(G,orb[1]); # The action of G on the first orbit.
<permutation group with 9 generators>
gap> G2 := Action(G,orb[2]); # The action of G on the second orbit.
<permutation group with 9 generators>
gap> IsPrimitive(G1,MovedPoints(G1));
true
gap> IsPrimitive(G2,MovedPoints(G2));
false

Both actions are faithful:

gap> Size(G);
82944
gap> List([G1,G2],Size);
[ 82944, 82944 ]

The automorphim group is solvable, but not nilpotent:

gap> Factors(Size(G));
[ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3 ]
gap> IsSolvable(G);
true  # Obvious (by Burnside's Theorem).
gap> IsNilpotent(G);
false
gap> List(LowerCentralSeries(G),Size);
[ 82944, 20736 ]
gap> List(DerivedSeries(G),Size);
[ 82944, 20736, 6912, 1728, 64, 1 ]

The action of the automorphism group on the jokers is the imprimitive action of the wreath product of the symmetric group of degree 4 and the symmetric group of degree 3 on 3*4 = 12 points, and the action of the automorphism group on the `normal' cards is the primitive action of this wreath product on 4^3 = 64 points:

gap> GeneratorsOfGroup(G2);
[ (1,2)(6,9)(8,11)(10,12), (2,3)(4,6)(5,8)(7,10), (3,4), (4,5), (5,7), (6,8),
(8,10), (9,11), (11,12) ]
gap> H := TransitiveGroup(12,TransitiveIdentification(G2)); 
# Group structure in human-readable form
[S(4)3]S(3)=S(4)wrS(3)  
gap> Size(H); # A check.
82944
gap> 6*24^3; # dito.
82944
gap> W := WreathProduct(Group((1,2),(1,2,3,4)),Group((1,2),(1,2,3)));
<permutation group of size 82944 with 8 generators>
gap> phi := IsomorphismGroups(G,W);   # A concrete isomorphism.
[ (1,21,6,26,11,19)(2,25,7,18,9,23)(3,17,5,22,10,27)(4,29,8,30,12,31)(13,24,
     14,28,15,20)(16,32)(33,53,38,58,43,51)(34,57,39,50,41,55)(35,49,37,54,42,
     59)(36,61,40,62,44,63)(45,56,46,60,47,52)(48,64)(65,66)(67,68)(69,73,70,
     74,71,75)(72,76), (1,46,7,29,35,22)(2,14,15,31,19,18)(3,30)(4,62,11,32,51,
     26)(5,45,39,21,33,38)(6,13,47,23,17,34)(8,61,43,24,49,42)(9,48,55,25,36,
     54)(10,16,63,27,20,50)(12,64,59,28,52,58)(40,53,41)(44,56,57)(65,72,75,66,
     69,74)(67,70,73)(68,71,76) ] -> [ (1,2)(3,4)(5,9,8,10,7,12)(6,11),
   (1,9,5)(2,10,6)(3,11,7,4,12,8) ]