We construct the famous Higman-Sims graph as a Cayley graph for a permutation group. Our code is based on an interesting paper by Jorgensen and Klin from the Electronic Journal of Combinatorics (http://www.combinatorics.org/Volume_10/PDF/v10i1r17.pdf). They provide constructions for a number of srg's on 100 vertices.

First we form a permutation group.

H1 = PermutationGroup([[(1,2,3,4,5)], [(6,7,8,9,10)], [(2,3,5,4)]])
H1

Permutation Group with generators [(6,7,8,9,10), (2,3,5,4), (1,2,3,4,5)]

The argument to PermutationGroup() is a list where each item in the list is a list of cycles. Using H1.order() shows that H1 has order 100 while H1.gens() provides a list of generators---naturally they are the three elements we used, but in a different order. The command H1.cayley_graph() will return a directed Cayley graph using the elements of H.gens() as the connection set.

Obviously, to get the Higman-Sims graph we need a special connection set. For this we make use of the following set of 22 triples:

ds = [(1,0,0), (4,0,0), (0,1,1), (0,4,1), (2,0,1), (4,2,1),
      (4,3,1), (0,1,2), (0,4,2), (1,2,2), (1,3,2), (2,0,2),
      (3,1,2), (3,2,2), (3,3,2), (3,4,2), (4,0,2), (0,1,3),
      (0,4,3), (1,0,3), (2,2,3), (2,3,3)]

We set

y,z,x = H1.gens()

and then create a connection set

C = [ x^it[0]*y^it[1]*z^it[2] for it in ds]
C

[(1,2,3,4,5), (1,5,4,3,2), (2,3,5,4)(6,7,8,9,10), 
(2,3,5,4)(6,10,9,8,7), (1,5,3,4), (1,4,5,2)(6,8,10,7,9), 
(1,4,5,2)(6,9,7,10,8), (2,5)(3,4)(6,7,8,9,10), 
(2,5)(3,4)(6,10,9,8,7), (1,5)(2,4)(6,8,10,7,9), 
(1,5)(2,4)(6,9,7,10,8), (1,4)(2,3), (1,3)(4,5)(6,7,8,9,10), 
(1,3)(4,5)(6,8,10,7,9), (1,3)(4,5)(6,9,7,10,8), 
(1,3)(4,5)(6,10,9,8,7), (1,2)(3,5), (2,4,5,3)(6,7,8,9,10), 
(2,4,5,3)(6,10,9,8,7), (1,4,3,5), (1,2,5,4)(6,8,10,7,9), 
(1,2,5,4)(6,9,7,10,8)]

Here $x$, $y$ and $z$ are our original generators and $C$ is a subset of $G$ consisting of elements of the form $x^iy^jz^k$. So they are specified by triples $(i,j,k)$ and ds is indeed a set of triples. We perform a partial check on our work by testing if $C$ is inverse-closed.

all( [x^-1 in C for x in C] )

True

The graph we want is

G = H1.cayley_graph( generators=C)

How can we confirm that this is the Higman-Sims graph? Well, it is connected, regular, and has exactly three eigenvalues (as we see in the factored characteristic polynomial):

G.is_connected(), G.is_regular(), G.am().fcp()

(True, True, (x - 22) * (x + 8)^22 * (x - 2)^77)

Since the Higman-Sims graph is determined by its eigenvalues, we have it. We used G.am().fcp() to get the factored characteristic polynomial of $G$, because it's shorter than G.characteristic_polynomial().factor() even with tab completion. Also, for a graph on any significant number of vertices there is very little to be gained by looking at the coefficients of its characteristic polynomial---they are far too large!

We can use G.girth() to see that $G$ is triangle-free and we can see that $G$ is vertex transitive.

G.girth(), G.is_vertex_transitive()

(4, True)

To verify that $G$ is arc-transitive, we prove more by showing that the stabilizer of a vertex has exactly three orbits on vertices. We set things up with

G.relabel()
part = [[0], [1..99]]
orbs = G.automorphism_group( return_group=False,\
    partition=part, orbits=True)

Some explanations are in order. As created the vertices of $G$ are permutations, after G.relabel() they are the integers in $[0..99]$. Now part is a simple partition of $G$, isolating the vertex $0$. Then orbs is the list of orbits of the subgroup of automorphisms of $G$ that fix each cell of the partition part, effectively the stabiliser of the vertex $0$. From

len(orbs)

3

we infer that the vertex stabiliser has three orbits, which must be 0, the neighbors of 0 and the vertices at distance two from 0. We conclude that $\aut G$ is a rank-three permutation group. Its order?

G.automorphism_group(return_group=False,order=True)

88704000

The Higman-Sims graph contains many triangle-free srg's as subgraphs. For example, the subgraphs obtained by deleting a vertex and its neighbors, or by deleting two adjacent vertices and its neighbors. Its vertices can be partitioned into two copies of the Hoffman-Singleton graph, but that's another story.