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. 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. 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.

Comments are closed.