LogTo("pg_gap2.log");
####################################################################
# #
# This is the GAP example from Chapter 3 of "Permutation Groups", #
# by Peter J. Cameron, Cambridge University Press 1999. #
# #
# The purpose is to construct the unique Moore graph having #
# diameter 2 and valency 7 on 50 vertices, the so-called #
# Hoffman-Singleton graph, and investigate its automorphism group #
# and some other graphs and groups built from it. #
# #
# GAP will run with this file as input, but only the last commands #
# produce any output. To see the whole thing, copy the #
# non-comment lines to the GAP prompt. #
# #
# If you are running GAP under LINUX, you can issue the command #
# gap < pg_gap2.txt #
# (where pg_gap2.txt is the name of this file) #
# and you will produce a log file pg_gap2.log which will contain #
# all of this file with the output in the appropriate place! #
# I don't know how to do this with other operating systems. #
# The options #
# gap pg_gap2.txt #
# or #
# Read("pg_gap2.txt"); # while GAP is running #
# will NOT work. #
# #
# I have suppressed some very long output. This can be #
# reinstated by changing ;; to ; #
# #
####################################################################
#
# Load the GRAPE package
#
RequirePackage("grape");
#
# Construct a function for a group action on sets of sets, etc.
#
OnSetsRecursive:=function(x,g)
if not IsSet(x) then
return x^g; # this is the action of
# permutation g on point x
else
return Set(List(x, y -> OnSetsRecursive(y,g)));
fi;
end;
#
# The adjacency rule for the Hoffman-Singleton graph, as
# constructed in the book:
# the vertices are the 3-subsets of 1..7
# together with an A_7 orbit on projective planes;
# two 3-sets are adjacent if they are disjoint;
# a 3-set and a plane are adjacent if the 3-set is a line of the plane.
#
HSAdjacent:=function(x,y)
if IsInt(x[1]) then # x is a 3-set
if IsInt(y[1]) then # y is a 3-set
return Intersection(x,y)=[]; # join if disjoint
else # or y is a projective plane
return x in y; # join if x is a line of y
fi;
else # or x is a projective plane
if IsInt(y[1]) then # and y is a 3-set
return y in x; # join if y is a line of x
else # or y is a projective plane
return false; # don't join
fi;
fi;
end;
#
# Here is a starting projective plane
#
Pi:=Set([[1,2,4],[2,3,5],[3,4,6],[4,5,7],
[1,5,6],[2,6,7],[1,3,7]]);
#
# Construct the graph using GRAPE's graph constructor
#
HofSingGraph:=Graph(AlternatingGroup(7),
[[1,2,3], Pi],
OnSetsRecursive,
HSAdjacent);;
#
# and now the group is the automorphism group of the graph
# (this uses the GAP4 command AutomorphismGroup - if you are
# using GAP3, you should upgrade, but you can use the command
# AutGroupGraph instead)
#
HofSingGroup:=AutomorphismGroup(HofSingGraph);
#
# and we can update the group of the graph to speed things up
#
HofSingGraph := NewGroupGraph(HofSingGroup,HofSingGraph);;
#
# We recognise a specific coclique as the set of planes in our
# original construction of the graph
#
IsPlane:=function(x)
return not IsInt(VertexName(HofSingGraph,x)[1]);
end;
#
Coclique:=Set(Filtered(Vertices(HofSingGraph),IsPlane));
#
# and construct the 100 images of this set under the group
#
Cocliques:=Orbit(HofSingGroup, Coclique, OnSets);;
#
# This code calculates the number of cocliques meeting a given one
# in any given number of vertices
#
IntList:=Collected(List(Cocliques,
x -> Size(Intersection(x,Coclique))));
#
# Now we construct several 100-vertex graphs on the set of cocliques
# where the joining rules are specified by a list of intersection sizes
#
Joined:=function(x,y,L) # L is a list of intersection sizes
return Size(Intersection(x,y)) in L;
end;
#
J0:=function(x,y)
return Joined(x,y,[0]);
end;
#
Graph0:=Graph(HofSingGroup, [Coclique], OnSets, J0);;
#
# Graph0 is isomorphic to the disjoint union of two copies
# of the Hoffman-Singleton graph - let's check this
#
List(ConnectedComponents(Graph0),
x -> IsIsomorphicGraph(InducedSubgraph(Graph0,x),HofSingGraph));
#
J8:=function(x,y)
return Joined(x,y,[8]);
end;
#
Graph8:=Graph(HofSingGroup, [Coclique], OnSets, J8);;
#
# Graph8 is distance-transitive with valency 15 and diameter 4
# We check the distance-regularity with GlobalParameters
#
GlobalParameters(Graph8);
#
J08:=function(x,y)
return Joined(x,y,[0,8]);
end;
#
Graph08:=Graph(HofSingGroup, [Coclique], OnSets, J08);;
#
# Graph08 is the Higman-Sims graph
#
GlobalParameters(Graph08);
#
# This checks that Graph08 is strongly regular
#
# and finally, composition series of the groups:
#
DisplayCompositionSeries(HofSingGroup); # U(3,5).2
DisplayCompositionSeries(AutomorphismGroup(Graph08)); # HS.2
# Now the book suggests constructing the 2-transitive action of HS:
HigSimsGroup:=DerivedSubgroup(AutomorphismGroup(Graph08));;
# short names
G:=HigSimsGroup;; H:=AutomorphismGroup(Graph8);;
IsSubgroup(G,H);
# degree of permutation group - should be 176
Index(G,H);
# construct the permutation group
# Note: "Operation" changed to "Action" in GAP4
HigSimsTwoTrans:=Action(G,RightCosets(G,H),OnRight);
# degree of transitivity - should be 2
Transitivity(HigSimsTwoTrans);