Hoffman–Singleton graph

Hoffman–Singleton graph
Hoffman–Singleton graph
Named after	Alan J. Hoffman; Robert R. Singleton
Vertices	50
Edges	175
Radius	2
Diameter	2[1]
Girth	5[1]
Automorphisms	252,000; (PSU(3,52):2)[2]
Chromatic number	4
Chromatic index	7[3]
Genus	29[4]
Properties	Strongly regular; Symmetric; Hamiltonian; Integral; Cage; Moore graph
	Table of graphs and parameters

In the mathematical field of graph theory, the Hoffman–Singleton graph is a 7-regular undirected graph with 50 vertices and 175 edges. It is the unique strongly regular graph with parameters (50,7,0,1).[5] 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.[6] Since it is a Moore graph where each vertex has degree 7, and the girth is 5, it is a (7,5)-cage.

The Hoffman–Singleton graph. The subgraph of blue edges is a sum of ten disjoint pentagons.

Construction

Here are some constructions of the Hoffman–Singleton graph.[7]

Construction from pentagons and pentagrams

Take five pentagons P_h and five pentagrams Q_i . Join vertex j of P_h to vertex h·i+j of Q_i. (All indices are modulo 5.)[7]

Construction from PG(3,2)

Take a Fano plane on seven elements, such as {abc, ade, afg, bef, bdg, cdf, ceg} and apply all 2520 even permutations on the 7-set abcdefg. Canonicalize each such Fano plane (e.g. by reducing to lexicographic order) and discard duplicates. Exactly 15 Fano planes remain. Each 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 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 $G$ be the set $\mathbb {Z} _{2}\times \mathbb {Z} _{5}\times \mathbb {Z} _{5}$ . Define a binary operation $\circ$ on $G$ such that for each $(a,b,c)$ and $(x,y,z)$ in $G$ , $(a,b,c)\circ (x,y,z)=(a+x,b-bx+y,c+(-1)^{a}by+2^{a}z)$ . Then the Hoffman-Singleton graph has vertices $g\in G$ and that there exists an edge between $g\in G$ and $g'\in G$ whenever $g'=g\circ s$ for some $s\in \{(0,0,1),(0,0,4),(1,0,0),(1,1,0),(1,2,0),(1,3,0),(1,4,0)\}$ . [8] (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 $(-1)^{x}by$ in the last term, but that does not produce the Hoffman-Singleton graph. It should instead be $(-1)^{a}by$ as written here.[9])

Algebraic properties

The automorphism group of the Hoffman–Singleton graph is a group of order 252,000 isomorphic to PΣU(3,5²) the semidirect product of the projective special unitary group PSU(3,5²) 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 recursively[10] $(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)$

and

$(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)$

The stabilizer of a vertex of the graph is isomorphic to the symmetric group S₇ on 7 letters. The setwise stabilizer of an edge is isomorphic to Aut(A₆)=A₆.2², where A₆ 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 $(x-7)(x-2)^{28}(x+3)^{21}$ . 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 100-vertex graph that connects disjoint independent sets can be partitioned into two 50-vertex subgraphs, each of which is isomorphic to the Hoffman-Singleton graph, in an unusual case of self-replicating + multiplying behavior.

Notes

Weisstein, Eric W. "Hoffman-Singleton Graph". MathWorld.
Hafner, P. R. "The Hoffman-Singleton Graph and Its Automorphisms." J. Algebraic Combin. 18, 7–12, 2003.
Royle, G. "Re: What is the Edge Chromatic Number of Hoffman-Singleton?" GRAPHNET@listserv.nodak.edu posting. Sept. 28, 2004.
Conder, M.D.E.; Stokes, K.: "Minimum genus embeddings of the Hoffman-Singleton graph", preprint, August 2014.
Brouwer, Andries E., Hoffman-Singleton graph.
Hoffman, Alan J.; Singleton, Robert R. (1960), "Moore graphs with diameter 2 and 3" (PDF), IBM Journal of Research and Development, 5 (4): 497–504, doi:10.1147/rd.45.0497, MR 0140437.
Baez, John (February 1, 2016), "Hoffman–Singleton Graph", Visual Insight, American Mathematical Society
Chishwashwa, N.; Faber, V.; Streib, N. (2022). "Digraph Networks and Groupoids". arXiv:2208.10537 [math.CO].
Harder, Jannis, Messages on Mastodon
These generators published by GAP. There are of course many other generators for this group.

References

Benson, C. T.; Losey, N. E. (1971), "On a graph of Hoffman and Singleton", Journal of Combinatorial Theory, Series B, 11 (1): 67–79, doi:10.1016/0095-8956(71)90015-3, ISSN 0095-8956, MR 0281658
Chishwashwa, N.; Faber, V.; Streib, N. (2022), "Digraph Networks and Groupoids", arXiv:2208.10537 [math.CO]
Holton, D.A.; Sheehan, J. (1993), The Petersen graph, Cambridge University Press, pp. 186 and 190, ISBN 0-521-43594-3.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[MW-1] Weisstein, Eric W. "Hoffman-Singleton Graph". MathWorld.

[2] Hafner, P. R. "The Hoffman-Singleton Graph and Its Automorphisms." J. Algebraic Combin. 18, 7–12, 2003.

[3] Royle, G. "Re: What is the Edge Chromatic Number of Hoffman-Singleton?" GRAPHNET@listserv.nodak.edu posting. Sept. 28, 2004.

[4] Conder, M.D.E.; Stokes, K.: "Minimum genus embeddings of the Hoffman-Singleton graph", preprint, August 2014.

[5] Brouwer, Andries E., Hoffman-Singleton graph.

[6] Hoffman, Alan J.; Singleton, Robert R. (1960), "Moore graphs with diameter 2 and 3" (PDF), IBM Journal of Research and Development, 5 (4): 497–504, doi:10.1147/rd.45.0497, MR 0140437.

[vi-7] Baez, John (February 1, 2016), "Hoffman–Singleton Graph", Visual Insight, American Mathematical Society

[8] Chishwashwa, N.; Faber, V.; Streib, N. (2022). "Digraph Networks and Groupoids". arXiv:2208.10537 [math.CO].

[9] Harder, Jannis, Messages on Mastodon

[10] These generators published by GAP. There are of course many other generators for this group.