Up

Hoffman-Singleton graph

There is a unique strongly regular graph Γ with parameters v = 50, k = 7, λ = 0, μ = 1. The spectrum is 71 228 (ā€“3)21.

It was found by Hoffman & Singleton as example of a Moore graph (a regular graph of girth 5 with the largest possible number k2 + 1 of vertices). Two other Moore graphs are known, namely the pentagon and the Petersen graph. If there are other Moore graphs, they must have valency 57 and 3250 vertices.

The Hoffman-Singleton graph is the (7,5)-cage.

It is Hamiltonian.

Group

The full group of automorphisms is G = PSU(3,5).2 acting rank 3, with point stabilizer S7.

Construction

A simple direct construction is the following: Take five pentagons Ph and five pentagrams Qi, so that vertex j of Ph is adjacent to vertices jā€“1,j+1 of Ph and vertex j of Qi is adjacent to vertices jā€“2,j+2 of Qi. Now join vertex j of Ph to vertex hi+j of Qi. (All indices mod 5.)

The second construction uses the fact that it is possible to identify the 35 lines of PG(3,2) with the 35 triples from a 7-set in such a way that intersecting lines correspond to triples that have precisely one element in common. Now take as vertices the 15 points and 35 lines of PG(3,2), let the points form a coclique, let a point be adjacent to a line when they are incident, and let two lines be adjacent when the corresponding triples are disjoint.

The third construction produces the Higman-Sims graph, together with a split into two copies of Γ. In the Steiner system S(4,7,23), fix an symbol a. Construct the Higman-Sims graph on 1+22+77 points by taking a point x, the 22 symbols distinct from a and the 77 blocks containing a, where blocks are adjacent when they meet precisely in {a}. Now let B be a block of S(4,7,23) not containing a. We find a partition (1+7+42)+(15+35) of the 1+22+77 induced by B (the 42 blocks are those meeting B in one point, the 35 those meeting B in three points), and both 1+7+42 and 15+35 induce a Hoffman-Singleton graph.

Supergraphs

As we saw, Γ is subgraph of the Higman-Sims graph on 100 vertices.

Subgraphs

We give the substructures of Γ associated to the 7 maximal subgroups of G distinct from PSU(3,5), sorted according to increasing orbit size.

a) A vertex. There are 50 of these, forming a single orbit. The stabilizer of one (in the full automorphism group) is S7 with vertex orbit sizes 1+7+42. The subgraph induced on the second subconstituent is the unique distance-regular graph with intersection array {6,5,1;1,1,6}.

b) A 15-coclique. There are 100 of these, forming a single orbit. The stabilizer is A7 with vertex orbit sizes 15+35. The complement of a 15-coclique is the unique distance-regular graph with intersection array {4,3,3;1,1,2}, namely the Odd graph O4 of disjoint triples in a 7-set. It has full group S7, with point stabilizer S3×S4. The group is twice that of the Hoffman-Singleton graph since this graph can be extended to a Hoffman-Singleton graph in two ways; both occur in the Higman-Sims graph.

Two 15-cocliques meet in 0 (7x), 3 (35x), 5 (42x), 8 (15x) or 15 (1x) points. Meeting in 0, 5 or 15 is an equivalence relation, and the collection of 100 15-cocliques is the union of two collections of size 50. Being disjoint induces the structure of a Hoffman-Singleton graph on both.

The graph on the 15-cocliques, adjacent when they meet in 8 points, is the unique distance-regular graph with intersection array {15,14,10,3;1,5,12,15}. It has full group PSU(3,5).2 with point stabilizer A7 and edge stabilizer L2(7):2 (see below).

The graph on the 15-cocliques, adjacent when they meet in 0 or 8 is the Higman-Sims graph.

The two sets of 50 15-cocliques and the 50 vertices play a similar role (and there is an outer automorphism that interchanges the three). Thus, we can make a graph on 150 vertices, regular of valency 37, with a partition 50+50+50 such that the union of any two parts is the Higman-Sims graph.

c) Split into two copies of 5C5. There are 126 of these, forming a single orbit. (The construction given above gives an explicit split.) The stabilizer is 5+1+2:8:2 with vertex orbit size 50.

d) An edge. There are 175 of these, forming a single orbit. The stabilizer of one is A6.22 with vertex orbit sizes 2+12+36.

The line graph of the Hoffman-Singleton graph is the unique distance-regular graph with intersection array {12,6,5;1,1,4}. Its distance-2 graph is strongly regular with parameters v = 175, k = 72, λ = 20, μ = 36. (It is the collinearity graph of a partial geometry pg(5,18,2) constructed by Haemers. The collinearity graph of the dual pg(18,5,2) has parameters v = 630, k = 85, λ = 20, μ = 10, and full automorphism group Alt(7), transitive on the points.)

The subgraph induced on the orbit of size 36 is the Sylvester graph, the unique distance-regular graph with intersection array {5,4,2;1,1,4}.

e) A pair of disjoint 15-cocliques. There are 350 of these, forming a single orbit. The stabilizer of one is M10 with vertex orbit sizes 20+30.

The subgraph induced on the orbit of size 20 is 10K2.

The subgraph induced on the orbit of size 30 is Tutte's 8-cage, the incidence graph of the generalized quadrangle GQ(2,2).

f) A Petersen graph. There are 525 of these, forming a single orbit. The stabilizer of one is 2S5.2 with vertex orbit sizes 10+40.

The subgraph induced on the orbit of size 40 is the unique (6,5)-cage.

Each hexagon of Γ is contained in a unique Petersen graph.

Each Petersen graph is split 5+5 in 6 splits into two 5C5. Each split into two 5C5 determines 25 Petersen graphs. Each pair of splits determines a unique Petersen graph. In this way we find the unital in PG(2,52), with splits into two 5C5 as points, and Petersen graphs as lines.

g) A Heawood graph. There are 750 of these, forming a single orbit. The stabilizer of one is L2(7):2 with vertex orbit sizes 8+14+28. The 14 induces the Heawood graph.

Heawood subgraphs are equivalent to pairs of 15-cocliques meeting in 8 points: each half occurs in a unique 15-coclique and these two 15-cocliques meet in 8 points (and conversely, two 15-cocliques meeting in 8 points carry a Heawood graph on their symmetric difference).

The 28 induces the Coxeter graph.

Independence and chromatic number

The Hoffman-Singleton graph has independence number 15, and chromatic number 4. It has edge-chromatic number 7. The complement of the Hoffman-Singleton graph has independence number 2, and chromatic number 25.

Paths and cycles

Aut(Γ) is transitive on the induced paths of length 0, 1, 2, 3, 4, 5. It has three orbits on paths P7 (of length 6). Aut(Γ) is transitive on the induced cycles of length 5, 6, 7. It has two orbits on cycles C8.

Locally Hoffman-Singleton graphs

No locally Hoffman-Singleton graphs are known. Such a graph cannot be distance-transitive (van Bon). If a locally Hoffman-Singleton graph is distance-regular, it must have intersection array {50,42,9; 1,2,42} or {50,42,1; 1,2,50} (Gavrilyuk & Makhnev), and cannot be vertex-transitive (Gavrilyuk, Guo & Makhnev). Any locally Hoffman-Singleton graph has diameter at most 6. (Proof: by Weetman ci-graphs have degree at least iā€“1, so that the diameter is at most 8. If it is 8, then Γ contains a disconnected induced subgraph with degree at least 3, which contradicts interlacing. If it is 7, then Γ contains a disconnected induced subgraph of which one component is a circuit and the other component has degree at least 3. But the subgraphs far from a C5, C6, P6 do not have degree at least 3.)

References

John van Bon, On Locally Hoffman-Singleton Graphs, J. Comb. Theory (B) 63 (1995) 159-161.

A.E. Brouwer & J.H. van Lint, Strongly regular graphs and partial geometries, in: Enumeration and Design - Proc. Silver Jubilee Conf. on Combinatorics, Waterloo, 1982, D.M. Jackson & S.A. Vanstone (eds.) Academic Press, Toronto (1984) 85-122.

W.H. Haemers, A new partial geometry constructed from the Hoffman-Singleton graph, Finite Geometries and designs, Proc. Second Isle of Thorns Conference 1980, P.J. Cameron, J.W.P. Hirschfeld & D.R. Hughes (eds.), London Math. Soc. Lecture Note Ser. 49, Cambridge University Press, Cambridge (1981) 119-127.

A.J. Hoffman & R.R. Singleton, On Moore graphs with diameters 2 and 3, IBM J. Res. Develop. 4 (1960) 497-504.

L.O. James, A combinatorial proof that the Moore (7,2) graph is unique, Utilitas Math. 5 (1974) 79-84.

G. Royle, Re: What is the Edge Chromatic Number of Hoffman-Singleton?, GRAPHNET@listserv.nodak.edu posting, 2004-09-29.

[BCN], Section 13.1.