Higman-Sims graph

There is a unique strongly regular graph Γ with parameters v = 100, k = 22, λ = 0, μ = 6. The spectrum is 22¹ 2⁷⁷ (−8)²². The graph was found by Higman & Sims (1969). Uniqueness was proved by Gewirtz (1969). Earlier, this graph had been constructed (1956), and uniqueness was shown (1964), by Dale M. Mesner.

Group

The full group of automorphisms is G = HS.2, acting rank 3, with point stabilizer M₂₂.2.

Construction

1+22+77

The easiest construction is 1+22+77: take a vertex x, let its 22 neighbours be the symbols and its 77 nonneighbours be the blocks of the Steiner system S(3,6,22), where symbols form a coclique, symbols and blocks are adjacent when incident, and blocks are adjacent when disjoint.

50+50

In the description of the Hoffman-Singleton graph we saw that the Higman-Sims graph is the graph on the 15-cocliques, adjacent when they meet in 0 or 8 points. We also saw that vertices and two sets of 50 15-cocliques play the same role, so one also obtains the Higman-Sims graph by taking the vertices and one collection of 50 15-cocliques in the Hoffman-Singleton graph, with the obvious adjacencies.

30+70

Similar to the 15+35 construction of the Hoffman-Singleton graph is the 30+70 construction of the Higman-Sims graph. In the former the starting point was that the lines of PG(3,2) can be labeled with the triples in a 7-set such that lines meet when the corresponding triples have 1 element in common. This time we label the lines of PG(3,2) with the 4+4 splits of an 8-set, where intersecting lines correspond to splits with common refinement 2+2+2+2. Clearly, both descriptions of the lines of PG(3,2) are isomorphic. Take as vertices of the Higman-Sims graph the 15 points and 15 planes of PG(3,2) together with the 70 4-subsets of an 8-set. Join two 4-sets when they have 1 element in common. A 4-set determines a 4+4 split and hence a line in PG(3,2), and is adjacent to the points and planes incident with that line. A plane is adjacent to the nonincident points. This yields the Higman-Sims graph.

Higman's geometry

In S(5,8,24), fix two symbols, and look at the two sets of 176 blocks that contain precisely one of them. Higman made a geometry, calling the blocks in one family "points" and those in the other family "quadrics", where a point is incident with a quadric when the blocks meet in 0 or 4 symbols. This yields a square 2-(176,50,14) design with group HS acting doubly transitively on points and quadrics. It is self-dual, with HS.2 interchanging points and quadrics. Up to conjugacy there are two polarities, one with 80 and one with 176 absolute points. Using one of the latter type we can write the incidence matrix as a symmetric matrix A+I, and A is the adjacency matrix of a strongly regular graph with parameters v=176, k=49, λ=12, μ=14, and group S₈ with vertex orbit sizes 8+168. For the relation with Γ, see below.

Subgraphs

We give the substructures of Γ associated to the 11 maximal subgroups of G distinct from HS, sorted according to increasing orbit size.

a) A vertex.
There are 100 of these, forming a single orbit. The stabilizer of one (in the full automorphism group) is M₂₂.2 with vertex orbit sizes 1+22+77. The subgraph induced on the second subconstituent is the M22 graph, the unique strongly regular graph with v=77, k=16, λ=0.

b) A split into two Hoffman-Singleton graphs.
There are 352 of these, forming a single orbit. The stabilizer is U₃(5).2 with vertex orbit size 100. (That such splits exist is shown in the description of the Hoffman-Singleton graph, where the Higman-Sims graph is constructed on the 100 15-cocliques of the Hoffman-Singleton graph.)

Under HS these 352 fall into two families of size 176, and HS acts doubly transitively on both. This is the Higman geometry of 176 points and 176 quadrics.

The 704 Hoffman-Singleton subgraphs of Γ meet in 0,50 (1x), 15,35 (50x), 20,30 (175x), or 25,25 (126x) points. The point-quadric incidence in Higman's geometry corresponds to the 15,35,15,35 intersection of the corresponding splits.

c) An edge.
There are 1100 of these, forming a single orbit. The stabilizer of one is L₃(4):2² with vertex orbit sizes 2+42+56. The subgraph induced on the 42 is the point-line incidence graph of the projective plane PG(2,4). The subgraph induced on the 56 is the Gewirtz graph.

d) A PG(3,2) point-plane nonincidence graph
As we saw, Γ contains the bipartite point-plane nonincidence graph of PG(3,2). There are 1100 of these, forming a single orbit. The stabilizer of one is S₈×2 with vertex orbit sizes 30+70. The subgraph induced on the 30 is our point-plane nonincidence graph of PG(3,2). It is distance-regular with intersection array {8,7,4;1,4,8}. The subgraph induced on the 70 is the graph on the 4-subsets of an 8-set, adjacent when they meet in a single element.

Let us describe this in terms of the Steiner system S(5,8,24). Pick two symbols a, b, and let S(3,6,22) consist of the 77 octads on a,b (with these elements removed). Pick an octad B not containing a,b. The 77 blocks of S(3,6,22) now split 14+56+7 for having 4,2,0 symbols in common with B, and in the 1+22+77 construction of Γ, the (1+14)+(8+7) induces the point-plane nonincidence graph of PG(3,2).

If we want to extend this 15+15 to a split into 50+50 defined by some octad C containg a but not b, then C must be disjoint from B, and we have 8 choices. And if {B,C,D} is a partition of the set of 24 symbols, then D defines the complementary split (the 35's switch sides).

The objects we found here are known as conics in Higman's geometry. They are K_8,8's in the point-quadric incidence graph: sets of 8 points contained in 8 quadrics. Each pair of points is in precisely two conics, and their union is contained in two quadrics. Dually, the intersection of two quadrics (of size 14) contains two conics that meet in two points. The conic B defines a polarity by sending the point C to the quadric D when {B,C,D} is as above.

e) A non-edge.
There are 3850 of these, forming a single orbit. The stabilizer of one is 2⁵.S₆ with vertex orbit sizes 2+6+32+60. The subgraph induced on the 32 is the folded 6-cube. The subgraph induced on the 60 is the second subconstituent of the M22 graph.

g) 2-coclique extension of the Petersen graph.
There are 5775 of these, forming a single orbit. The stabilizer of one is 2₊¹⁺⁶:S₅ with vertex orbit sizes 20+80. The subgraph induced on the 20 is the 2-coclique extension of the Petersen graph. (The one on 80 is messy.)

i) Pair of splits from the same family.
In terms of Higman's geometry: a pair of points. (Note that a pair of points determines a pair of quadrics and vice versa.) There are 15400 of these, forming a single orbit. The stabilizer of one is (2×A₆.2²).2 with vertex orbit sizes ***40+60***

j) Partitions into four 5C₅.
As we saw, for each of the 176 50+50 splits from one family there are 126 from the other family such that the common refinement is 25+25+25+25. Thus, there are 176*126 = 22176 such unordered pairs of splits, and these form a single orbit. The stabilizer of one is 5₊¹⁺²:[2⁵] with vertex orbit size 100.

k) Good partitions into ten {4,3,1;1,3,4}.
Γ contains 61600 subgraphs isomorphic to K_5,5 minus a matching, the complement of the 2×5 grid, the unique distance-regular graph with intersection array {4,3,1;1,3,4}, the bipartite double of the complete graph K₅. For brevity, let us call such a graph a BD(K₅). These subgraphs form a single orbit, with stabilizer 6.A₅.2² of order 1440 and vertex orbit sizes 10+30+60. Counting is easy in the 1+22+77 construction: such a subgraph containing the 1 is uniquely determined by 4 symbols not in a block (and we find the four blocks that contain 3 of the 4 symbols, and the unique block disjoint from the previous four blocks).

On the 30 the induced subgraph is the point-plane nonincidence graph of PG(3,2). Now this graph has a unique split (up to isomorphism) into three BD(K₅)'s, since the point-plane incidence graph has a unique split into three 5K₂'s. (Description: Let PG(3,2) have points and hyperplanes given by the nonzero elements of GF(16), where x is incident with y when Tr(xy) = 0. Since the only cube of trace 0 is 1, partitioning points and planes according to exponent mod 3 works.)

Our object is a partition of Γ into ten BD(K₅)'s where this set of ten carries the structure of a Petersen graph, and for each BD(K₅) the subgraph induced on the union of its three neighbours is the point-plane nonincidence graph of PG(3,2). There are 36960 *** of these, forming a single orbit. The stabilizer of one is 5:4 × S₅ with vertex orbit size 100.

This description is a bit involved, but just saying "Partition into ten BD(K₅)'s" is not enough: Γ has a very large number of such partitions.

References

A.E. Brouwer, Polarities of G. Higman's symmetric design and a strongly regular graph on 176 vertices, Aequationes Math. 25 (1982) 77-82.

A. Gewirtz, Graphs with maximal even girth, Canad. J. Math. 21 (1969) 915-934.

D.G. Higman & C. Sims, A simple group of order 44,352,000, Math.Z. 105 (1968) 110-113.

G. Higman, On the simple group of D.G. Higman and C.C. Sims, Illinois J. Math. 13 (1969) 74-80.

D.M. Mesner, 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, Ph.D. Thesis, Michigan State University, 1956. (Local copy here .)

D.M. Mesner, Negative Latin square designs, Institute of Statistics, UNC, NC Mimeo series 410, November 1964.

M.S. Smith, On the isomorphism of two simple groups of order 44,352,000, J. Algebra 41 (1976) 172-174.