\( \newcommand\al{\alpha} \newcommand\be{\beta} \newcommand\de{\delta} \newcommand\De{\Delta} \newcommand\eps{\epsilon} \newcommand\ga{\gamma} \newcommand\Ga{\Gamma} \newcommand\ka{\kappa} \newcommand\la{\lambda} \newcommand\La{\Lambda} \newcommand\om{\omega} \newcommand\Om{\Omega} \newcommand\sg{\sigma} \newcommand\Sg{\Sigma} \renewcommand\th{\theta} %--- Latex uses \th for a Norse character \newcommand\Th{\Theta} \newcommand\vphi{\varphi} % % some calligraphy % \newcommand\cA{{\mathcal A}} \newcommand\cB{{\mathcal B}} \newcommand\cC{{\mathcal C}} \newcommand\cD{{\mathcal D}} \newcommand\cE{{\mathcal E}} \newcommand\cF{{\mathcal F}} \newcommand\cG{{\mathcal G}} \newcommand\cH{{\mathcal H}} \newcommand\cI{{\mathcal I}} \newcommand\cJ{{\mathcal J}} \newcommand\cK{{\mathcal K}} \newcommand\cL{{\mathcal L}} \newcommand\cM{{\mathcal M}} \newcommand\cN{{\mathcal N}} \newcommand\cO{{\mathcal O}} \newcommand\cP{{\mathcal P}} \newcommand\cQ{{\mathcal Q}} \newcommand\cR{{\mathcal R}} \newcommand\cS{{\mathcal S}} \newcommand\cT{{\mathcal T}} \newcommand\cU{{\mathcal U}} \newcommand\cV{{\mathcal V}} % % fields and rings (and a semigroup) % \newcommand\cx{{\mathbb C}}% complexes \newcommand\fld{{\mathbb F}} \newcommand\flde{{\mathbb E}} \newcommand\ints{{\mathbb Z}} \newcommand\nn{{\mathbb N}}%non-negative integers \newcommand\re{{\mathbb R}}%reals \newcommand\rats{{\mathbb Q}} % % the really useful stuff % \newcommand\comp[1]{{\mkern2mu\overline{\mkern-2mu#1}}} \newcommand\diff{\mathbin{\mkern-1.5mu\setminus\mkern-1.5mu}}% for \setminus \newcommand\res{\mathbin{\mkern-2.0mu\restriction\mkern-2.0mu}} \newcommand\sbs{\subseteq} \newcommand\sps{\supseteq} \newcommand\seq[3]{#1_{#2},\ldots,#1_{#3}} \DeclareMathOperator{\supp}{supp} \DeclareMathOperator{\im}{im} \DeclareMathOperator{\row}{row} \newcommand\pmat[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand\cprod{\mathbin{\square}} \newcommand\gbin[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}} % % matrix theory % \newcommand\ip[2]{\langle#1,#2\rangle} \newcommand\one{{\bf1}} \DeclareMathOperator{\rk}{rk} \DeclareMathOperator{\tr}{tr} \DeclareMathOperator{\col}{col} \newcommand\mat[3]{\mathrm{Mat}_{#1\times #2}(#3)} \newcommand\sm[3]{\sum_{#1=#2}^{#3}} % % some group theory % \newcommand\aut[1]{{\rm Aut}(#1)} \newcommand\fx[1]{{\rm fix}(#1)}% ch2 \newcommand\grp[1]{\langle #1\rangle} \newcommand\nrml{\vartriangleleft} \newcommand\nrmleq{\trianglelefteq} \DeclareMathOperator{\Sym}{Sym} \newcommand\sym[1]{\Sym(#1)} \DeclareMathOperator{\Alt}{Alt} \newcommand\alt[1]{\Alt(#1)} \)

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.