호프만–싱글턴 그래프

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 구성
3. 대수적 성질
4. 부분 그래프 및 포함 그래프
참조

1. 개요

호프만–싱글턴 그래프는 50개의 꼭짓점과 7개의 차수를 가진 정점 50개로 구성된 무방향 그래프이다. 이 그래프는 다양한 방법으로 구성될 수 있으며, 오각형과 오각별, PG(3,2)를 이용하거나 군론적 구성을 사용할 수 있다. 호프만–싱글턴 그래프는 대칭 그래프이며, 자기동형군은 위수가 252,000이다. 또한, 특성 다항식은 (x-7)(x-2)^{28}(x+3)^{21}이며, 100개의 독립 집합을 갖는다. 이 그래프는 다양한 부분 그래프를 포함하며, 특히 Heawood 그래프, 뫼비우스-칸토어 그래프, 홀수 그래프 O(4), 콕서터 그래프, 터트-콕서 그래프, 실베스터 그래프, 히그먼-심스 그래프 등을 부분 그래프로 포함한다.

더 읽어볼만한 페이지

강한 정규 그래프 - 페일리 그래프
페일리 그래프는 유한체와 제곱수를 기반으로 구성되며, 강하게 정규적이고 자기 여 그래프이며 해밀턴 순환 그래프이다.
강한 정규 그래프 - M22 그래프
M22 그래프는 노드, 간선, 속성, 그래프 구조, 데이터를 요소로 가지며, 슈타이너 계나 히그먼-심스 그래프를 통해 구성될 수 있고, 그래프 스펙트럼과 자기 동형군, 삼각형이 없는 강한 정규 그래프라는 특징을 가진다.
정규 그래프 - 페일리 그래프
페일리 그래프는 유한체와 제곱수를 기반으로 구성되며, 강하게 정규적이고 자기 여 그래프이며 해밀턴 순환 그래프이다.
정규 그래프 - 완전 그래프
완전 그래프는 그래프 내 모든 꼭짓점 쌍이 변으로 연결된 그래프로, 꼭짓점 수 n에 따라 K_n으로 표기되며 n(n-1)/2개의 변을 가지고, 사회 연결망 분석 등 다양한 분야에 응용된다.
그래프 이론 - 다이어그램
다이어그램은 2차원 기하학적 기호를 사용하여 정보를 시각적으로 표현하는 기술로, 과학, 공학, IT, 비즈니스 등 다양한 분야에서 활용되며 정보를 간략하게 나타내고 시각적 사고를 돕는다.
그래프 이론 - 쾨니히스베르크의 다리 문제
쾨니히스베르크의 다리 문제는 프레겔 강에 놓인 7개의 다리를 한 번씩만 건너 출발점으로 되돌아올 수 있는지 묻는 문제로, 오일러에 의해 그래프 이론적으로 분석되어 해결되었으며 그래프 이론의 탄생에 기여했다.

호프만–싱글턴 그래프
그래프 정보
이름	호프만-싱글턴 그래프
원어 이름	Hoffman–Singleton graph
명명자	앨런 J. 호프만 로버트 R. 싱글턴
꼭짓점 수	50
변 수	175
자기 동형	PSU(3,5²):2)
색칠수	4
채색 지수	7
둘레	5
지름	2
반지름	2
종수	29
속성	강한 정규 그래프 대칭 그래프 해밀턴 그래프 정수 그래프 케이지 무어 그래프

2. 구성

호프만–싱글턴 그래프를 구성하는 방법은 여러 가지가 알려져 있다.^[22]^[7] 대표적으로 오각형과 오각별을 이용하는 방법, 유한 기하학 구조인 PG(3,2)를 활용하는 방법, 군론적인 접근법 등이 있다.

2. 1. 오각형과 오각별을 이용한 구성

호프만–싱글턴 그래프는 5개의 오각형 P_h와 5개의 오각별(오망성) Q_i를 이용하여 구성할 수 있다. 구성 방법은 다음과 같다.^[7]

1. 5개의 오각형 P_h (h = 0, 1, 2, 3, 4)와 5개의 오각별 Q_i (i = 0, 1, 2, 3, 4)를 준비한다.

2. 각 오각형 P_h 내부에서, 꼭짓점 j는 꼭짓점 j-1 및 j+1과 변으로 연결된다.

3. 각 오각별 Q_i 내부에서, 꼭짓점 j는 꼭짓점 j-2 및 j+2와 변으로 연결된다.

4. 오각형 P_h의 꼭짓점 j와 오각별 Q_i의 꼭짓점 h · i + j를 변으로 연결한다.

이때 모든 첨자(h, i, j)는 0, 1, 2, 3, 4의 값을 가지며, 덧셈과 곱셈은 5를 법으로 하는 모듈러 연산을 따른다.^[23]^[7]

2. 2. PG(3,2)를 이용한 구성

7개의 원소를 갖는 파노 평면의 한 예시인

\{abc, ade, afg, bef, bdg, cdf, ceg\}

를 고정한다.^[7] 이 파노 평면에 7개의 원소로 이루어진 집합

\{a, b, c, d, e, f, g\}

에 대한 모든 짝순열(총 2520개, 교대군

A_7

의 원소)을 적용한다.^[7] 이렇게 얻어진 2520개의 파노 평면들을 사전식 순서 등을 이용하여 정규화하고 중복되는 것을 제거하면, 정확히 15개의 고유한 파노 평면이 남게 된다.^[7]

원래의 7개 원소 집합

\{a, b, c, d, e, f, g\}

에서 선택할 수 있는 크기 3인 부분집합, 즉 삼중쌍은 총 35개가 존재한다. 이때, 각각의 삼중쌍은 위에서 얻은 15개의 파노 평면 중 정확히 3개에 포함된다.^[7] 이 35개의 삼중쌍과 15개의 파노 평면 사이의 포함 관계는 PG(3,2)라는 구조를 정의하는데, 이는 15개의 점(파노 평면)과 35개의 선(삼중쌍)으로 구성된 유한 사영 평면이다.^[7]

호프만-싱글턴 그래프는 이 PG(3,2) 구조를 기반으로 다음과 같이 구성할 수 있다:^[7]

# 50개의 꼭짓점을 만든다: 15개는 파노 평면에 해당하고, 35개는 삼중쌍에 해당한다.

# 각 파노 평면 꼭짓점을 그 평면에 포함된 7개의 삼중쌍 꼭짓점과 연결한다. 이는 리바이 그래프의 구성 방식과 유사하다.

# 서로소 관계에 있는, 즉 공통 원소를 갖지 않는 두 삼중쌍에 해당하는 꼭짓점들을 서로 연결한다. 이는 홀수 그래프 O(4)의 구성 방식과 유사하다.

PG(3,2)를 이용하는 이러한 구성 방식은 호프만-싱글턴 그래프를 부분 그래프로 포함하는 더 큰 그래프인 Higman-Sims 그래프를 구성하는 데에도 유사하게 활용된다.^[7]

2. 3. 군론적 구성

호프만–싱글턴 그래프를 구성하는 한 가지 방법은 다음과 같다.^[7]

집합

G

를

\mathbb{Z}_2\times\mathbb{Z}_5\times\mathbb{Z}_5

라고 하자.

G

안의 각 원소

(a,b,c)

와

(x,y,z)

에 대해, 다음과 같은 이항 연산

\circ

를 정의한다:

(a,b,c)\circ(x,y,z)=(a+x,b-bx+y,c+(-1)^a by+2^az)

.

호프만-싱글턴 그래프는 꼭짓점

g \in G

를 가지며,

g'=g\circ s

를 만족하는

s \in \{(0,0,1),(0,0,4),(1,0,0),(1,1,0),(1,2,0),(1,3,0),(1,4,0)\}

가 존재할 경우, 꼭짓점

g \in G

와

g'\in G

사이에 변(edge)이 존재하도록 정의된다.^[8] (참고로, 원본 논문 저자들이 "groupoid"라는 용어를 사용했지만, 이는 범주론적 의미가 아닌 이항 함수 또는 마그마를 의미한다. 또한, 논문의 공식에는 마지막 항이

(-1)^x by

로 표기된 오타가 있는데, 이는 호프만-싱글턴 그래프를 생성하지 않는다. 올바른 공식은 여기에 제시된

(-1)^a by

이다.^[9])

3. 대수적 성질

호프만-싱글턴 그래프는 여러 주목할 만한 대수적 성질을 지닌다. 이 그래프의 자기동형군은 위수가 252,000이며, 그래프의 구조적 대칭성을 나타낸다.^[10] 또한, 그래프의 특성 다항식을 통해 고유값을 계산할 수 있는데, 모든 고유값이 정수이므로 호프만–싱글턴 그래프는 정수 그래프에 해당한다.^[10] 그래프 내에는 크기가 15인 독립 집합이 100개 존재하며, 이들 간의 관계 또한 중요한 대수적 특징 중 하나이다.

3. 1. 자기 동형군

호프만-싱글턴 그래프의 자기동형군은 위수가 252,000인 군으로, 사영 특수 유니터리 군 PSU(3,5²)와 프로베니우스 자기동형사상에 의해 생성된 위수 2의 순환군의 반직접곱인 PΣU(3,5²)와 동형이다.^[10] 이 자기동형군은 그래프의 꼭짓점, 변, 호(arc)에 대해 추이적으로 작용한다. 따라서 호프만-싱글턴 그래프는 대칭 그래프이다.

50개의 기호에 대한 순열군으로서, 이 자기동형군은 다음 두 순열을 반복적으로 적용하여 생성할 수 있다.^[10]

:

(1\ 44\ 22\ 49\ 17\ 43\ 9\ 46\ 40\ 45)(2\ 23\ 24\ 14\ 18\ 10\ 12\ 42\ 38\ 6)(3\ 41\ 19\ 4\ 15\ 20\ 7\ 13\ 37\ 8)(5\ 28\ 21\ 29\ 16\ 25\ 11\ 26\ 39\ 30)(27\ 47)(31\ 36\ 34\ 32\ 35)(33\ 50)

그리고

:

(1\ 7\ 48\ 47\ 41\ 46\ 17)(2\ 39\ 11\ 4\ 15\ 14\ 42)(3\ 32\ 28\ 9\ 23\ 6\ 43)(5\ 22\ 38\ 18\ 44\ 36\ 29)(8\ 37\ 40\ 34\ 26\ 49\ 24)(10\ 16\ 31\ 27\ 13\ 21\ 45)(19\ 33\ 25\ 35\ 50\ 30\ 20)

그래프 꼭짓점의 안정자군은 7개의 문자에 대한 대칭군

S_7

과 동형이다. 그래프 변의 안정자군은

\mathrm{Aut}(A_6) = A_6.2^2

와 동형이며, 여기서

A_6

는 6개의 문자에 대한 교대군이다. 이 두 종류의 안정자군은 모두 호프만-싱글턴 그래프 전체 자기동형군의 극대 부분군이다.

3. 2. 특성 다항식

호프만-싱글턴 그래프의 인접 행렬의 특성 다항식은 다음과 같다.^[10]

:

(x-7) (x-2)^{28} (x+3)^{21}

이 다항식의 근인 그래프의 스펙트럼 (고유값)은 7 (중복도 1), 2 (중복도 28), -3 (중복도 21)이다. 모든 고유값이 정수이므로, 호프만–싱글턴 그래프는 정수 그래프이다.

3. 3. 독립 집합

호프만–싱글턴 그래프는 크기가 15인 독립 집합을 정확히 100개 가진다. 각 독립 집합은 다른 7개의 독립 집합과 서로소 관계에 있다. 이 100개의 독립 집합을 꼭짓점으로 하고, 서로소 관계에 있는 독립 집합들을 변으로 연결하면 새로운 그래프를 만들 수 있다. 이 그래프는 각각 호프만–싱글턴 그래프와 동형인 50개의 꼭짓점을 가진 두 개의 부분 그래프로 나눌 수 있다.

4. 부분 그래프 및 포함 그래프

호프만–싱글턴 그래프는 다양한 종류의 중요한 그래프들을 부분 그래프로 포함하고 있으며, 다른 그래프의 부분 그래프가 되기도 한다.

주요 부분 그래프로는 1260개의 5-순환, 5250개의 6-순환, 그리고 525개의 페테르센 그래프가 있다.^[24]^[11] 또한 이분 그래프인 Möbius–Kantor 그래프 2625개와 Heawood 그래프 750개와 동형인 부분 그래프들을 포함한다. 이 외에도 홀수 그래프 O(4), 콕서터 그래프, 텃-콕서터 그래프 역시 호프만-싱글턴 그래프의 부분 그래프이다.^[11] 특정 방법을 통해 꼭짓점을 제거하면 175개의 실베스터 그래프를 얻을 수도 있다.^[12]

한편, 호프만–싱글턴 그래프는 더 큰 그래프인 히그먼-심스 그래프의 부분 그래프이기도 하다.^[13]

4. 1. 순환(Cycle)

호프만–싱글턴 그래프는 1260개의 5-순환과 5250개의 6-순환을 가지고 있다.^[24]^[11] 또한, 525개의 페테르센 그래프를 포함하며, 각 6-순환은 정확히 하나의 페테르센 그래프에 속한다. 이 페테르센 그래프 중 하나를 제거하면 고유한 (6,5)-케이지와 동형인 그래프가 남게 된다.^[24]^[11] (50,7,0,1)의 강정칙 그래프라는 성질만으로도 호프만–싱글턴 그래프가 1260개의 5-순환을 갖는다는 것을 알 수 있다.

호프만–싱글턴 그래프는 이분 그래프인 Möbius–Kantor 그래프와 Heawood 그래프와 동형인 부분 그래프를 다수 포함한다. 이 그래프들의 꼭짓점에 +1과 -1 값을 교대로 부여하여 색칠하면, 호프만-싱글턴 그래프의 고유값 -3에 해당하는 고유 벡터를 찾을 수 있다. -3은 호프만-싱글턴 그래프의 유일한 음의 고유값이다. 이러한 고유 벡터들은 호프만-싱글턴 그래프의 -3 고유 공간을 생성하지만, Möbius-Kantor 그래프나 Heawood 그래프의 수가 -3 고유 벡터의 수보다 많기 때문에 "과도하게 완성된" 기저를 형성한다.

구체적으로, 호프만-싱글턴 그래프에는 Heawood 그래프와 동형인 부분 그래프가 750개 존재한다. Heawood 그래프의 자기동형군의 위수는 336이며, 호프만-싱글턴 그래프의 자기동형군 위수는 750 * 336 = 252,000이다. 이는 그래프 내의 임의의 Heawood 그래프를 고정하면 호프만-싱글턴 그래프 전체가 고정됨을 의미한다. Heawood 그래프는 파노 평면의 인접 그래프이기도 하다. 호프만-싱글턴 그래프에서 크기가 15인 독립 집합은 100개 존재하는데, 그중 하나를 고정하면 이와 8개의 꼭짓점을 공유하는 다른 독립 집합이 15개 있다. 여기서 8개의 공통 꼭짓점을 제외하면 남는 14개의 꼭짓점이 Heawood 그래프를 형성한다. 이를 통해 100 * 15 / 2 = 750개의 Heawood 그래프가 존재함을 확인할 수 있다.

비슷하게, Möbius–Kantor 그래프와 동형인 부분 그래프는 2625개 존재하며, 이 그래프의 자기동형군 위수는 96이다 (2625 * 96 = 252,000).

또한 호프만–싱글턴 그래프는 홀수 그래프 O(4), 콕서터 그래프, 텃-콕서터 그래프를 부분 그래프로 포함한다.^[11]

호프만–싱글턴 그래프의 임의의 변(모서리)을 선택하고, 그 변의 양 끝 꼭짓점 중 하나와 그 꼭짓점에 연결된 12개의 다른 꼭짓점을 제거하면, 남은 36개의 꼭짓점은 실베스터 그래프를 형성한다. 호프만-싱글턴 그래프의 각 변은 고유한 실베스터 그래프에 대응되므로, 총 175개의 실베스터 그래프 복사본이 존재한다.^[12]

히그먼-심스 그래프는 호프만-싱글턴 그래프를 부분 그래프로 포함한다.^[13]

4. 2. 페테르센 그래프

호프만–싱글턴 그래프는 525개의 페테르센 그래프를 부분 그래프로 포함한다.^[24]^[11] 이 그래프에는 5250개의 6-순환이 있으며, 각각의 6-순환은 정확히 하나의 페테르센 그래프에 속한다.^[24] 호프만–싱글턴 그래프에서 페테르센 그래프 하나를 제거하면, 남는 그래프는 유일한 (6,5)-케이지와 동형이다.^[24]^[11]

4. 3. 뫼비우스-칸토어 그래프와 Heawood 그래프

호프만–싱글턴 그래프는 여러 부분 그래프를 포함하는데, 그중에는 이분 그래프인 뫼비우스-칸토어 그래프와 Heawood 그래프와 동형인 것들이 많이 있다. 이들 그래프의 꼭짓점에 +1과 -1 값을 번갈아 칠하면, 호프만-싱글턴 그래프의 고유값 -3에 해당하는 고유 벡터를 찾을 수 있다. 이 -3은 호프만-싱글턴 그래프의 유일한 음수 고유값이다. 이 고유 벡터들은 호프만-싱글턴 그래프의 -3 고유 공간을 생성하지만, 실제로는 -3 고유 벡터보다 뫼비우스-칸토어 그래프나 Heawood 그래프가 더 많아서 수학적으로 "과도하게 완성된" 기저를 이룬다고 표현한다.

호프만–싱글턴 그래프 안에는 Heawood 그래프와 동형인 부분 그래프가 750개 있다. Heawood 그래프의 자기동형군의 위수는 336이다. 호프만-싱글턴 그래프의 자기동형군 위수는 750 * 336 = 252,000인데, 이는 그래프 내의 임의의 Heawood 그래프 하나를 고정하면 호프만-싱글턴 그래프 전체가 고정된다는 것을 의미한다. 비슷하게, 뫼비우스-칸토어 그래프와 동형인 부분 그래프는 2,625개 존재한다. 뫼비우스-칸토어 그래프의 자기동형군 위수는 96이며, 2,625 * 96 = 252,000이므로 유사한 관계가 성립한다.

Heawood 그래프는 특히 파노 평면의 인접 그래프이다. 호프만-싱글턴 그래프의 특정 구성(15개의 점과 35개의 선으로 이루어진 구성)을 고려하면 Heawood 그래프가 나타나는 이유를 짐작할 수 있다. 호프만-싱글턴 그래프에는 크기가 15인 독립 집합이 100개 있다. 이 중 하나를 고정하면, 이 집합과 8개의 꼭짓점을 공유하는 다른 독립 집합은 15개가 있다. 이 8개의 공통 꼭짓점을 제외하고 남은 14개의 꼭짓점은 Heawood 그래프를 형성한다. 따라서 총 100 * 15 / 2 = 750개의 Heawood 그래프가 존재한다.

4. 4. 홀수 그래프, 콕서터 그래프, 텃-콕서터 그래프

호프만-싱글턴 그래프는 홀수 그래프 O(4), 콕서터 그래프 및 텃-콕서터 그래프 또한 부분 그래프로 포함한다.^[11]

4. 5. 실베스터 그래프

호프만–싱글턴 그래프의 임의의 모서리 하나를 선택한다. 이 모서리의 양 끝 꼭짓점 두 개와, 그중 한 꼭짓점에 직접 연결된 이웃 꼭짓점 12개를 제거하면 남는 36개의 꼭짓점으로 이루어진 그래프가 실베스터 그래프이다.^[12] 호프만–싱글턴 그래프의 각 모서리는 서로 다른 실베스터 그래프에 대응시킬 수 있으므로, 호프만–싱글턴 그래프 안에는 총 175개의 실베스터 그래프 복사본이 존재한다.^[12]

4. 6. 히그먼-심스 그래프

호프만–싱글턴 그래프는 히그먼-심스 그래프에 포함되므로, 히그먼-심스 그래프는 호프만-싱글턴 그래프의 상위 그래프이다.^[13]

참조

_[1] 논문 The Hoffman-Singleton Graph and Its Automorphisms
_[2] 간행물 Re: What is the Edge Chromatic Number of Hoffman-Singleton? https://listserv.nod[...] GRAPHNET@listserv.nodak.edu 2004-09-28
_[3] 웹사이트 Hoffman-Singleton Graph
_[4] 논문 Minimum genus embeddings of the Hoffman-Singleton graph 2014-08
_[5] 웹사이트 Hoffman-Singleton graph http://www.win.tue.n[...]
_[6] 논문 Moore graphs with diameter 2 and 3 http://www.research.[...]
_[7] 웹사이트 Hoffman–Singleton Graph http://blogs.ams.org[...] American Mathematical Society 2016-02-01
_[8] arXiv Digraph Networks and Groupoids
_[9] 웹사이트 Messages on Mastodon https://mathstodon.x[...]
_[10] 문서 These generators published by GAP. There are of course many other generators for this group.
_[11] 웹사이트 Hoffman-Singleton graph http://www.win.tue.n[...]
_[12] 웹사이트 Hoffman-Singleton graph http://www.win.tue.n[...]
_[13] 웹사이트 Hoffman-Singleton graph http://www.win.tue.n[...]
_[14] 논문 The Hoffman-Singleton Graph and Its Automorphisms
_[15] 간행물 Re: What is the Edge Chromatic Number of Hoffman-Singleton? http://listserv.noda[...] GRAPHNET@istserv.nodak.edu 2004-09-28
_[16] 웹사이트 Hoffman-Singleton Graph
_[17] 논문 Minimum genus embeddings of the Hoffman-Singleton graph 2014-08
_[18] 웹사이트 Hoffman-Singleton graph http://www.win.tue.n[...]
_[19] 논문 Moore graphs with diameter 2 and 3 http://www.research.[...]
_[20] 인용 http://www.win.tue.n[...]
_[21] 인용 http://www.research.[...]
_[22] 인용 http://blogs.ams.org[...] American Mathematical Society
_[23] 인용 http://blogs.ams.org[...] American Mathematical Society
_[24] 저널 인용 On the uniqueness of the smallest graph of girth 5 and valency 6

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com