# The Hoffman-Singleton graph and groupoids

The Hoffman-Singleton graph is the unique graph on $50$ vertices with the following property: Every vertex is of degree $7$ 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 $252,000$ — 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 $\mathbb{F}_5^2$, the projective space $\mathbb{P}^3(\mathbb{F}_2)$ 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 $x$ to start things off. Let $y_i$, for $i=0$, $1$, …, $6$ be its neighbors. Let the other $6$ neighbors of $y_i$ be $z_{ir}$ for $r=1$, …, $6$. Write $Z_i$ for the set $\{ z_{i1}, z_{i2}, \dots, z_{i6} \}$. Between $x$, the $7$ $y$‘s and the $42$ $z$‘s, we have described all the vertices of the graph, and we have described all of the edges which go into $x$ or into a $y$; the remaining $126$ edges connect one $z_{ir}$ to another.

There can be no edge between $z_{ir}$ and $z_{is}$, as there is already a length $2$ path $(z_{ir}, y, z_{is})$. So all the remaining edges go between $z_{ir}$ and $z_{js}$ for $i \neq j$. Fixing distinct values $i$ and $j$, and a value $r$, there must be one length $2$ path from $z_{ir}$ to $y_j$, so there must be exactly one $z_{js}$ which is joined to $Z_{ir}$. Similarly, for each $z_{js}$, with $i$ fixed, there is exactly on $z_{ir}$ bordering $z_{js}$. So the edges of the graph form a bijection between $Z_i$ and $Z_j$, for each $i \neq j$. Call this bijection $\sigma(i \to j)$. In short, we have $\binom{7}{2}$ bijections to describe.

One can check that the Hoffman-Singleton property is equivalent to the claim that, for all distinct $i$, $j$, $k$ and $\ell$, the compositions $Z_i \to Z_j \to Z_k \to Z_i$ and $Z_i \to Z_j \to Z_k \to Z_{\ell} \to Z_i$ 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 $\sigma(i \to j)$ (up to the action of $(S_6)^7$) 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 $S_6$ 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 $\alpha$ be an outer automorphism of $S_6$. Then we can take $\sigma(0 \to j) = \sigma(j \to 0) = \mathrm{Id}$ and take $\sigma(i \to j) = \alpha((ij))$ for $1 \leq i \neq j \leq 6$.

It is quite easy to check that the compositions $Z_i \to Z_j \to Z_k \to Z_i$ and $Z_i \to Z_j \to Z_k \to Z_{\ell} \to Z_i$ create the permutations $\alpha((jk))$ and $\alpha((jk\ell))$, and those permutations have cycle structure $2+2+2$ and $3+3$. In particular, they have no fixed points.

## 4 thoughts on “The Hoffman-Singleton graph and groupoids”

1. Allen Knutson says:

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, ???).

2. David Speyer says:

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 $d^2+1$ 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.