호프만–싱글턴 그래프

그래프 이론에서 호프만–싱글턴 그래프(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.

분류:그래프 이론
분류:정규 그래프
분류:강한 정규 그래프