gap> LoadPackage("grape"); Loading GRAPE 4.2 (GRaph Algorithms using PErmutation groups), by L.H.Soicher@qmul.ac.uk. true gap> Read("/usr/local/gap4r4/pkg/grape/grh/McL"); gap> M:=McL;; # the McLaughlin graph gap> G:=AutGroupGraph(M);; # Aut(M) gap> Factors(Size(G)); [ 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 5, 5, 5, 7, 11 ] gap> M:=NewGroupGraph(G,M);; # now M is a G-graph gap> GlobalParameters(M); [ [ 0, 0, 112 ], [ 1, 30, 81 ], [ 56, 56, 0 ] ] gap> K:=CompleteSubgraphs(M,-1,2); # the max. cliques of M, up to the action of G [ [ 1, 30, 122, 258, 269 ] ] gap> K:=CompleteSubgraphs(M,5,2); # similarly, for the 5-cliques [ [ 1, 30, 122, 258, 269 ] ] gap> K:=K[1];; gap> ForAll(Difference(Vertices(M),K),x-> # checking the > Length(Intersection(K,Adjacency(M,x)))=2); # alpha-condition for K true gap> fivecliques:=Immutable(Set(Orbit(G,K,OnSets)));; # set of all 5-cliques gap> Length(fivecliques); 15400 gap> H:=Stabilizer(G,fivecliques[1],OnSets);; gap> suborbs:=List(Orbits(H,fivecliques,OnSets),Set);; gap> List(suborbs,Length); [ 1, 90, 1215, 11664, 2430 ] gap> reps:=List(suborbs,x->x[1]);; # suborbit reps for 5-cliques gap> List(reps,x->Size(Intersection(reps[1],x))); [ 5, 2, 1, 0, 0 ] gap> H:=List(reps,x->Stabilizer(G,x,OnSets));; gap> T:=List(H,x->Centre(DerivedSubgroup(x)));; # subgroups corr. to suborbit reps gap> List(T,Size); [ 3, 3, 3, 3, 3 ] gap> # check 1-1 correspondence between T and reps gap> ForAll([1..Length(T)],i->reps[i]= > Union(Filtered(Orbits(T[i],[1..275]),x->Length(x)=1))); true gap> gens:=List(T,x->First(GeneratorsOfGroup(x),y->Order(y)=3));; gap> TT:=List(gens,x->Group(x,gens[1]));; gap> List(TT,Size); [ 3, 9, 24, 375, 120 ] gap> # now recognize the groups TT[2],...,TT[5]. gap> IsElementaryAbelian(TT[2]); true gap> List(Elements(TT[2]),x->Number([1..275],y->y=y^x)); [ 275, 14, 5, 5, 5, 5, 14, 14, 14 ] gap> IdGroup(TT[3])=IdGroup(SL(2,3)); true gap> IdGroup(SylowSubgroup(TT[4],5))=IdGroup(ExtraspecialGroup(125,5)); true gap> IdGroup(TT[5])=IdGroup(SL(2,5)); true gap> Runtime(); # in milliseconds 7320 gap> # gap> # Now eliminate certain conjugacy class representatives of subgroups gap> # of G as possible groups of automorphisms of a McLaughlin geometry. gap> # gap> C:=ConjugacyClasses(G);; gap> C:=Set(List(C,x->Subgroup(G,[Representative(x)])));; gap> C:=Filtered(C,x->Size(x)>1 and (Size(x)=2 or IsOddInt(Size(x))));; gap> Collected(List(C,Size)); [ [ 2, 2 ], [ 3, 2 ], [ 5, 2 ], [ 7, 1 ], [ 9, 1 ], [ 11, 1 ], [ 15, 1 ] ] gap> Runtime(); # in milliseconds 10490 gap> Unbind(M.names); gap> linesize:=5; 5 gap> for H in C do > N:=Normalizer(G,H); > # classify the edges fixed by H, up to the action of N > cM:=CollapsedCompleteOrbitsGraph(H,M,N); > wts:=List(VertexNames(cM),Length); > K:=CompleteSubgraphsOfGivenSize(cM,2,2,false,true,wts); > fixededgereps:=List(K,x->Union(List(x,y->VertexName(cM,y)))); Syntax error: warning: unbound global variable fixededgereps:=List(K,x->Union(List(x,y->VertexName(cM,y)))); ^ > if fixededgereps<>[] then > Print("\nSize(H)=",Size(H)," Size(N)=",Size(N)); > # determine the set of all edges fixed by H > fixededges:=Union(Orbits(N,fixededgereps,OnSets)); > Print(" Size(fixededges)=",Size(fixededges)); > # classify the linesize-cliques fixed by H, up to the action of N > K:=CompleteSubgraphsOfGivenSize(cM,linesize,2,false,true,wts); > fixedcliquesreps:=List(K,x->Union(List(x,y->VertexName(cM,y)))); Syntax error: warning: unbound global variable fixedcliquesreps:=List(K,x->Union(List(x,y->VertexName(cM,y)))); ^ > # determine the set of all linesize-cliques fixed by H > fixedcliques:=Union(Orbits(N,fixedcliquesreps,OnSets)); > Print(" Size(fixedcliques)=",Size(fixedcliques),"\n"); > wts:=[]; > names:=[]; > for x in fixedcliquesreps do > xwt:=Number(fixededges,y->IsSubset(x,y)); > if xwt>0 then > orb:=Set(Orbit(N,x,OnSets)); > for y in orb do > Add(names,y); > Add(wts,xwt); > od; > fi; > od; > target:=Length(fixededges); > lambda:=Graph(N,names,OnSets, > function(x,y) return Length(Intersection(x,y))<=1; end, true); > Print("lambda order = ",OrderGraph(lambda)); > Print(" VertexDegrees(lambda) = ",VertexDegrees(lambda),"\n"); > isolevel:=0; > K:=CompleteSubgraphsOfGivenSize(lambda,target,isolevel,true,true,wts); > Print("covering of fixed edges exists = ",Length(K)>0,"\n"); > > if Size(H)=9 then > # special case 9A of McLaughlin group > fixededge:=fixededges[1]; > possiblelines:=Filtered(fivecliques,x->Intersection(x,fixededge)<>[]); Syntax error: warning: unbound global variable possiblelines:=Filtered(fivecliques,x->Intersection(x,fixededge)<>[])\ ; ^ > delta:=Graph(Stabilizer(N,fixededge,OnSets),possiblelines,OnSets, > function(x,y) return Length(Intersection(x,y))<=1; end, true); > HH:=Action(H,VertexNames(delta),OnSets); > NN:=delta.group; > cdelta:=CollapsedCompleteOrbitsGraph(HH,delta,NN); > Print("collapsed-delta order = ",OrderGraph(cdelta),"\n"); > Print("collapsed-delta vertex-degrees = ",VertexDegrees(cdelta),"\n"); > isolevel:=0; > K:=CompleteSubgraphsOfGivenSize(cdelta,55,isolevel, > true,true,List(VertexNames(cdelta),Length)); > Print("9A line config. exists = ",Length(K)>0,"\n"); > fi; > fi; > od; Size(H)=2 Size(N)=15840 Size(fixededges)=66 Size(fixedcliques)=110 lambda order = 110 VertexDegrees(lambda) = [ 99 ] covering of fixed edges exists = false Size(H)=5 Size(N)=200 Size(fixededges)=5 Size(fixedcliques)=0 lambda order = 0 VertexDegrees(lambda) = [ ] covering of fixed edges exists = false Size(H)=3 Size(N)=116640 Size(fixededges)=10 Size(fixedcliques)=91 lambda order = 91 VertexDegrees(lambda) = [ 0, 81 ] covering of fixed edges exists = true Size(H)=9 Size(N)=162 Size(fixededges)=1 Size(fixedcliques)=1 lambda order = 1 VertexDegrees(lambda) = [ 0 ] covering of fixed edges exists = true collapsed-delta order = 55 collapsed-delta vertex-degrees = [ 36, 39 ] 9A line config. exists = false Size(H)=3 Size(N)=3888 Size(fixededges)=37 Size(fixedcliques)=10 lambda order = 10 VertexDegrees(lambda) = [ 0 ] covering of fixed edges exists = false Size(H)=2 Size(N)=80640 Size(fixededges)=280 Size(fixedcliques)=56 lambda order = 56 VertexDegrees(lambda) = [ 45 ] covering of fixed edges exists = false gap> Runtime(); # in milliseconds 11530 gap> # gap> # Now prove that no McLaughlin geometry satisfies the Axiom of Pasch. gap> # gap> delta1:=Graph(G,fivecliques,OnSets, > function(x,y) return Length(Intersection(x,y))=1; end, true);; gap> VertexDegrees(delta1); [ 1215 ] gap> delta2:=Graph(G,fivecliques,OnSets, > function(x,y) return Length(Intersection(x,y))=2; end, true);; gap> VertexDegrees(delta2); [ 90 ] gap> gap> PaschClosure := function(delta1edge) > local c,d,i,ind,x,L; > if not IsEdge(delta1,delta1edge) then > Error(" must be an edge of delta1"); > fi; > c:=delta1edge[1]; > d:=delta1edge[2]; > x:=Intersection(VertexName(delta1,c),VertexName(delta1,d))[1]; > # the 5-cliques indexed by c and d meet in the point x. > ind:=InducedSubgraph(delta1, > Filtered(Intersection(Adjacency(delta1,c),Adjacency(delta1,d)), > a->not (x in VertexName(delta1,a)))); > L:=[]; > for i in [1..OrderGraph(ind)] do > if Adjacency(ind,i)<>[] then > Add(L,Position(VertexNames(delta1),VertexName(ind,i))); > fi; > od; > L:=Union(L,[c,d]); > if Length(L)<>6 or not IsCompleteGraph(InducedSubgraph(delta1,L)) then > Error("PaschClosure: This shouldn't happen"); > fi; > return L; > end; function( delta1edge ) ... end gap> gap> c:=1; 1 gap> d:=Adjacency(delta1,c)[1]; 11 gap> config:=Immutable(PaschClosure([c,d])); [ 1, 11, 7579, 7799, 13874, 14043 ] gap> S:=Stabilizer(delta1.group,config,OnSets);; gap> Size(S); 2880 gap> Size(Centre(S)); 2 gap> Transitivity(S,config); 6 gap> IdGroup(Kernel(ActionHomomorphism(S,config)))=IdGroup(CyclicGroup(4)); true gap> T:=List(config,x-> > Centre(DerivedSubgroup(Stabilizer(G,VertexName(delta1,x),OnSets))));; gap> U:=Group(List(T,x->First(GeneratorsOfGroup(x),y->Order(y)=3)),());; gap> Size(U); 40320 gap> Size(Centre(U)); 2 gap> U=DerivedSubgroup(U); true gap> gap> H:=Stabilizer(delta1.group,Set([c,d]),OnSets);; gap> Size(H); 192 gap> int:=Intersection(VertexName(delta1,c),VertexName(delta1,d)); [ 1 ] gap> F:=Filtered([1..OrderGraph(delta1)],i->IsSubset(VertexName(delta1,i),int) > and IsEdge(delta1,[c,i]) and IsEdge(delta1,[d,i]));; gap> orbs:=Orbits(H,F);; gap> List(orbs,Length); [ 48, 96, 64, 2 ] gap> reps:=List(orbs,x->x[1]);; gap> for r in reps do > lines:=ShallowCopy(config); > for s in [c,d] do > lines:=Union(lines,PaschClosure([r,s])); > od; > Print("\nLength(lines)=",Length(lines),"\n"); > Print("no. delta1 edges between lines = ", > Length(UndirectedEdges(InducedSubgraph(delta1,lines))),"\n"); > Print("no. delta2 edges between lines = ", > Length(UndirectedEdges(InducedSubgraph(delta2,lines))),"\n"); > oldlines:=lines; > for T in Combinations(oldlines,2) do > if IsEdge(delta1,T) then > lines:=Union(lines,PaschClosure(T)); > fi; > od; > Print("now Length(lines)=",Length(lines),"\n"); > Print("no. delta1 edges between lines = ", > Length(UndirectedEdges(InducedSubgraph(delta1,lines))),"\n"); > Print("no. delta2 edges between lines = ", > Length(UndirectedEdges(InducedSubgraph(delta2,lines))),"\n"); > od; Length(lines)=15 no. delta1 edges between lines = 57 no. delta2 edges between lines = 6 now Length(lines)=35 no. delta1 edges between lines = 255 no. delta2 edges between lines = 34 Length(lines)=15 no. delta1 edges between lines = 57 no. delta2 edges between lines = 0 now Length(lines)=63 no. delta1 edges between lines = 483 no. delta2 edges between lines = 15 Length(lines)=15 no. delta1 edges between lines = 57 no. delta2 edges between lines = 0 now Length(lines)=63 no. delta1 edges between lines = 477 no. delta2 edges between lines = 12 Length(lines)=15 no. delta1 edges between lines = 57 no. delta2 edges between lines = 0 now Length(lines)=21 no. delta1 edges between lines = 105 no. delta2 edges between lines = 0 gap> gap> Runtime(); # in milliseconds 22070 gap> quit;