히그먼-심스 그래프

그래프 이론에서 히그먼-심스 그래프()는 꼭짓점 100개와 모서리 1100개를 갖는 22-정규 그래프이다. 히그먼-심스 그래프는 이웃한 꼭지점 쌍이 공통 이웃을 공유하지 않고 이웃하지 않은 꼭지점 쌍이 6개의 공통 이웃을 공유하는 유일한 강한 정규 그래프 srg(100,22,0,6)이다. 이것은  에 의해 처음 구성되었고, 1968년에 도널드 G. 히그스과 찰스 C. 심스에 의해 히그먼-심스 그래프의 자기 동형군에서 지표 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의 순환군과 위수 인 히그먼-심스 군의 반직접곱과 동형인 위수 를 갖는 군이다. 임의의 변을 다른 변으로 옮기는 자기 동형이 존재하고, 따라서 히그먼-심스 그래프는 변 전이 그래프이다.Brouwer, A. E. and Haemers, W. H. "The Gewirtz Graph: An Exercise in the Theory of Graph Spectra."

히그먼-심스 그래프의 특성 다항식은 이다. 스펙트럼이 정수로 구성되므로 히그먼-심스 그래프는 정수 그래프이다. 또한 히그먼-심스 그래프는 이 특성 다항식를 갖는 유일한 그래프로, 스펙트럼에 의해 결정되는 그래프이다.

 리치 격자 내부 
오른쪽|섬네일|220x220픽셀| 리치 격자 내부의 히그먼-심스 그래프 투영.
히그먼-심스 그래프는 리치 격자 내부에서 자연스럽게 발생한다. X, Y 및 Z 가 리치 격자의 세 점인 경우 거리 XY, XZ 및 YZ는 이다. 각각 정확히 100개의 리치 격자 점 T 가 있으므로 모든 거리 XT, YT 및 ZT 가 2와 같으며 두 점 T 와 T′ 사이의 거리가 일 때 연결하면, 결과 그래프는 히그먼-심스 그래프와 동형이다. 더욱이, X, Y, Z 각각을 고정하는 리치 격자의 모든 자기 동형 사상(즉, 각각을 고정하는 유클리드 합동)의 집합은 히그먼-심스 군(만약 우리가 X 와 Y 의 교환을 허용한다면, 모든 것의 차수 2 확장 그래프 자기 동형이 얻어진다). 이것은 히그먼-심스 군이 콘웨이 군 Co2 (차수 2 확장 포함) 및 Co3 내에서 발생하고 결과적으로 Co1 내에서도 발생함을 보여준다.

 각주 



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