Hoffman–Singleton graph

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.

Hoffman–Singleton graph
Named afterAlan J. Hoffman
Robert R. Singleton
Vertices50
Edges175
Radius2
Diameter2[1]
Girth5[1]
Automorphisms252,000
(PSU(3,52):2)[2]
Chromatic number4
Chromatic index7[3]
Genus29[4]
PropertiesStrongly regular
Symmetric
Hamiltonian
Integral
Cage
Moore graph
Table of graphs and parameters
The Hoffman–Singleton graph. The subgraph of blue edges is a sum of ten disjoint pentagons.

Construction

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

Construction from pentagons and pentagrams

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]

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.

Algebraic properties

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. 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.

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 6-cycle belonging to exactly one Petersen each. Removing any one Petersen leaves a copy of the unique (6,5) cage.[8]

The Hoffman–Singleton graph also contains many copies of the Möbius–Kantor graph and the Heawood graph, which are all bipartite, and by coloring them with alternating values of +1 and -1, an eigenvector of the graph can be found, with associated eigenvalue of −3. (This the only negative eigenvalue of the Hoffman–Singleton graph.) Taken together, these eigenvectors span the −3 eigenspace of the Hoffman–Singleton graph, although they form a highly overcomplete basis: there are many more Möbius–Kantor graphs or Heawood graphs than there are −3 eigenvectors. There are 750 copies of the Heawood graph, and the Heawood graph has automorphism group of order 336. In turn, 750*336 = 252000, the size of the automorphism group of the Hoffman-Singleton graph, which means that the Hoffman-Singleton graph is fixed by fixing any Heawood graph inside of it. Similarly, there are 2625 copies of the Möbius–Kantor graph, which has automorphism group order 96, and 2625*96=252000, so the analogous statement holds.

The Heawood graph is notably the incidence graph of the Fano plane, and so following the 15+35 construction of the Hoffman–Singleton graph above, this immediately shows many places where Heawood graphs must occur. Take an independent set of size 15 in the Hoffman Singleton graph. There are 100 of these. Find another independent set that has 8 vertices in common with the first. There are 15 such neighboring independent sets. Discard the 8 common vertices. The 14 vertices that remain form a Heawood graph. There are thus 100*15/2 = 750 Heawood graphs as established earlier.

The Hoffman Singleton graph also contains the odd graph O(4), the Coxeter graph, and the Tutte-Coxeter graph as subgraphs.

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

Notes
  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@istserv.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.
  7. Baez, John (February 1, 2016), "Hoffman–Singleton Graph", Visual Insight, American Mathematical Society
  8. Wong, Pak-Ken. "On the uniqueness of the smallest graph of girth 5 and valency 6". Journal of Graph Theory. 3: 407–409. doi:10.1002/jgt.3190030413.

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