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
order 100 while
H1.gens() provides a list of generators---naturally they
are the three elements we used, but in a different order.
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)]
y,z,x = H1.gens()
and then create a connection set
C = [ x^it*y^it*z^it 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] )
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.
G.am().fcp() to get the factored characteristic polynomial
of $G$, because it's shorter than
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
G.relabel() part = [, [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,
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.