히그먼-심스 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
{{그래프 정보|name=히그먼-심스 그래프|image=[[파일:Higman Sims Graph.svg|220px]]|vertices=100|edges=1100|radius=2|diameter=2|girth=4|automorphisms={{formatnum:88704000}}|properties=[[강한 정규 그래프]]<br>[[해밀턴 경로|해밀턴 그래프]]<br>[[오일러 그래프]]|image_caption=Paul Hafner의 구성에 따른 그림|namesake=도널드 G. 히그먼<br/>찰스 C. 심스}}
[[파일:Higman_Sims_Graph_Parts.svg|오른쪽|섬네일|220x220픽셀| Hafner 구성의 분리된 부분.]]
[[그래프 이론]]에서 '''히그먼-심스 그래프'''({{Llang|en|Higman-Sims graph}})는 꼭짓점 100개와 모서리 1100개를 갖는 22-[[정규 그래프|정규]] [[그래프 (수학)|그래프]]이다. 히그먼-심스 그래프는 이웃한 꼭지점 쌍이 공통 이웃을 공유하지 않고 이웃하지 않은 꼭지점 쌍이 6개의 공통 이웃을 공유하는 유일한 [[강한 정규 그래프]] srg(100,22,0,6)이다.<ref>{{매스월드|제목=Higman&ndash;Sims Graph}}</ref> 이것은 {{하버드 인용 본문|Mesner|1956}} 에 의해 처음 구성되었고, 1968년에 도널드 G. 히그스과 찰스 C. 심스에 의해 히그먼-심스 그래프의 자기 동형군에서 [[부분군의 지표|지표]] 2인 부분군 [[히그먼-심스 군]]을 정의하는 방법으로 재발견되었다.<ref>{{저널 인용|제목=A simple group of order 44,352,000|저널=[[Mathematische Zeitschrift]]|성=Higman|이름=Donald G.|성2=Sims|이름2=Charles C.|저자링크2=Charles Sims (mathematician)|url=https://deepblue.lib.umich.edu/bitstream/2027.42/46258/1/209_2005_Article_BF01110435.pdf|연도=1968|권=105|호=2|쪽=110–113|doi=10.1007/BF01110435}}</ref>

== 구성 ==

=== 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의 [[순환군]]과 위수 {{Val|44352000|fmt=commas}}인 히그먼-심스 군의 [[반직접곱]]과 동형인 위수 {{Val|88704000|fmt=commas}}를 갖는 군이다.<ref>{{웹 인용|url=http://www.win.tue.nl/~aeb/drg/graphs/Higman-Sims.html|제목=Higman&ndash;Sims graph|성=Brouwer, Andries E.|저자링크=Andries E. Brouwer}}</ref> 임의의 변을 다른 변으로 옮기는 자기 동형이 존재하고, 따라서 히그먼-심스 그래프는 [[간선 전이 그래프|변 전이 그래프]]이다.<ref>Brouwer, A. E. and Haemers, W. H. "The Gewirtz Graph: An Exercise in the Theory of Graph Spectra."</ref>

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

== 리치 격자 내부 ==
[[파일:Higman-Sims-19.svg|오른쪽|섬네일|220x220픽셀| 리치 격자 내부의 히그먼-심스 그래프 투영.]]
히그먼-심스 그래프는 [[리치 격자]] 내부에서 자연스럽게 발생한다. ''X'', ''Y'' 및 ''Z'' 가 리치 격자의 세 점인 경우 거리 ''XY'', ''XZ'' 및 ''YZ''는 <math>2, \sqrt{6}, \sqrt{6}</math>이다. 각각 정확히 100개의 리치 격자 점 ''T'' 가 있으므로 모든 거리 ''XT'', ''YT'' 및 ''ZT'' 가 2와 같으며 두 점 ''T'' 와 ''T''&#x2032; 사이의 거리가 <math> \sqrt{6} </math>일 때 연결하면, 결과 그래프는 히그먼-심스 그래프와 동형이다. 더욱이, ''X'', ''Y'', ''Z'' 각각을 고정하는 리치 격자의 모든 자기 동형 사상(즉, 각각을 고정하는 유클리드 합동)의 집합은 히그먼-심스 군(만약 우리가 ''X'' 와 ''Y'' 의 교환을 허용한다면, 모든 것의 차수 2 확장 그래프 자기 동형이 얻어진다). 이것은 히그먼-심스 군이 콘웨이 군 Co<sub>2</sub> (차수 2 확장 포함) 및 Co<sub>3</sub> 내에서 발생하고 결과적으로 Co<sub>1</sub> 내에서도 발생함을 보여준다.<ref>{{서적 인용|제목=Sphere Packings, Lattices and Groups|성=Conway|이름=John H.|저자링크=존 호턴 콘웨이|성2=Sloane|이름2=Neil J. A.|저자링크2=Neil Sloane|판=3rd|총서=Grundlehren der mathematischen Wissenschaften|출판사=[[Springer-Verlag]]|isbn=1-4419-3134-1}}</ref>

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

* {{인용|last1=Mesner|first1=Dale Marsh|title=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|publisher=Department of Statistics, Michigan State University|series=Doctoral Thesis|mr=2612633|year=1956}}

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