[GAP Forum] Looking for automorphisms of triple steiner systems

Leonard Soicher L.H.Soicher at qmul.ac.uk
Mon Mar 22 17:53:04 GMT 2010


Dear Forum, 

I would suggest making use of the DESIGN package and its 
function to compute the automorphism group of a block 
design, as illustrated in the logfile, below.
The DESIGN package uses GRAPE for this computation, which
in turn makes use of Brendan McKay's nauty package, and so
this will only work on a Unix system on which GAP, GRAPE 
and DESIGN have been fully installed.

Regards,
Leonard

gap> LoadPackage("design");

Loading  GRAPE 4.3  (GRaph Algorithms using PErmutation groups),
by L.H.Soicher at qmul.ac.uk.

-----------------------------------------------------------------------------
Loading  DESIGN 1.4 (The Design Package for GAP)
by Leonard H. Soicher (http://www.maths.qmul.ac.uk/~leonard/).
-----------------------------------------------------------------------------
true
gap> st:=[ [ 2, 4, 11 ], [ 7, 10, 12 ], [ 3, 8, 10 ], [ 2, 6, 12 ], [ 3, 6, 13 ], [
> 1, 6, 10 ], [ 5, 11, 13 ], [ 1, 2, 3 ],
>   [ 3, 4, 9 ], [ 5, 7, 8 ], [ 3, 7, 11 ], [ 4, 8, 12 ], [ 1, 8, 13 ], [ 5,
> 6, 9 ], [ 9, 12, 13 ], [ 1, 7, 9 ],
>   [ 2, 5, 10 ], [ 2, 7, 13 ], [ 2, 8, 9 ], [ 6, 8, 11 ], [ 9, 10, 11 ], [ 4,
> 10, 13 ], [ 1, 11, 12 ], [ 1, 4, 5 ],
>   [ 4, 6, 7 ], [ 3, 5, 12 ] ];;
gap> S:=BlockDesign(13,st);
rec( isBlockDesign := true, v := 13, 
  blocks := [ [ 1, 2, 3 ], [ 1, 4, 5 ], [ 1, 6, 10 ], [ 1, 7, 9 ], 
      [ 1, 8, 13 ], [ 1, 11, 12 ], [ 2, 4, 11 ], [ 2, 5, 10 ], [ 2, 6, 12 ], 
      [ 2, 7, 13 ], [ 2, 8, 9 ], [ 3, 4, 9 ], [ 3, 5, 12 ], [ 3, 6, 13 ], 
      [ 3, 7, 11 ], [ 3, 8, 10 ], [ 4, 6, 7 ], [ 4, 8, 12 ], [ 4, 10, 13 ], 
      [ 5, 6, 9 ], [ 5, 7, 8 ], [ 5, 11, 13 ], [ 6, 8, 11 ], [ 7, 10, 12 ], 
      [ 9, 10, 11 ], [ 9, 12, 13 ] ] )
gap> AllTDesignLambdas(S); 
[ 26, 6, 1 ]
gap> G:=AutomorphismGroup(S);
Group([ (1,7,9)(2,11,4)(5,13,10)(6,8,12), (4,11)(5,12)(6,10)(7,9)(8,13) ])
gap> Size(G);
6
gap> 

On Mon, Mar 22, 2010 at 11:36:12AM -0600, Alexander Hulpke wrote:
> 
> 
> Dear Forum,
> 
> Mbg Nimda asked:
> 
> > I'm trying to determine the automorphism group of Steiner(2,3,13) but I get
> > a memory exceeded error.
> > Here is the session:
> > 
> > gap> st;
> > [ [ 2, 4, 11 ], [ 7, 10, 12 ], [ 3, 8, 10 ], [ 2, 6, 12 ], [ 3, 6, 13 ], [
> > 1, 6, 10 ], [ 5, 11, 13 ], [ 1, 2, 3 ],
> >  [ 3, 4, 9 ], [ 5, 7, 8 ], [ 3, 7, 11 ], [ 4, 8, 12 ], [ 1, 8, 13 ], [ 5,
> > 6, 9 ], [ 9, 12, 13 ], [ 1, 7, 9 ],
> >  [ 2, 5, 10 ], [ 2, 7, 13 ], [ 2, 8, 9 ], [ 6, 8, 11 ], [ 9, 10, 11 ], [ 4,
> > 10, 13 ], [ 1, 11, 12 ], [ 1, 4, 5 ],
> >  [ 4, 6, 7 ], [ 3, 5, 12 ] ]
> > gap>
> > gap>
> > gap> g:=SymmetricGroup(13);
> > Sym( [ 1 .. 13 ] )
> > gap> h:=Stabilizer(g,st,OnSetsSets);
> 
> First, `st' should be sorted to be a set:
> st:=Set(st);
> 
> Then, alas, the OnSetsSets action only does a naive orbit algorithm, and has no backtrack implementation. The stabilizer calculation therefore needs to form the whole orbit, which is unlikely to succeed.
> 
> The best way to deal with this would be to use the GRAPE package, encode the steiner system in a graph and use the graph automorphism function.
> 
> Alternatively (as 13 choose 3= 286 is still small), you could take the action on 3-sets, and in this action compute a set stabilizer (a single set stabilizer has a backtrack implementation and therefore much faster):
> 
> gap> comb:=Combinations([1..13],3);;
> gap> act:=ActionHomomorphism(g,comb,OnSets,"surjective");
> <action epimorphism>
> 
> Now translate st to a set of points in this action of degree 286
> gap> stp:=Set(List(st,x->Position(comb,x)));
> [ 1, 22, 42, 47, 56, 64, 83, 90, 99, 106, 107, 126, 137, 145, 149, 153, 175, 
>   191, 199, 205, 210, 229, 239, 262, 277, 282 ]
> 
> stabilize, and transfer back to S13:
> gap> u:=Stabilizer(Image(act),stp,OnSets);
> <permutation group of size 6 with 2 generators>
> gap> u:=PreImage(act,u);
> Group([ (4,11)(5,12)(6,10)(7,9)(8,13), (1,9)(2,4)(5,8)(6,13)(10,12) ])
> 
> I hope this helps,
> 
>    Alexander Hulpke
> 
> -- Colorado State University, Department of Mathematics,
> Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
> email: hulpke at math.colostate.edu, Phone: ++1-970-4914288
> http://www.math.colostate.edu/~hulpke
> 
> 
> 
> 
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum



More information about the Forum mailing list