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). 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. Since it is a Moore graph where each vertex has degree 7, and the girth is 5, it is a (7,5)-cage.

Construction
Here are some constructions of the Hoffman–Singleton graph.

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

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

Algebraic properties
The automorphism group of the Hoffman–Singleton graph is a group of order  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

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.

Subgraphs and supergraphs
There are 1260 5-cycles and 525 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.

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.

The Hoffman-Singleton graph contains 42000 copies of the dodecahedral graph as a subgraph.

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

References
 
 
.

Individual graphs
Regular graphs
Strongly regular graphs
그래프 이론에서 호프만–싱글턴 그래프(Hoffman–Singleton graph)는 50개의 꼭짓점과 175개의 변을 가진 7-정규 그래프로 매개변수 (50,7,0,1)를 갖는 유일한 강한 정규 그래프이다. 앨런 호프만과 로버트 싱글턴이 모든 무어 그래프를 분류하려고 시도하면서 구성한 것으로, 존재하는 것으로 알려진 가장 차수가 높은 무어 그래프이다. 각 정점의 차수가 7이고 둘레가 5인 무어 그래프이므로 이는 (7,5)-케이지이다.

구성 
호프만-싱글턴 그래프를 구성하는 두 가지 방법이 있다.

오각형과 오각별에서 구성 
다섯 개의 오각형 와 다섯 개의 오각별 에서, 의 꼭짓점  과  의 꼭짓점 를 변으로 연결한다. 이때 각 첨자는 0, 1, 2, 3, 4의 값을 가지며 5를 법으로 하여 합동인 첨자는 같은 것으로 본다.

PG(3,2)에서 구성 
와 같이 7개의 원소를 갖는 파노 평면을 고정하고, 7-집합  에 2520개의 짝수 순열, 즉 교대군 의 원소를 모두 적용한다. 이렇게 얻어지는 2520개의 파노 평면을 각각 사전순 정렬 등을 이용하여 정규화하고, 중복 항목을 삭제하면 파노 평면이 정확히 15개 남는다. 집합 의 각 삼중쌍(크기 3인 부분집합)은 정확히 3개의 파노 평면에 포함된다. 35개의 삼중쌍과 15개의 파노 평면 사이의 결합은 점 15개와 선 35개를 갖는 PG(3,2)를 유도한다.

15개의 파노 평면과 35개의 삼중쌍 각각에 대한 꼭지점을 생성한다. 각 파노 평면을 Levi 그래프와 같이 7개의 삼중쌍에 각각 연결하고, 홀수 그래프 O(4)와 같이 서로소인 삼중쌍을 서로 연결하면 호프만-싱글턴 그래프가 구성된다.

PG(3,2)에서의 구성은 호프만-싱글턴 그래프를 부분 그래프로 포함하는 Higman-Sims 그래프를 구성하는 데 비슷하게 사용된다.

대수적 성질 
호프만-싱글턴 그래프의 자기동형군의 위수는 252,000으로, 프로베니우스 자기동형사상에 의해 생성된 차수 2의 순환군과 사영 특수 유니터리군 PSU(3,52)의 반직접곱인 PΣU(3,52)와 동형이다. 자기동형군은 호프만-싱글턴 그래프의 각 꼭지점, 변 및 호에 전이적으로 작용한다. 따라서 호프만-싱글턴 그래프는 대칭 그래프이다. 꼭지점의 안정자는 크기 7인 집합 위의 대칭군 과 동형이다. 그래프의 변을 꼭짓점 두개의 집합으로 보았을 때, 각 변의 안정자는 와 동형이며, 여기서 은 크기 6인 집합 위의 교대군이다. 두 가지 유형의 안정자는 모두 호프만-싱글턴 그래프의 전체 자기동형군의 극대 부분군이다.

호프만-싱글턴 그래프의 특성 다항식은 이다. 스펙트럼이 정수로 이루어져 있으므로 호프만–싱글턴 그래프는 정수 그래프이다.

호프만–싱글턴 그래프에는 크기가 15인 독립집합이 정확히 100개 있다. 각 독립집합은 정확히 7개의 다른 독립 집합과 서로소이다. 독립집합을 꼭짓점으로 하고, 서로소인 독립집합을 연결하여 구성한 그래프는 호프만–싱글턴 그래프와 동형인 부분 그래프 2개로 분할될 수 있다.

부분 그래프 및 포함 그래프 
호프만–싱글턴 그래프에는 5-순환 1260개와 6-순환 5250개가 있다. 페테르센 그래프 525개를 포함하고, 각 6-순환은 정확히 하나의 페테르센 그래프에 속한다. 이러한 부분 그래프 중 하나를 제거하면 고유한 (6,5) 케이지와 동형인 그래프가 남는다.

호프만–싱글턴 그래프에는 이분 그래프인 Möbius–Kantor 그래프와 Heawood 그래프와 동형인 부분 그래프가 많이 포함되어 있다. 이들을 각각 +1과 -1의 값을 교대로 색칠하여 고유값 -3을 갖는 호프만-싱글턴 그래프의 고유 벡터를 찾을 수 있고, -3은 호프만-싱글턴 그래프의 유일한 음의 고유값이다. 이러한 고유 벡터는 호프만-싱글턴 그래프의 -3 고유 공간을 생성하지만, -3 고유 벡터보다 Möbius-Kantor 그래프 또는 Heawood 그래프가 더 많으므로 "과도하게 완성된" 기저를 이룬다. 호프만-싱글턴 그래프에는 Heawood 그래프와 동형인 750개의 부분 그래프가 있고, Heawood 그래프의 자기동형군의 위수는 336이다. 호프만-싱글턴 그래프의 자기동형군의 위수는 750*336 = 252000이므로, 그래프 내부의 임의의 Heawood 그래프를 고정하게 되면 호프만-싱글턴 그래프도 고정된다. 비슷하게, 자기동형군의 위수 96이고 2625*96=252000인 Möbius-Kantor 그래프와 동형인 부분 그래프는 2625개 존재하고 유사한 명제가 성립한다.

Heawood 그래프는 특히 파노 평면의 인접 그래프이므로, 위에서 등장한 호프만-싱글턴 그래프의 15+35 구성을 고려하면 Heawood 그래프가 등장해야 하는 많은 위치를 즉시 보여준다. 호프만-싱글턴 그래프에서 크기가 15인 독립 집합은 100개 존재한다. 그 중 하나를 고정하면, 이와 8개의 꼭짓점을 공유하는 다른 독립 집합은 15개 존재한다. 8개의 공통 꼭지점을 버리면 남아 있는 14개의 꼭지점은 Heawood 그래프를 형성한다. 따라서 앞서 설명한 대로 100*15/2 = 750 Heawood 그래프가 있다.

호프만-싱글턴 그래프는 홀수 그래프 O(4), 콕서터 그래프 및 텃-콕서터 그래프 또한 부분 그래프로 포함한다.

호프만-싱글턴 그래프의 변을 하나 고정하고, 두 끝 꼭짓점 중 하나와 연결된 꼭짓점을 12개를 버리면, 남아 있는 그래프는 꼭짓점 36개를 갖는 실베스터 그래프이다. 호프만-싱글턴 그래프의 각 변은 고유한 실베스터 그래프에 대응되므로 실베스터 그래프와 동형인 부분 그래프는 175개 존재한다.

히그먼-심스 그래프는 호프만-싱글턴 그래프를 포함하므로 포함 그래프이다.

같이 보기 

 McKay–Miller–Širáň 그래프: 호프만–싱글턴 그래프를 포함한 그래프류
 주어진 직경과 최대 차수의 알려진 가장 큰 그래프의 표

각주

참고 문헌 

 
 Holton, D.A.; Sheehan, J. (1993), The Petersen graph, Cambridge University Press, 186쪽, 190쪽, ISBN 0-521-43594-3.
그래프 이론
정규 그래프
강한 정규 그래프