View source for Hoffman–Singleton graph

{{Short description|7-regular undirected graph with 50 nodes and 175 edges}}
{{infobox graph
 | name = Hoffman–Singleton graph
 | image = [[File:Hoffman-Singleton graph.svg|200px]]
 | namesake = [[Alan J. Hoffman]]<br/>[[Robert R. Singleton]]
 | vertices = 50
 | edges = 175
 | automorphisms = {{formatnum:252000}}<br/>([[Projective special unitary group|PSU]](3,5<sup>2</sup>):2)<ref>Hafner, P. R. "The Hoffman-Singleton Graph and Its Automorphisms." J. Algebraic Combin. 18, 7–12, 2003.</ref>
 | chromatic_number = 4
 | chromatic_index = 7<ref>Royle, G. "Re: What is the Edge Chromatic Number of Hoffman-Singleton?" GRAPHNET@listserv.nodak.edu posting. Sept. 28, 2004. [https://listserv.nodak.edu/cgi-bin/wa.exe?A2=GRAPHNET;3f0a8ad8.0409&S=]</ref>
 | girth = 5<ref name="MW">{{MathWorld|urlname=Hoffman-SingletonGraph|title=Hoffman-Singleton Graph}}</ref>
 | diameter = 2<ref name="MW"/>
 | radius = 2
 | genus = 29<ref>Conder, M.D.E.; Stokes, K.: "Minimum genus embeddings of the Hoffman-Singleton graph", preprint, August 2014.</ref>
 | properties = [[Strongly regular graph|Strongly regular]]<br/>[[Symmetric graph|Symmetric]]<br/>[[Hamiltonian graph|Hamiltonian]]<br/>[[integral graph|Integral]]<br/>[[Cage (graph theory)|Cage]]<br/>[[Moore graph]]
}}

[[Image:Hoffman singleton graph circle2.gif|250px|right|thumb|
The Hoffman–Singleton graph. The subgraph of blue edges is a sum of ten disjoint pentagons.]]

In the [[mathematics|mathematical]] field of [[graph theory]], the '''Hoffman–Singleton graph''' is a {{nowrap|7-[[regular graph|regular]]}} [[undirected graph]] with 50 vertices and 175 edges. It is the unique [[strongly regular graph]] with parameters (50,7,0,1).<ref name="banana"/> It was constructed by [[Alan Hoffman (mathematician)|Alan Hoffman]] and Robert Singleton while trying to classify all [[Moore graph]]s, and is the highest-order Moore graph known to exist.<ref>{{citation
 | last1 = Hoffman
 | first1 = Alan J.
 | last2 = Singleton
 | first2 = Robert R.
 | title = Moore graphs with diameter 2 and 3
 | journal = IBM Journal of Research and Development
 | volume = 5
 | issue = 4
 | year = 1960
 | pages = 497–504
 | url = http://www.research.ibm.com/journal/rd/045/ibmrd0405H.pdf
 |mr=0140437
 | doi=10.1147/rd.45.0497}}.</ref> Since it is a [[Moore graph]] where each vertex has [[degree (graph theory)|degree]] 7, and the [[girth (graph theory)|girth]] is 5, it is a {{nowrap|(7,5)-[[cage (graph theory)|cage]]}}.

==Construction==
Here are some constructions of the Hoffman–Singleton graph.<ref name="vi">{{citation|url=http://blogs.ams.org/visualinsight/2016/02/01/hoffman-singleton-graph/|title=Hoffman–Singleton Graph|first=John|last=Baez|authorlink=John Baez|date=February 1, 2016|publisher=American Mathematical Society|work=Visual Insight}}</ref>

===Construction from pentagons and pentagrams===
Take five [[pentagon]]s ''P<sub>h</sub>'' and five [[pentagram]]s ''Q<sub>i</sub>'' . Join vertex ''j'' of ''P<sub>h</sub>'' to vertex ''h'' · ''i'' + ''j'' of ''Q<sub>i</sub>'' (all indices are [[modular arithmetic|modulo]] 5.)<ref name="vi"/>

===Construction from [[PG(3,2)]]===
Take a [[Fano plane]] on seven elements, such as <nowiki>{</nowiki>''abc, ade, afg, bef, bdg, cdf, ceg''<nowiki>}</nowiki> and apply all 2520 [[even permutation|even]] [[permutation]]s on the {{nowrap|7-set}} ''abcdefg''. Canonicalize each such Fano plane (e.g. by reducing to [[lexicographic order]]) and discard duplicates. Exactly 15 Fano planes remain. Each {{nowrap|3-set}} (triplet) of the set ''abcdefg'' is present in exactly 3 Fano planes. The incidence between the 35 triplets and 15 Fano planes induces [[PG(3,2)]], with 15 points and 35 lines. To make the Hoffman-Singleton graph, create a graph vertex for each of the 15 Fano planes and 35 triplets. Connect each Fano plane to its 7 triplets, like a [[Levi graph]], and also connect [[disjoint sets|disjoint]] triplets to each other like the [[odd graph]] O(4).

A very similar construction from PG(3,2) is used to build the [[Higman–Sims graph]], which has the Hoffman-Singleton graph as a subgraph.

===Construction on a groupoid/magma===
Let <math>G</math> be the set <math>\mathbb{Z}_2\times\mathbb{Z}_5\times\mathbb{Z}_5</math>. Define a [[binary operation]] <math>\circ</math> on <math>G</math> such that for each <math>(a,b,c)</math> and <math>(x,y,z)</math> in <math>G</math>,
<math>(a,b,c)\circ(x,y,z)=(a+x,b-bx+y,c+(-1)^a by+2^az)</math>. 
Then the Hoffman-Singleton graph has vertices <math>g \in G</math> and that there exists an edge between <math>g \in G</math> and <math>g'\in G</math> whenever <math>g'=g\circ s</math> for some <math>s \in \{(0,0,1),(0,0,4),(1,0,0),(1,1,0),(1,2,0),(1,3,0),(1,4,0)\}</math>.
<ref>{{cite arXiv | last1=Chishwashwa | first1=N. | last2=Faber | first2=V.|last3=Streib | first3=N. | title=Digraph Networks and Groupoids | eprint=2208.10537 | year=2022| class=math.CO }}</ref> (Although the authors use the word "groupoid", it is in the sense of a binary function or magma, not in the category-theoretic sense. Also note there is a typo in the formula in the paper: the paper has <math>(-1)^x by</math> in the last term, but that does not produce the Hoffman-Singleton graph. It should instead be <math>(-1)^a by </math> as written here.<ref>{{citation | last1=Harder | first1=Jannis | title=Messages on Mastodon | url=https://mathstodon.xyz/@jix/111812567568668511}}</ref>)

==Algebraic properties==
The [[automorphism group]] of the Hoffman–Singleton graph is a [[group (mathematics)|group]] of [[order of a group|order]] {{formatnum:252000}} [[group isomorphism|isomorphic]] to PΣU(3,5<sup>2</sup>), the [[semidirect product]] of the [[projective special unitary group]] PSU(3,5<sup>2</sup>) with the [[cyclic group]] of order 2 generated by the [[Frobenius automorphism]]. It [[group action|acts]] transitively on the vertices, on the edges and on the arcs of the graph<!-- primitively too on the vertices and edges -->. Therefore, the Hoffman–Singleton graph is a [[symmetric graph]]. As a [[permutation group]] on 50 symbols, it can be [[Generating set of a group|generated]] by the following two permutations applied recursively<ref>These generators published by GAP. There are of course many other generators for this group.</ref>
:<math>(1\ 44\ 22\ 49\ 17\ 43\ 9\ 46\ 40\ 45)

(2\ 23\ 24\ 14\ 18\ 10\ 12\ 42\ 38\ 6)

(3\ 41\ 19\ 4\ 15\ 20\ 7\ 13\ 37\ 8)

(5\ 28\ 21\ 29\ 16\ 25\ 11\ 26\ 39\ 30)

(27\ 47)

(31\ 36\ 34\ 32\ 35)

(33\ 50)</math>

and

:<math>(1\ 7\ 48\ 47\ 41\ 46\ 17)

(2\ 39\ 11\ 4\ 15\ 14\ 42)

(3\ 32\ 28\ 9\ 23\ 6\ 43)

(5\ 22\ 38\ 18\ 44\ 36\ 29)

(8\ 37\ 40\ 34\ 26\ 49\ 24)

(10\ 16\ 31\ 27\ 13\ 21\ 45)

(19\ 33\ 25\ 35\ 50\ 30\ 20)</math>

The [[stabilizer subgroup|stabilizer]] of a vertex of the graph is isomorphic to the [[symmetric group]] S<sub>7</sub> on 7 letters. The setwise stabilizer of an edge is isomorphic to Aut(A<sub>6</sub>) = A<sub>6</sub>.2<sup>2</sup>, where A<sub>6</sub> is the [[alternating group]] on 6 letters. Both of the two types of stabilizers are [[maximal subgroup]]s of the whole automorphism group of the Hoffman–Singleton graph.

The [[characteristic polynomial]] of the Hoffman–Singleton graph is equal to <math>(x-7)(x-2)^{28}(x+3)^{21}</math>. Therefore, the Hoffman–Singleton graph is an [[integral graph]]: its [[Spectral graph theory|spectrum]] consists entirely of [[integer]]s.

The Hoffman-Singleton graph has exactly 100 [[independent set (graph theory)|independent set]]s of size 15 each. Each independent set is disjoint from exactly 7 other independent sets. The {{nowrap|100-vertex}} graph that connects disjoint independent sets can be partitioned into two {{nowrap|50-vertex}} subgraphs, each of which is isomorphic to the Hoffman-Singleton graph, in an unusual case of self-replicating + multiplying behavior.

==Subgraphs and supergraphs==
There are 1260 5-[[cycle (graph theory)|cycle]]s and 5250 6-cycles in the Hoffman–Singleton graph. There are 525 copies of the [[Petersen graph]], with each {{nowrap|6-cycle}} belonging to exactly one Petersen each. Removing any one Petersen leaves a copy of the unique {{nowrap|(6,5)-cage}}.  The Hoffman Singleton graph also contains the odd graph O(4), the [[Coxeter graph]], and the [[Tutte-Coxeter graph]] as subgraphs.<ref name="banana">{{citation
 | url = http://www.win.tue.nl/~aeb/drg/graphs/Hoffman-Singleton.html
 | title = Hoffman-Singleton graph
 | authorlink = Andries E. Brouwer
 | author = Brouwer, Andries E.}}.</ref>

Take any edge of the Hoffman-Singleton graph, and discard those two vertices as well as the 12 vertices directly connected to either of them. The graph that remains is the [[Sylvester graph]] on 36 vertices. Because each such edge can be mapped to a distinct Sylvester graph, there are 175 copies of the Sylvester graph in the Hoffman Singleton graph.<ref name="banana"/>

The Hoffman Singleton graph is contained in the Higman–Sims graph which is therefore a supergraph.<ref name="banana"/>

==See also==
*[[McKay–Miller–Širáň graph]]s, a class of graphs including the Hoffman–Singleton graph
*[[Table of the largest known graphs of a given diameter and maximal degree]]

==Notes==
{{reflist}}

==References==
* {{Citation | last1=Benson | first1=C. T. | last2=Losey | first2=N. E. | title=On a graph of Hoffman and Singleton | doi=10.1016/0095-8956(71)90015-3 |mr=0281658 | year=1971 | journal=[[Journal of Combinatorial Theory, Series B]] | issn=0095-8956 | volume=11 | issue=1 | pages=67–79| doi-access= }}
* {{cite arXiv | last1=Chishwashwa | first1=N. | last2=Faber | first2=V.|last3=Streib | first3=N. | title=Digraph Networks and Groupoids | eprint=2208.10537 | year=2022 | class=math.CO |mode=cs2}}
*{{citation
 | last1 = Holton | first1 = D.A.
 | last2 = Sheehan | first2 = J.
 | isbn = 0-521-43594-3
 | pages = 186 and 190
 | publisher = [[Cambridge University Press]]
 | title = The Petersen graph
 | title-link = The Petersen Graph
 | year = 1993}}.


{{DEFAULTSORT:Hoffman-Singleton Graph}}
[[Category:Individual graphs]]
[[Category:Regular graphs]]
[[Category:Strongly regular graphs]]