히그먼-심스 그래프

히그먼-심스 그래프
히그먼-심스 그래프
	Paul Hafner의 구성에 따른 그림
이름의 유래	도널드 G. 히그먼; 찰스 C. 심스
꼭짓점	100
모서리	1100
반지름	2
지름	2
안둘레	4
자기 동형 사상	88,704,000
특성	강한 정규 그래프; 해밀턴 그래프; 오일러 그래프

그래프 이론에서 히그먼-심스 그래프(영어: Higman-Sims graph)는 꼭짓점 100개와 모서리 1100개를 갖는 22-정규 그래프이다. 히그먼-심스 그래프는 이웃한 꼭지점 쌍이 공통 이웃을 공유하지 않고 이웃하지 않은 꼭지점 쌍이 6개의 공통 이웃을 공유하는 유일한 강한 정규 그래프 srg(100,22,0,6)이다.^[1] 이것은 Mesner (1956) 에 의해 처음 구성되었고, 1968년에 도널드 G. 히그스과 찰스 C. 심스에 의해 히그먼-심스 그래프의 자기 동형군에서 지표 2인 부분군 히그먼-심스 군을 정의하는 방법으로 재발견되었다.^[2]

구성[편집]

M22 그래프에서 구성[편집]

강한 정규 그래프 srg(77, 16, 0, 4)인 M22 그래프의 슈타이너 계 S(3,6,22)에서 점에 해당하는 22개의 새로운 꼭짓점을 추가한다. 각 블록을 블록이 포함하는 점과 연결하고, 새로 추가된 22개의 꼭짓점과 연결된 꼭짓점 하나를 더하여 히그먼-심스 그래프를 얻는다.

호프만–싱글턴 그래프에서[편집]

호프만-싱글턴 그래프에는 크기가 15인 독립집합이 100개 존재한다. 100개의 대응하는 꼭짓점으로 새 그래프를 만들고 대응하는 독립 집합이 정확히 0 또는 8개의 공통 요소를 갖는 꼭짓점을 연결한다. 이 결과로 만들어지는 그래프는 히그먼-심스 그래프이고, 히그먼-심스 그래프를 352가지 방법으로 호프만-싱글턴 그래프 두 개로 분할할 수 있다.

정육면체에서[편집]

정육면체의 각 꼭짓점을 000, 001, 010, ..., 111으로 표시한다. 꼭짓점 4개로 구성된 집합 70개 중 집합 원소의 XOR이 000인 집합만을 남긴다. 이러한 집합은 면 6개, 두 변이 각각 정육면체의 변과 면 대각선인 직사각형 6개, 정사면체 2개로 총 14개 존재한다. 이는 점 8개 위에서 크기가 4인 블록 14개를 갖는 블록 설계이다. 각 꼭짓점은 블록 7개에 포함되고, 각 꼭짓점 쌍은 블록 3개에 포함되고, 각 꼭짓점 삼중쌍은 블록 1개에 포함된다. 꼭짓점 8개에 붙은 표시를 치환하여 8! = 40320개의 정육면체와 블록 설계를 만들고 중복을 제거하면 30가지의 블록 설계가 남는다. 이는 1344개의 자기 동형 사상이 있고, 40320/1344 = 30이기 때문이다.

30개의 설계와 70개의 블록(꼭짓점 집합의 4-부분집합)에 대해 꼭짓점을 만든다. 각 블록은 정확히 6개의 설계에 나타난다. 각 설계를 설계가 포함하는 14개 블록에 연결한다. 각 설계는 8개의 서로 다른 설계와 서로소이고, 이러한 설계 쌍을 연결한다. 각 블록은 16개의 서로 다른 블록과 꼭짓점을 정확히 한 개하고, 이러한 블록 쌍을 연결한다. 결과 그래프는 히그먼-심스 그래프가 된다. 블록은 다른 블록 16개와 디자인 6개에 연결되므로 차수 22이고, 설계는 블록 14개와 다른 설계 8개에 연결되므로 차수 22이다. 따라서 모든 꼭짓점은 각각 차수 22이다.

대수적 성질[편집]

히그먼-심스 그래프의 자기동형군은 위수 2의 순환군과 위수 44,352,000인 히그먼-심스 군의 반직접곱과 동형인 위수 88,704,000를 갖는 군이다.^[3] 임의의 변을 다른 변으로 옮기는 자기 동형이 존재하고, 따라서 히그먼-심스 그래프는 변 전이 그래프이다.^[4]

히그먼-심스 그래프의 특성 다항식은 $(x-22)(x-2)^{77}(x+8)^{22}$ 이다. 스펙트럼이 정수로 구성되므로 히그먼-심스 그래프는 정수 그래프이다. 또한 히그먼-심스 그래프는 이 특성 다항식를 갖는 유일한 그래프로, 스펙트럼에 의해 결정되는 그래프이다.

리치 격자 내부[편집]

히그먼-심스 그래프는 리치 격자 내부에서 자연스럽게 발생한다. X, Y 및 Z 가 리치 격자의 세 점인 경우 거리 XY, XZ 및 YZ는 $2,{\sqrt {6}},{\sqrt {6}}$ 이다. 각각 정확히 100개의 리치 격자 점 T 가 있으므로 모든 거리 XT, YT 및 ZT 가 2와 같으며 두 점 T 와 T′ 사이의 거리가 ${\sqrt {6}}$ 일 때 연결하면, 결과 그래프는 히그먼-심스 그래프와 동형이다. 더욱이, X, Y, Z 각각을 고정하는 리치 격자의 모든 자기 동형 사상(즉, 각각을 고정하는 유클리드 합동)의 집합은 히그먼-심스 군(만약 우리가 X 와 Y 의 교환을 허용한다면, 모든 것의 차수 2 확장 그래프 자기 동형이 얻어진다). 이것은 히그먼-심스 군이 콘웨이 군 Co₂ (차수 2 확장 포함) 및 Co₃ 내에서 발생하고 결과적으로 Co₁ 내에서도 발생함을 보여준다.^[5]

참고 문헌[편집]

↑ Weisstein, Eric Wolfgang. “Higman–Sims Graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
↑ Higman, Donald G.; Sims, Charles C. (1968). “A simple group of order 44,352,000” (PDF). 《Mathematische Zeitschrift》 105 (2): 110–113. doi:10.1007/BF01110435.
↑ Brouwer, Andries E. “Higman–Sims graph”.
↑ Brouwer, A. E. and Haemers, W. H. "The Gewirtz Graph: An Exercise in the Theory of Graph Spectra."
↑ Conway, John H.; Sloane, Neil J. A. 《Sphere Packings, Lattices and Groups》. Grundlehren der mathematischen Wissenschaften 3판. Springer-Verlag. ISBN 1-4419-3134-1.

Mesner, Dale Marsh (1956), 《An investigation of certain combinatorial properties of partially balanced incomplete block experimental designs and association schemes, with a detailed study of designs of Latin square and related types》, Doctoral Thesis, Department of Statistics, Michigan State University, MR 2612633

[1] Weisstein, Eric Wolfgang. “Higman–Sims Graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.

[2] Higman, Donald G.; Sims, Charles C. (1968). “A simple group of order 44,352,000” (PDF). 《Mathematische Zeitschrift》 105 (2): 110–113. doi:10.1007/BF01110435.

[3] Brouwer, Andries E. “Higman–Sims graph”.

[4] Brouwer, A. E. and Haemers, W. H. "The Gewirtz Graph: An Exercise in the Theory of Graph Spectra."

[5] Conway, John H.; Sloane, Neil J. A. 《Sphere Packings, Lattices and Groups》. Grundlehren der mathematischen Wissenschaften 3판. Springer-Verlag. ISBN 1-4419-3134-1.

[1]

[2]

[3]

[4]

[5]