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.

I first heard of this graph through the following theorem, in Babai and Frankl’s book.

Let G be a regular graph of degree d and girth at least 5. Then the vertices within distance 2 of a fixed v are all distinct, so there are 1 + v + v(v-1) of them. Assume that’s all the vertices in G. Then d is 2, 3, 7, or 57 (pentagon, Petersen, Hoffman-Singleton, ???).

I first learned of it from Problem 1.F in van Lint and Wilson’s book:

Let G be a graph where every vertex has degree d. Suppose that G has no loops, multiple edges, 3-cycles or 4-cycles. Then G has at least vertices. When can equality occur?

Working on this problem really made me appreciate Knuth and Stanley’s tradition of marking open questions when they pose them.

I once saw a pretty entertaining talk by Rob Beezer called “Everything you Wanted to Know About the Hoffman-Singleton Graph… But Were Afraid to Draw”. See the slides for lots of pictures: http://buzzard.ups.edu/talks/beezer-2009-portland-maa-hoffman-singleton.pdf

yes thasnks.