Higman–Sims graph

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(100,22,0,6), where 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 Mesner (1956) and rediscovered in 1968 by Donald G. Higman and Charles C. Sims as a way to define the Higman–Sims group, a subgroup of index two in the group of automorphisms of the Hoffman–Singleton graph.

Construction

From M22 graph

Take the M22 graph, a strongly regular graph srg(77,16,0,4) and augment it with 22 new vertices corresponding to the points of S(3,6,22), each block being connected to its points, and one additional vertex C connected to the 22 points.

From Hoffman–Singleton graph

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-(8,4,1) 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.