Higman–Sims graph

Higman–Sims graph
Drawing based on Paul R. Hafner's construction.[1]
Named after	Donald G. Higman Charles C. Sims
Vertices	100
Edges	1100
Radius	2
Diameter	2
Girth	4
Automorphisms	88,704,000 (HS:2)
Properties	Strongly regular Edge-transitive Hamiltonian Eulerian

The separated parts of Hafner's construction.

In mathematical graph theory, the Higman–Sims graph is a 22-regular undirected graph with 100 vertices and 1100 edges. It is the unique strongly regular graph with 100 vertices and valency 22, where no neighboring pair of vertices share a common neighbor and each non-neighboring pair of vertices share six common neighbors.^[2] It was first constructed by Mesner (1956) and rediscovered in 1968 by Donald G. Higman and Charles C. Sims as a way to define the Higman–Sims group, and that group is a subgroup of index two in the group of automorphisms of the Higman–Sims graph.^[3]

Construction begins with the M₂₂ graph, whose 77 vertices are the blocks of the S(3,6,22) Steiner system W₂₂. Adjacent vertices are defined to be disjoint blocks. This graph is strongly regular; any vertex has 16 neighbors, any 2 adjacent vertices have no common neighbors, and any 2 non-adjacent vertices have 4 common neighbors. This graph has M₂₂:2 as its automorphism group, M₂₂ being a Mathieu group.

The Higman–Sims graph is then formed by appending the 22 points of W₂₂ and a 100th vertex C. The neighbors of C are defined to be those 22 points. A point adjacent to a block is defined to be one that is included.

A Higman–Sims graph can be partitioned into two copies of the Hoffman–Singleton graph in 352 ways.

Algebraic properties

The automorphism group of the Higman–Sims graph is a group of order 88,704,000 isomorphic to the semidirect product of the Higman–Sims group of order 44,352,000 with the cyclic group of order 2.^[4] It has automorphisms that take any edge to any other edge, making the Higman–Sims graph an edge-transitive graph.^[5]

The characteristic polynomial of the Higman–Sims graph is (x − 22)(x − 2)⁷⁷(x + 8)²². Therefore the Higman–Sims graph is an integral graph: its spectrum consists entirely of integers. It is also the only graph with this characteristic polynomial, making it a graph determined by its spectrum.

Inside the Leech lattice

A projection of the Higman–Sims graph inside the Leech lattice.

The Higman–Sims graph naturally occurs inside the Leech lattice: if X, Y and Z are three points in the Leech lattice such that the distances XY, XZ and YZ are $2,{\sqrt {6}},{\sqrt {6}}$ respectively, then there are exactly 100 Leech lattice points T such that all the distances XT, YT and ZT are equal to 2, and if we connect two such points T and T′ when the distance between them is ${\sqrt {6}}$, the resulting graph is isomorphic to the Higman–Sims graph. Furthermore, the set of all automorphisms of the Leech lattice (that is, Euclidean congruences fixing it) which fix each of X, Y and Z is the Higman–Sims group (if we allow exchanging X and Y, the order 2 extension of all graph automorphisms is obtained). This shows that the Higman–Sims group occurs inside the Conway groups Co₂ (with its order 2 extension) and Co₃, and consequently also Co₁.^[6]

References

1. Hafner, P. R. (2004). "On the Graphs of Hoffman–Singleton and Higman–Sims" (PDF). the Electronic Journal of Combinatorics. 11 (1): R77(1–32) External link in |journal= (help).
2. Weisstein, Eric W. "Higman–Sims Graph". MathWorld.
3. Higman, Donald G.; Sims, Charles C. (1968). "A simple group of order 44,352,000". Mathematische Zeitschrift. 105 (2): 110–113. doi:10.1007/BF01110435.
4. Brouwer, Andries E. "Higman–Sims graph".
5. Brouwer, A. E. and Haemers, W. H. "The Gewirtz Graph: An Exercise in the Theory of Graph Spectra." Euro. J. Combin. 14, 397–407, 1993.
6. Conway, John H.; Sloane, Neil J. A. Sphere Packings, Lattices and Groups. Grundlehren der mathematischen Wissenschaften (3rd ed.). Springer-Verlag. ISBN 1-4419-3134-1. chapter 10 (John H. Conway, "Three Lectures on Exceptional Groups"), §3.5 ("The Higman–Sims and McLaughlin groups"), p. 292–293.

• Mesner, Dale Marsh (1956), An investigation of certain combinatorial properties of partially balanced incomplete block experimental designs and association schemes, with a detailed study of designs of Latin square and related types, Doctoral Thesis, Department of Statistics, Michigan State University, MR 2612633