호프만–싱글턴 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
{{그래프 정보|name=호프만–싱글턴 그래프|namesake=앨런 호프만<br/>로버트 싱글턴|image=[[파일:Hoffman-Singleton graph.svg|200px]]|vertices=50|edges=175|diameter=2|radius=2|girth=5|automorphisms={{formatnum:252000}}<br/>([[Projective special unitary group|PSU]](3,5<sup>2</sup>):2)|chromatic_number=4|chromatic_index=7|properties=[[강한 정규 그래프]]<br/>[[대칭 그래프]]<br/>[[해밀턴 그래프]]<br/>[[정수 그래프]]<br/>[[무어 그래프]]|genus=29}}[[파일:Hoffman_singleton_graph_circle2.gif|오른쪽|섬네일|250x250픽셀| 호프만-싱글턴 그래프. 파란색 간선으로 이루어진 부분 그래프는 서로소인 오각형 10개의 합이다.]]
[[그래프 이론]]에서 '''호프만–싱글턴 그래프'''(Hoffman–Singleton graph)는 50개의 꼭짓점과 175개의 변을 가진 7-[[정규 그래프]]로 매개변수 (50,7,0,1)를 갖는 유일한 강한 정규 그래프이다.<ref>{{인용|url=http://www.win.tue.nl/~aeb/drg/graphs/Hoffman-Singleton.html}}.</ref> 앨런 호프만과 로버트 싱글턴이 모든 [[무어 그래프]]를 분류하려고 시도하면서 구성한 것으로, 존재하는 것으로 알려진 가장 차수가 높은 [[무어 그래프]]이다.<ref>{{인용|url=http://www.research.ibm.com/journal/rd/045/ibmrd0405H.pdf}}.</ref> 각 정점의 차수가 7이고 [[안둘레|둘레]]가 5인 [[무어 그래프]]이므로 이는 (7,5)-[[케이지(그래프 이론)|케이지]]이다.

== 구성 ==
호프만-싱글턴 그래프를 구성하는 두 가지 방법이 있다.<ref name="vi">{{인용|url=http://blogs.ams.org/visualinsight/2016/02/01/hoffman-singleton-graph/|출판사=American Mathematical Society}}</ref>

=== 오각형과 오각별에서 구성 ===
다섯 개의 [[오각형]] <math>P_h</math>와 다섯 개의 [[오각별]] <math>Q_i</math>에서, <math>P_h</math>의 꼭짓점 <math>j</math> 과 ''<math>Q_i</math>'' 의 꼭짓점 <math>h \cdot i + j</math>를 변으로 연결한다. 이때 각 첨자는 0, 1, 2, 3, 4의 값을 가지며 5를 법으로 하여 합동인 첨자는 같은 것으로 본다.<ref name="vi">{{인용|url=http://blogs.ams.org/visualinsight/2016/02/01/hoffman-singleton-graph/|출판사=American Mathematical Society}}</ref>

=== [[PG(3,2)]]에서 구성 ===
<math>\{abc, ade, afg, bef, bdg, cdf, ceg\}</math>와 같이 7개의 원소를 갖는 [[파노 평면]]을 고정하고, 7-집합 <math>\{a, b, c, d, e, f, g\}</math> 에 2520개의 [[짝수 순열]], 즉 [[교대군]] <math>A_7</math>의 원소를 모두 적용한다. 이렇게 얻어지는 2520개의 파노 평면을 각각 사전순 정렬 등을 이용하여 정규화하고, 중복 항목을 삭제하면 파노 평면이 정확히 15개 남는다. 집합 <math>\{a, b, c, d, e, f, g\}</math>의 각 삼중쌍(크기 3인 부분집합)은 정확히 3개의 파노 평면에 포함된다. 35개의 삼중쌍과 15개의 파노 평면 사이의 결합은 점 15개와 선 35개를 갖는 [[PG(3,2)]]를 유도한다.

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

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

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

호프만-싱글턴 그래프의 [[특성방정식|특성 다항식]]은 <math>(x-7) (x-2)^{28} (x+3)^{21}</math>이다. [[스펙트럼 그래프 이론|스펙트럼]]이 정수로 이루어져 있으므로 호프만–싱글턴 그래프는 [[적분 그래프|정수 그래프]]이다.

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

== 부분 그래프 및 포함 그래프 ==
호프만–싱글턴 그래프에는 5-[[순환 (그래프 이론)|순환]] 1260개와 6-[[순환 (그래프 이론)|순환]] 5250개가 있다. [[페테르센 그래프]] 525개를 포함하고, 각 6-순환은 정확히 하나의 페테르센 그래프에 속한다. 이러한 부분 그래프 중 하나를 제거하면 고유한 (6,5) 케이지와 동형인 그래프가 남는다.<ref>{{저널 인용|제목=On the uniqueness of the smallest graph of girth 5 and valency 6|저널=[[Journal of Graph Theory]]|성=Wong|이름=Pak-Ken|권=3|쪽=407–409|doi=10.1002/jgt.3190030413}}</ref>

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

== 각주 ==
{{각주}}

== 참고 문헌 ==

* {{인용|last1=Benson|first1=C. T.|last2=Losey|first2=N. E.|title=On a graph of Hoffman and Singleton|doi=10.1016/0095-8956(71)90015-3|mr=0281658|year=1971|journal=Journal of Combinatorial Theory, Series B|issn=0095-8956|volume=11|issue=1|pages=67–79|doi-access=free}}
* Holton, D.A.; Sheehan, J. (1993), ''The Petersen graph'', Cambridge University Press, 186쪽, 190쪽, ISBN 0-521-43594-3.
[[분류:그래프 이론]]
[[분류:정규 그래프]]
[[분류:강한 정규 그래프]]