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.