호프만–싱글턴 그래프

호프만–싱글턴 그래프
이름의 유래	앨런 호프만 로버트 싱글턴
꼭짓점	50
모서리	175
반지름	2
지름	2
안둘레	5
자기 동형 사상	252,000 (PSU(3,5^2):2)
색칠수	4
색칠 지표	7
종수	29
특성	강한 정규 그래프 대칭 그래프 해밀턴 그래프 정수 그래프 무어 그래프

호프만-싱글턴 그래프. 파란색 간선으로 이루어진 부분 그래프는 서로소인 오각형 10개의 합이다.

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

구성

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

오각형과 오각별에서 구성

다섯 개의 오각형 ${\displaystyle P_{h}}$와 다섯 개의 오각별 ${\displaystyle Q_{i}}$에서, ${\displaystyle P_{h}}$의 꼭짓점 ${\displaystyle j}$ 과 ${\displaystyle Q_{i}}$ 의 꼭짓점 ${\displaystyle h\cdot i+j}$를 변으로 연결한다. 이때 각 첨자는 0, 1, 2, 3, 4의 값을 가지며 5를 법으로 하여 합동인 첨자는 같은 것으로 본다.^[3]

PG(3,2)에서 구성

${\displaystyle \{abc,ade,afg,bef,bdg,cdf,ceg\}}$와 같이 7개의 원소를 갖는 파노 평면을 고정하고, 7-집합 ${\displaystyle \{a,b,c,d,e,f,g\}}$ 에 2520개의 짝수 순열, 즉 교대군 ${\displaystyle A_{7}}$의 원소를 모두 적용한다. 이렇게 얻어지는 2520개의 파노 평면을 각각 사전순 정렬 등을 이용하여 정규화하고, 중복 항목을 삭제하면 파노 평면이 정확히 15개 남는다. 집합 ${\displaystyle \{a,b,c,d,e,f,g\}}$의 각 삼중쌍(크기 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,5²)의 반직접곱인 PΣU(3,5²)와 동형이다. 자기동형군은 호프만-싱글턴 그래프의 각 꼭지점, 변 및 호에 전이적으로 작용한다. 따라서 호프만-싱글턴 그래프는 대칭 그래프이다. 꼭지점의 안정자는 크기 7인 집합 위의 대칭군 ${\displaystyle S_{7}}$과 동형이다. 그래프의 변을 꼭짓점 두개의 집합으로 보았을 때, 각 변의 안정자는 ${\displaystyle \mathrm {Aut} (A_{6})=A_{6}\times 2^{2}}$와 동형이며, 여기서 ${\displaystyle A_{6}}$은 크기 6인 집합 위의 교대군이다. 두 가지 유형의 안정자는 모두 호프만-싱글턴 그래프의 전체 자기동형군의 극대 부분군이다.

호프만-싱글턴 그래프의 특성 다항식은 ${\displaystyle (x-7)(x-2)^{28}(x+3)^{21}}$이다. 스펙트럼이 정수로 이루어져 있으므로 호프만–싱글턴 그래프는 정수 그래프이다.

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

부분 그래프 및 포함 그래프

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

호프만–싱글턴 그래프에는 이분 그래프인 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áň 그래프: 호프만–싱글턴 그래프를 포함한 그래프류
• 주어진 직경과 최대 차수의 알려진 가장 큰 그래프의 표

각주

1. http://www.win.tue.nl/~aeb/drg/graphs/Hoffman-Singleton.html  |제목=이(가) 없거나 비었음 (도움말).
2. (PDF) http://www.research.ibm.com/journal/rd/045/ibmrd0405H.pdf  |제목=이(가) 없거나 비었음 (도움말).
3. , American Mathematical Society http://blogs.ams.org/visualinsight/2016/02/01/hoffman-singleton-graph/  |제목=이(가) 없거나 비었음 (도움말)
4. 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. 

참고 문헌

• 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 
• Holton, D.A.; Sheehan, J. (1993), The Petersen graph, Cambridge University Press, 186쪽, 190쪽, ISBN 0-521-43594-3.