Existence and uniqueness of the Hoffman-Singleton Graph (outline)

Noam D. Elkies

0. Let G be a Moore graph of degree 7, i.e., a strongly regular graph with parameters (50, 7, 0, 1), or equivalently a graph of degree 7 on 50 vertices with diameter 2 and girth 5. Such G contains 50·7·6·6/10 = 1260 pentagons.

1. Let A be the neighborhood of one of those pentagons, and let B be its complement in V (G). Then V (G) = A ∪ B is a partition of V (G) into two 25-vertex parts such that every vertex of G is adjacent to 2 in the same part and 5 in the other part. This is all we’ll use about A, B.

2. Of the 1260 pentagons, 1000 are of type ABxAB and 250 of type AAxBB. This leaves only 10 of type AAAAx and BBBBx. It soon follows that each of A, B consists of five pentagons.

3. We now know what the AA and BB edges look like; the condition that G have no 3- or 4-cycles will force the AB edges uniquely up to automorphism of A, B. First, each A vertex has its one of its five B neighbors in each of the five B pentagons and vice versa. Thus the restriction of G to the union of an A and a B pentagon is a Petersen graph.

4. We can orient the A and B pentagons compatibly, i.e., label the 50 vertices A_{i}(x), B_{j}(y) (i, j, x, y ∈ F_{5}) so that the pentagon edges are {A_{i}(x), A_{i}(x+1)} and {B_{j}(y), B_{j}(y + 1)} and the AB edges are {A_{i}(x), B_{j}(2x + c_{ij})} for some c_{ij}. [A priori it might have been necessary to use −2x + c_{ij} instead of 2x + c_{ij} for some i, j, but thanks to the girth condition we can always flip some pentagons, i.e., relabel A_{i}(x), B_{j}(x) as A_{i}(−x), B_{j}(−x) for certain i, j, to eliminate all the minus signs.]

5. To avoid 4-cycles it is now only necessary that c_{ij} + c_{i′j′} ≠ c_{i′j} + c_{ij′} (i ≠ i′, j ≠ j′). This determines the c_{ij} up to rotating the pentagons [i.e., relabeling A_{i}(x) as A_{i}(x − δ_{i}), which translates the c_{ij} by δ_{i}, and likewise for B_{j}(y)] and permuting the i’s and j’s among themselves. For instance we may take c_{ij} = i · j.