In the mathematical

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 field of graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, the Hoffman–Singleton graph is a 7-regular

Regular graph

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...

 undirected graph with 50 vertices and 175 edges. It is the unique strongly regular graph

Strongly regular graph

In graph theory, a discipline within mathematics, a strongly regular graph is defined as follows. Let G = be a regular graph with v vertices and degree k...

 with parameters (50,7,0,1). It was constructed by Alan Hoffman

Alan Hoffman (mathematician)

Alan Jerome Hoffman, born May 30, 1924 in New York City, is a mathematician and IBM fellow emeritus, T. J. Watson Research Center, IBM, Yorktown Heights, N.Y. He is the founding editor of the Journal Linear Algebra and its Applications, and holds several patents...

 and Robert Singleton while trying to classify all Moore graphs, and is the highest order Moore graph known to exist. Since it is a Moore graph where each vertex has degree 7, and the girth is 5, it is a (7,5)-cage

Cage (graph theory)

In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth.Formally, an -graph is defined to be a graph in which each vertex has exactly r neighbors, and in which the shortest cycle has length exactly g. It is known that an -graph exists...

.

Construction

A simple direct construction is the following: Take five pentagons P_h and five pentagrams Q_i, so that vertex j of P_h is adjacent to vertices j-1,j+1 of P_h and vertex j of Q_i is adjacent to vertices j-2,j+2 of Q_i. Now join vertex j of P_h to vertex hi+j of Q_i. (All indices mod 5.)

Algebraic properties

The automorphism group of the Hoffman-Singleton graph is a group of order isomorphic to PΣU(3,5²) the semidirect product

Semidirect product

In mathematics, specifically in the area of abstract algebra known as group theory, a semidirect product is a particular way in which a group can be put together from two subgroups, one of which is a normal subgroup. A semidirect product is a generalization of a direct 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

Symmetric graph

In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphismsuch that...

. It is also a Cayley graph

Cayley graph

In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem and uses a specified, usually finite, set of generators for the group...

.

The characteristic polynomial

Characteristic polynomial

In linear algebra, one associates a polynomial to every square matrix: its characteristic polynomial. This polynomial encodes several important properties of the matrix, most notably its eigenvalues, its determinant and its trace....

 of the Hoffman-Singleton graph is equal to . Therefore the Hoffman-Singleton graph is an integral graph

Integral graph

In the mathematical field of graph theory, an integral graph is a graph whose spectrum consists entirely of integers. In other words, a graphs is an integral graph if all the eigenvalues of its characteristic polynomial are integers....

: its spectrum

Spectral graph theory

In mathematics, spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated to the graph, such as its adjacency matrix or Laplacian matrix....

 consists entirely of integers.

Subgraphs

Using only the fact that the Hoffman-Singleton graph is a strongly regular graph with parameters (50,7,0,1), it can be shown that there are 1260 5-cycles contained in the Hoffman-Singleton graph.

Additionally, the Hoffman-Singleton graph contains 525 copies of the Petersen graph

Petersen graph

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named for Julius Petersen, who in 1898 constructed it...

.