Higman–Sims graph

From Wikipedia, the free encyclopedia

The graph with semi-random vertex position. The 77 black vertices are the blocks of Steiner System, the 22 blue verices are W22 and the red one is the 100th vertex. The 616 black edges connects the disjoint blocks, the 462 blue edges connects the blocks with the W22 nodes and the 22 red edges forms the centrale wheel (= 1100 total edges).

The graph with semi-random vertex position. The 77 black vertices are the blocks of Steiner System, the 22 blue verices are W₂₂ and the red one is the 100th vertex. The 616 black edges connects the disjoint blocks, the 462 blue edges connects the blocks with the W₂₂ nodes and the 22 red edges forms the centrale wheel (= 1100 total edges).

In mathematics, the Higman–Sims graph 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. It was constructed 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.

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.