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 srg, i.e. no neighboring pair of vertices share a common neighbor and each non-neighboring pair of vertices share six common neighbors. It was first constructed by 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.
Take the M22 graph, a strongly regular graph srg and augment it with 22 new vertices corresponding to the points of S, each block being connected to its points, and one additional vertex C connected to the 22 points.
There are 100 independent sets of size 15 in the Hoffman–Singleton graph. Create a new graph with 100 corresponding vertices, and connect vertices whose corresponding independent sets have exactly 0 or 8 elements in common. The resulting Higman–Sims graph can be partitioned into two copies of the Hoffman-Singleton graph in 352 ways.
From a cube
Take a cube with vertices labeled 000, 001, 010,..., 111. Take all 70 possible 4-sets of vertices, and retain only the ones whose XOR evaluates to 000; there are 14 such 4-sets, corresponding to the 6 faces + 6 diagonal-rectangles + 2 parity tetrahedra. This is a 3- block design on 8 points, with 14 blocks of block size 4, each point appearing in 7 blocks, each pair of points appearing 3 times, each triplet of points occurring exactly once. Permute the original 8 vertices any of 8! = 40320 ways, and discard duplicates. There are then 30 different ways to relabel the vertices. This is because there are 1344 automorphisms, and 40320/1344 = 30. Create a vertex for each of the 30 designs, and for each row of every design. Connect each design to its 14 rows. Connect disjoint designs to each other. Connect rows to each other if they have exactly one element in common. The resulting graph is the Higman–Sims graph. Rows are connected to 16 other rows and to 6 designs degree 22. Designs are connected to 14 rows and 8 disjoint designs degree 22. Thus all 100 vertices have degree 22 each.
Algebraic properties
The automorphism group of the Higman–Sims graph is a group of order isomorphic to the semidirect product of the Higman–Sims group of order with the cyclic group of order 2. It has automorphisms that take any edge to any other edge, making the Higman–Sims graph an edge-transitive graph. The characteristic polynomial of the Higman–Sims graph is 7722. 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.
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 respectively, then there are exactly 100 Leech lattice pointsT 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, the resulting graph is isomorphic to the Higman–Sims graph. Furthermore, the set of all automorphisms of the Leech lattice which fix each of X, Y and Z is the Higman–Sims group. This shows that the Higman–Sims group occurs inside the Conway groups Co2 and Co3, and consequently also Co1.
