View source for Higman–Sims graph

{{CS1 config|mode=cs1}}
{{infobox graph
 | name = Higman–Sims graph
 | image = [[Image:Higman Sims Graph.svg|220px]]
 | image_caption = Drawing based on Paul R. Hafner's construction.<ref>{{Cite journal
 | last1 = Hafner | first1 = P. R.
 | title = On the Graphs of Hoffman&ndash;Singleton and Higman&ndash;Sims
 | journal = The Electronic Journal of Combinatorics
 | volume = 11 | issue = 1 | year = 2004 | pages = R77(1–32)
 | doi = 10.37236/1830
 | url=http://www.combinatorics.org/Volume_11/PDF/v11i1r77.pdf
 | doi-access = free
 }}.</ref>
 | namesake = [[Donald G. Higman]]<br/>[[Charles C. Sims]]
 | vertices = 100
 | edges = 1100
 | radius = 2
 | diameter = 2
 | girth = 4
 | automorphisms = {{formatnum:88704000}} ([[Higman–Sims group|HS]]:2)
 | chromatic_number = 
 | chromatic_index = 
 | properties = [[Strongly regular graph|Strongly regular]]<br>[[Edge-transitive graph|Edge-transitive]]<br>[[Hamiltonian graph|Hamiltonian]]<br>[[Eulerian graph|Eulerian]]
}}

[[Image:Higman Sims Graph Parts.svg|220px|right|thumb|
The separated parts of Hafner's construction.]]

In mathematical [[graph theory]], the '''Higman–Sims graph''' is a 22-[[regular graph|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.<ref>{{MathWorld|urlname=Higman-SimsGraph|title=Higman&ndash;Sims Graph}}</ref> It was first constructed by {{harvtxt|Mesner|1956}}<ref>{{cite thesis | last1=Mesner | first1=Dale Marsh | title=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 | publisher=Department of Statistics, Michigan State University | type=Doctoral Thesis |mr=2612633 | year=1956}}
</ref> 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 of a subgroup|index]] two in the group of automorphisms of the Hoffman–Singleton graph.<ref>{{Cite journal
 | last1 = Higman | first1 = Donald G.
 | last2 = Sims | first2 = Charles C. | author2-link = Charles Sims (mathematician)
 | title = A simple group of order 44,352,000
 | journal = [[Mathematische Zeitschrift]]
 | volume = 105 | issue = 2 | year = 1968 | pages = 110–113
 | doi = 10.1007/BF01110435
 | hdl = 2027.42/46258
 | s2cid = 32803979
 | url = https://deepblue.lib.umich.edu/bitstream/2027.42/46258/1/209_2005_Article_BF01110435.pdf| hdl-access = free}}.</ref>

==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 set (graph theory)|independent set]]s 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&ndash;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. Permute the original 8 vertices any of 8! = 40320 ways, and discard duplicates. There are then 30 different ways to relabel the vertices (i.e., 30 different designs that are all isomorphic to each other by permutation of the points). This is because there are 1344 [[automorphism]]s, and 40320/1344 = 30.

Create a vertex for each of the 30 designs, and for each row of every design (there are 70 such rows in total, each row being a 4-set of 8 and appearing in 6 designs). Connect each design to its 14 rows. Connect disjoint designs to each other (each design is disjoint with 8 others). Connect rows to each other if they have exactly one element in common (there are 4x4 = 16 such neighbors). 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 {{formatnum:88704000}} isomorphic to the [[semidirect product]] of the [[Higman–Sims group]] of order {{formatnum:44352000}} with the [[cyclic group]] of order 2.<ref>{{cite web
  | url = http://www.win.tue.nl/~aeb/drg/graphs/Higman-Sims.html
  | title = Higman&ndash;Sims graph
  | author-link = Andries E. Brouwer
  | author = Brouwer, Andries E.}}</ref> It has automorphisms that take any edge to any other edge, making the Higman–Sims graph an [[edge-transitive graph]].<ref>Brouwer, A. E. and Haemers, W. H. "The Gewirtz Graph: An Exercise in the Theory of Graph Spectra." Euro. J. Combin. 14, 397&ndash;407, 1993.</ref> The outer elements induce odd permutations on the graph. As mentioned [[#From Hoffman–Singleton graph|above]], there are 352 ways to partition the Higman–Sims graph into a pair of Hoffman–Singleton graphs; these partitions actually come in 2 orbits of size 176 each, and the outer elements of the Higman–Sims group swap these orbits.<ref>{{Cite book| title = Atlas of Finite Groups: Maximal Subgroups and Ordinary Characters for Simple Groups
 | last1 = Conway | first1 = J. H.
 | last2 = Curtis | first2 = R. T.
 | last3 = Norton | first3 = S. P.
 | last4 = Parker | first4 = R. A.
 | last5 = Wilson | first5 = R. A.
 | author1-link = John Horton Conway
 | author3-link = Simon P. Norton
 | author4-link = Richard A. Parker
 | author5-link = Robert Arnott Wilson
 | year = 1985
 | others = with computational assistance from J. G. Thackray
 | publisher = Oxford University Press
 | isbn = 978-019853199-9
 | ref = none
}}</ref>

The characteristic polynomial of the Higman–Sims graph is (''x''&nbsp;&minus;&nbsp;22)(''x''&nbsp;&minus;&nbsp;2)<sup>77</sup>(''x''&nbsp;+&nbsp;8)<sup>22</sup>. Therefore, the Higman–Sims graph is an [[integral graph]]: its [[Spectral graph theory|spectrum]] consists entirely of integers. It is also the only graph with this characteristic polynomial, making it a graph determined by its spectrum.

==Inside the Leech lattice==
[[Image:Higman-Sims-19.svg|220px|right|thumb|
A projection of the Higman–Sims graph inside the Leech lattice.]]
The Higman–Sims graph naturally [[Higman–Sims group#A Higman–Sims graph|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 <math>2, \sqrt{6}, \sqrt{6}</math> respectively, then there are exactly 100 Leech lattice points ''T'' such that all the distances ''XT'', ''YT'' and ''ZT'' are equal to 2, and if we connect two such points ''T'' and ''T''&prime; when the distance between them is <math> \sqrt{6} </math>, the resulting graph is isomorphic to the Higman–Sims graph.  Furthermore, the set of all automorphisms of the Leech lattice (that is, Euclidean congruences fixing it) which fix each of ''X'', ''Y'' and ''Z'' is the Higman–Sims group (if we allow exchanging ''X'' and ''Y'', the order 2 extension of all graph automorphisms is obtained).  This shows that the Higman–Sims group occurs inside the [[Conway group]]s Co<sub>2</sub> (with its order 2 extension) and Co<sub>3</sub>, and consequently also Co<sub>1</sub>.<ref>{{Cite book | last1=Conway | first1=John H. | authorlink1=John Horton Conway | last2=Sloane | first2=Neil J. A. | authorlink2=Neil Sloane | title=Sphere Packings, Lattices and Groups | edition=3rd | series=Grundlehren der mathematischen Wissenschaften | date=December 2010 | isbn=978-1-4419-3134-4 | publisher=[[Springer-Verlag]] }} chapter 10 (John H. Conway, "Three Lectures on Exceptional Groups"), §3.5 ("The Higman–Sims and McLaughlin groups"), pp. 292&ndash;293.</ref>

== References ==
{{reflist}}

{{DEFAULTSORT:Higman-Sims graph}}
[[Category:Group theory]]
[[Category:Individual graphs]]
[[Category:Regular graphs]]
[[Category:Strongly regular graphs]]