Hoffman–Singleton graph
{{Short description|7-regular undirected graph with 50 nodes and 175 edges}}
{{infobox graph
| name = Hoffman–Singleton graph
| image = 200px
| namesake = Alan J. Hoffman
Robert R. Singleton
| vertices = 50
| edges = 175
| automorphisms = {{formatnum:252000}}
(PSU(3,52):2)Hafner, P. R. "The Hoffman-Singleton Graph and Its Automorphisms." J. Algebraic Combin. 18, 7–12, 2003.
| chromatic_number = 4
| girth = 5{{MathWorld|urlname=Hoffman-SingletonGraph|title=Hoffman-Singleton Graph}}
| radius = 2
| properties = Strongly regular
Symmetric
Hamiltonian
Integral
Cage
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 mathematical field of graph theory, the Hoffman–Singleton graph is a {{nowrap|7-regular}} undirected graph with 50 vertices and 175 edges. It is the unique strongly regular graph with parameters (50,7,0,1). It was constructed by Alan Hoffman and Robert Singleton while trying to classify all Moore graphs, and is the highest-order Moore graph known to exist.{{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}}. Since it is a Moore graph where each vertex has degree 7, and the girth is 5, it is a {{nowrap|(7,5)-cage}}.
Construction
Here are some constructions of the Hoffman–Singleton graph.{{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}}
=Construction from pentagons and pentagrams=
=Construction from [[PG(3,2)]]=
Take a Fano plane on seven elements, such as
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 be the set . Define a binary operation on such that for each and in ,
.
Then the Hoffman-Singleton graph has vertices and that there exists an edge between and whenever for some .
{{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 }} (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 in the last term, but that does not produce the Hoffman-Singleton graph. It should instead be as written here.{{citation | last1=Harder | first1=Jannis | title=Messages on Mastodon | url=https://mathstodon.xyz/@jix/111812567568668511}})
Algebraic properties
The automorphism group of the Hoffman–Singleton graph is a group of order {{formatnum:252000}} isomorphic to PΣU(3,52), the semidirect product of the projective special unitary group PSU(3,52) with the cyclic group of order 2 generated by the Frobenius automorphism. It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore, the Hoffman–Singleton graph is a symmetric graph. As a permutation group on 50 symbols, it can be generated by the following two permutations applied recursivelyThese generators published by GAP. There are of course many other generators for this group.
:
(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)
and
:
(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)
The stabilizer of a vertex of the graph is isomorphic to the symmetric group S7 on 7 letters. The setwise stabilizer of an edge is isomorphic to Aut(A6) = A6.22, where A6 is the alternating group on 6 letters. Both of the two types of stabilizers are maximal subgroups of the whole automorphism group of the Hoffman–Singleton graph.
The characteristic polynomial of the Hoffman–Singleton graph is equal to . Therefore, the Hoffman–Singleton graph is an integral graph: its spectrum consists entirely of integers.
The Hoffman-Singleton graph has exactly 100 independent sets 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-cycles 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.{{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.}}.
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.
The Hoffman Singleton graph is contained in the Higman–Sims graph which is therefore a supergraph.
See also
- McKay–Miller–Širáň graphs, 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}}