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);