# Section3.2The Higman-Sims Graph

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. They provide constructions for a number of srg's on 100 vertices.

First we form a permutation group.

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:

We set

and then create a connection set

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.

By default, Sage creates Cayley graphs that are have directed edges. So we need to convert to an undirected graph.

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

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.

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

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

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?

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.