호프만-싱글턴 그래프

호프만-싱글턴 그래프
이름을 따서 명명됨	앨런 J. 호프먼 로버트 R.싱글턴
정점	50
가장자리	175
반지름	2
지름	2[1]
둘레	5[1]
자동형성	252,000 (PSU(3,52):2)[2]
색수	4
색도 지수	7[3]
속	29[4]
특성.	강력정규 대칭 해밀턴어 적분 케이지 무어 그래프
그래프 및 모수 표

그래프 이론의 수학적 분야에서 호프만-싱글턴 그래프는 정점 50개와 가장자리 175개를 가진 7-정기 비방향 그래프다.매개변수(50,7,0,1)가 있는 고유하고 정규적인 그래프다.^[5]앨런 호프만과 로버트 싱글턴이 모든 무어 그래프를 분류하려다 만든 것으로, 현존하는 것으로 알려진 최고순위의 무어 그래프다.^[6]각 꼭지점에 도 7이 있고 둘레가 5인 무어 그래프인 만큼 a(7,5)-케이지다.

건설

여기 호프만-싱글턴 그래프의 두 가지 구조가 있다.^[7]

펜타곤과 펜타그램으로 시공

5개의 펜타곤 P와_h 5개의 펜타곤 Q를_i 취한다. P의_h 꼭지점 j를 Q의_i 꼭지점 h·i+j에 결합한다(모든 지수는 modulo 5이다).^[7]

PG(3,2)에서 시공

{abc, ade, afg, bef, bdg, cdf, ceg} 등 7개 요소에 Fano 비행기를 타고 7세트 abcdefg에 2520개의 순열까지 모두 적용하십시오.그러한 Fano 평면을 각각 표준화하고(예: 사전 편찬 순서로 축소하여) 중복된 것을 폐기한다.정확히 15대의 파노 비행기가 남아 있다.세트 abcdefg의 각 3세트(트리플릿)는 정확히 3개의 Fano 평면에 존재한다.3중주 35편과 15편 파노 비행기 사이의 발생률은 15점과 35선으로 PG(3,2편)를 유도한다.호프만-싱글턴 그래프를 만들려면 15개의 Fano 평면과 35개의 트리플릿에 대해 각각 그래프 정점을 만드십시오.각 Fano 평면을 Levi 그래프와 같이 7개의 트리플릿에 연결하고, 또한 디스조인트 트리플릿을 홀수 그래프 O(4)처럼 서로 연결한다.

Higman-Sims 그래프를 만들기 위해 PG(3,2)의 매우 유사한 구조가 사용되는데, 이 그래프는 Hoffman-Singleton 그래프를 서브그래프로 가지고 있다.

대수적 특성

호프만-싱글턴 그래프의 자동형성군은 프로베니우스 자동형성에 의해 생성되는 순서 2의 주기적 그룹과 투사적 특수 유니터리 그룹 PSU(3,5²)의 반간접 생산물인 PHBU(3,5²)에 대해 25만 2천 개의 이형성 질서의 그룹이다.그것은 정점, 가장자리, 그리고 그래프의 호에서 전이적으로 작용한다.따라서 호프만-싱글턴 그래프는 대칭 그래프다.그래프의 정점 안정성은 7글자의 대칭군 S에₇ 대해 이형이다.가장자리의 세팅된 스태빌라이저(setwise stabilizer)는 Auto(A₆)=A₆.2에² 이형이며, 여기서 A는₆ 6글자의 교대 그룹이다.두 가지 유형의 안정제 모두 호프만-싱글턴 그래프의 전체 자동화 그룹의 최대 하위그룹이다.

호프만-싱글턴 그래프의 특성 다항식은${\displaystyle }$( ${\displaystyle \mathrm{x}}$- 7${\displaystyle }$)${\displaystyle }$( ${\displaystyle \mathrm{x}}$- 2${\displaystyle {}^{}}$) ${\displaystyle {28}^{}}$( ${\displaystyle x}$+ ${\displaystyle 3{}^{}}$) ${\displaystyle {21}^{}}$ ${\$과 같다$.$따라서 호프만-싱글턴 그래프는 통합 그래프로서 스펙트럼은 전적으로 정수로 구성된다.

호프만-싱글턴 그래프에는 각각 크기 15의 독립된 세트가 정확히 100개씩 들어 있다.각 독립 집합은 정확히 7개의 다른 독립 집합에서 분리된다.분리 독립 세트를 연결하는 100Vertex 그래프는 50Vertex 서브그래프 두 개로 분할할 수 있으며, 각 그래프는 호프만-싱글턴 그래프와 이형화되어 있어 자기복제 + 곱하기 동작이 특이한 경우다.

서브그래프 및 슈퍼그래프

호프만-싱글턴 그래프에는 1260개의 5사이클과 5250개의 6사이클이 있다.피터슨 그래프에는 525개의 복사본이 있으며, 각각의 6 사이클은 정확히 하나의 피터슨에 속한다.피터슨 하나를 제거하면 독특한(6,5) 케이지의 복사본이 남는다.^[8]

또한 호프만-싱글턴 그래프에는 모두 초당적인 뫼비우스-칸토르 그래프와 히우드 그래프의 복사본이 많이 포함되어 있으며, +1과 -1의 교번 값으로 색칠하면 관련 고유값 -3을 가진 그래프의 고유 벡터를 찾을 수 있다(이것은 호프만-싱글톤 그래프의 유일한 음성 고유값이다).이러한 고유 벡터를 종합하면, 호프만-싱글턴 그래프의 -3 아이겐스페이스에 걸쳐 있지만, 매우 완전한 기준을 형성한다. 즉, 뫼비우스-칸토르 그래프나 히우드 그래프는 -3 아이겐벡터보다 더 많다.히우드 그래프는 750장이며, 히우드 그래프는 336순서의 자동형 집단을 가지고 있다.즉, 750*336 = 252000, 호프만-싱글턴 그래프의 오토모피즘 그룹의 크기인데, 이것은 호프만-싱글턴 그래프가 그 안에 있는 어떤 히우드 그래프를 고정시켜 고정한다는 것을 의미한다.마찬가지로 뫼비우스-칸토르 그래프의 사본은 2625부인데, 이 그래프에는 오토모피즘 그룹 순서가 96부, 2625*96=252000부가 있으므로, 유사한 성명은 유지된다.

히우드 그래프는 특히 파노 평면의 발병률 그래프로, 따라서 위의 호프만-싱글턴 그래프 15+35구성에 이어 이는 즉시 히우드 그래프가 발생해야 하는 많은 장소를 보여준다.호프만 싱글톤 그래프에서 15사이즈의 독립된 세트를 취하십시오.이것들이 100개 있다.첫 번째와 공통으로 8개의 꼭지점이 있는 또 다른 독립된 집합을 찾으십시오.그런 이웃의 독립세트가 15개 있다.8개의 공통 정점을 삭제하십시오.남아 있는 14개의 정점들은 히우드 그래프를 형성한다.따라서 앞에서 설명한 바와 같이 100*15/2 = 750 Heawood 그래프가 있다.

또한 호프만 싱글톤 그래프에는 O(4), Coxeter 그래프, Tutte-Coxeter 그래프가 하위 그래프로 포함되어 있다.

Hoffman-Singleton 그래프의 가장자리를 잡고, 두 정점과 그 중 하나에 직접 연결된 정점 12개를 삭제한다.남은 그래프는 36개의 정점에 있는 실베스터 그래프다.그러한 각 가장자리는 구별되는 실베스터 그래프에 매핑될 수 있기 때문에 호프만 싱글톤 그래프에는 실베스터 그래프의 복사본이 175개 있다.

Hoffman Singleton 그래프는 Higman-Sims 그래프에 포함되어 있으며, 따라서 수퍼그래프다.

참고 항목

• McKay-Miller-Sirahň 그래프(Hoffman-Singleton 그래프 포함)
• 주어진 직경 및 최대 수준의 알려진 가장 큰 그래프 표

메모들

참조

• Benson, C. T.; Losey, N. E. (1971), "On a graph of Hoffman and Singleton", Journal of Combinatorial Theory, Series B, 11 (1): 67–79, doi:10.1016/0095-8956(71)90015-3, ISSN 0095-8956, MR 0281658
• Holton, D.A.; Sheehan, J. (1993), The Petersen graph, Cambridge University Press, pp. 186 and 190, ISBN 0-521-43594-3.