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.
Here are some constructions of the Hoffman–Singleton graph. [7]
Take five pentagons Ph and five pentagrams Qi . Join vertex j of Ph to vertex h·i+j of Qi. (All indices are modulo 5.) [7]
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.
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 . [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 in the last term, but that does not produce the Hoffman-Singleton graph. It should instead be as written here. [9])
The automorphism group of the Hoffman–Singleton graph is a group of order 252,000 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 recursively [10]
and
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 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.