TOPICS
Search

Higman-Sims Graph


Higman-SimsGraph

The Higman-Sims graph is the unique strongly regular graph on 100 nodes (Higman and Sims 1968, Brouwer 1983, Brouwer and Haemers 1993). It was also constructed independently in Theorem 5.3 of Goethals and Seidel (1970). It has regular parameters (nu,k,lambda,mu)=(100,22,0,6), where nu is the number of vertices, k is the number of neighbors of each vertex, lambda is the number of common neighbors shared by every adjacent pair of vertices, and mu is the number of common neighbors shared by every nonadjacent pair or vertices.

The Higman-Sims graph is distance-regular with intersection array {22,21;1,6}. It is also distance-transitive.

It is an integral graph with graph spectrum (-8)^(22)2^(77)22^1.

Higman-SimsGraphPieces

The embedding given at the top of this article is the graph sum of the ten graphs illustrated above which arise in the construction due to Hafner (2004).

It can be constructed by beginning with the 77 vectors of length 7 in the Witt design that contain the symbol 1, dropping the 1, and renumbering the remaining elements from 1 to 22. Consider these vectors V as vertices, and adjoin an additional 22 vertices P and one special vertex Omega. Now construct the 616 edges between v in V whenever the intersection of v_i and v_j is empty, the 462 edges between v_i and p_j whenever j is a member of v_i, and the 22 edges between Omega and every p_j. Then the result graph on 100 vertices and 1100 edges is the Higman-Sims graph.

The Higman-Sims graph can be constructed from the Hoffman-Singleton graph by treating the latter's 100 independent vertex sets of size 15 as vertices and connecting by edges those pairs of independent sets which share exactly 0 or 8 elements.

It can also be constructed from the Leech lattice by starting with three lattice points that form the vertices of an isosceles triangle with side lengths of 2, sqrt(6), and sqrt(6), identifying the exactly 100 lattice points that are at distance 2 from each triangle vertex, and joining two points with an edge if they are separated by distance sqrt(6). The resulting graph is the Higman-Sims graph (Conway and Sloane 1999, pp. 292-293; Gaucher 2013; Brouwer and van Maldeghem 2022, p. 303).

The automorphism group of the Higman-Sims graph acts transitively on its edges (Brouwer and Haemers 1993).

The graph obtained by vertex deletion of the neighbors of a point in the Higman-Sims graph (which is not, as claimed by van Dam and Haemers 2003, the subgraph induced by the vertex neighbors) is the M22 graph.


See also

Leech Lattice, M22 Graph, Strongly Regular Graph, Witt Design

Explore with Wolfram|Alpha

References

Brouwer, A. E. "Higman-Sims Graph." http://www.win.tue.nl/~aeb/drg/graphs/Higman-Sims.html.Brouwer, A. E. "The Uniqueness of the Strongly Regular Graph of 77 Points." J. Graph Th. 7, 455-461, 1983.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, pp. 163 and 391, 1989.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.Brouwer, A. E. and van Lint, J. H. "Strongly Regular Graphs and Partial Geometries." In Enumeration and Design: Papers from the conference on combinatorics held at the University of Waterloo, Waterloo, Ont., June 14-July 2, 1982 (Ed. D. M. Jackson and S. A. Vanstone). Toronto, Canada: Academic Press, pp. 85-122, 1984.Brouwer, A. E. and van Maldeghem, H. "The Higman-Sims Graph." §10.31 in Strongly Regular Graphs. Cambridge, England: Cambridge University Press, pp. 303-304, 2022.Conway, J. H. and Sloane, N. J. A. Sphere Packings, Lattices and Groups, 3rd ed. New York: Springer-Verlag, 1999.DistanceRegular.org. "Higman-Sims Graph." http://www.distanceregular.org/graphs/higman-sims.html.Gaucher, A. P. "Leech Lattice." https://cp4space.hatsya.com/2013/09/12/leech-lattice/. Sep. 12, 2013.Gewirtz, A. "Graphs with Maximal Even Girth." Canad. J. Math. 21, 915-934, 1969.Goethals, J.-M. and Seidel, J. J. "Strongly Regular Graphs Derived from Combinatorial Designs." Can. J. Math. 22, 597-514, 1970.Hafner, P. R. "On the Graphs of Hoffman-Singleton and Higman-Sims." Elec. J. Combin. 11, R77, 1-32, 2004.Higman, D. G. and Sims, C. C. "A Simple Group of Order 44352000." Math. Z. 105 , 110-113, 1968.Tonchev, V. D. "Binary Codes Derived from the Hoffman-Singleton and Higman-Sims Graphs." IEEE Trans. Info. Th. 43, 1021-1025, 1997.van Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some Distance-Regular Graphs." J. Algebraic Combin. 15, 189-202, 2003.

Cite this as:

Weisstein, Eric W. "Higman-Sims Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Higman-SimsGraph.html

Subject classifications