The Hoffman-Singleton graph is the unique graph on vertices with the following property: Every vertex is of degree and, between any two vertices, there is either an edge or a path of length two, but not both. The Hoffman-Singleton graph has a large symmetry group — order — and there are many ways to describe it that emphasize different symmetry properties. Various constructions describe it in terms of the geometry of the affine plane , the projective space or just pure combinatorics. Here is one more that I noticed the other day when reading through the original Hoffman-Singleton paper. While turning it into a blogpost, I noticed that the same observation was made by Markus Junker in 2005.
The first few paragraphs here are from the Hoffman-Singleton paper, although with notation I like better. The Hoffman-Singleton paper is not easily available online, but Zaman’s exposition is very similar. Fix a vertex to start things off. Let , for , , …, be its neighbors. Let the other neighbors of be for , …, . Write for the set . Between , the ‘s and the ‘s, we have described all the vertices of the graph, and we have described all of the edges which go into or into a ; the remaining edges connect one to another.
There can be no edge between and , as there is already a length path . So all the remaining edges go between and for . Fixing distinct values and , and a value , there must be one length path from to , so there must be exactly one which is joined to . Similarly, for each , with fixed, there is exactly on bordering . So the edges of the graph form a bijection between and , for each $i \neq j$. Call this bijection . In short, we have bijections to describe.
One can check that the Hoffman-Singleton property is equivalent to the claim that, for all distinct , , and , the compositions and have no fixed points.
At this point, Hoffman and Singleton get into a pretty detailed case analysis to prove that there is a unique choice for the (up to the action of ) and they list that solution. I’ll give a much simpler description below, but the real point I want to make is that this really looks like a question about finding grouoids equivalent to with certain properties. Unfortunately, this is an evil question to ask about groupoids. Still, I wonder, are there any groupoid theorems that would make it obvious that there is a unique solution?
I originally started writing this post to point out that the solution has a unique description. As mentioned above, Junker found this before me and says that others found it before him:
Construction Let be an outer automorphism of . Then we can take and take for .
It is quite easy to check that the compositions and create the permutations and , and those permutations have cycle structure and . In particular, they have no fixed points.