케일리 그래프

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

1. 개요
2. 정의
- 2.1. 방향 그래프 및 색칠
3. 성질
4. 예
- 4.1. 이면체군
- 4.2. 하이젠베르크 군
5. 역사
6. 확장 성질
- 6.1. 카즈단 성질 (T)
7. 케일리 적분 그래프
- 7.1. 케일리 정수 단순군 (CIS)
- 7.2. 케일리 적분군
참조

1. 개요

케일리 그래프는 군과 부분집합을 사용하여 정의되는 그래프로, 군의 원소를 정점으로 하고, 특정 조건을 만족하는 원소 쌍을 잇는 간선으로 구성된다. 생성 집합이 주어지면 연결 그래프가 되며, 그렇지 않으면 비연결 그래프가 된다. 케일리 그래프는 군의 작용을 가지며, 자비두시 정리에 의해 그래프가 특정 조건을 만족하면 케일리 그래프임을 알 수 있다. 케일리 그래프는 정규 그래프이며, 국소 유한성, 유한성, 연결성과 같은 성질을 가진다. 또한, 군의 표현론 및 스펙트럼 이론과 관련이 있으며, 확장 성질을 분석하는 데 사용될 수 있다. 케일리 그래프는 무한 순환군, 순환군, 곱군, 자유군 등 다양한 군의 구조를 시각화하는 데 활용되며, 하이젠베르크 군, 이면체군 등 다양한 군의 케일리 그래프가 예시로 제시된다. 케일리 그래프는 확장 성질을 분석하고, 케일리 적분 그래프와 케일리 정수 단순군, 케일리 적분군 등과 같은 개념을 연구하는 데 활용된다.

더 읽어볼만한 페이지

그래프의 응용 - 상태도 (오토마타 이론)
상태도는 유한 오토마타 이론에서 시스템의 상태와 전이를 시각적으로 표현하는 유향 그래프이며, 무어 머신, 밀리 머신, 하렐 상태도 등 다양한 형태로 활용된다.
그래프의 응용 - 제어 흐름 그래프
제어 흐름 그래프(CFG)는 프로그램의 제어 흐름을 추상적으로 나타내는 그래프로, 노드는 기본 블록, 엣지는 제어 흐름 상의 점프를 표현하며, 프로그램 분석 및 최적화, 특히 도달 가능성 분석, 지배 관계 분석, 루프 관리에 유용하게 사용된다.
순열군 - 교대군
교대군 $A_n$ 은 대칭군 $S_n$ 의 짝순열 집합으로, 순열의 홀짝성을 나타내는 군 준동형의 핵이며, $n>1$ 일 때 $n!/2$ 개의 원소를 갖고, $A_5$ 는 위수가 60인 가장 작은 비가환 단순군으로서 군의 구조, 자기 동형군, 조합론적 문제 등 다양한 성질과 응용을 가진다.
순열군 - 프로베니우스 군
프로베니우스 군은 유한군 $G$ 가 두 개 이상의 원소를 갖는 유한 집합 $S$ 위에 특정 조건을 만족시키며 추이적으로 작용할 때 정의되며, 프로베니우스 핵 $K$ 와 프로베니우스 여군 $H$ 의 반직접곱으로 표현된다.
기하군론 - 자유군
자유군은 집합 S로부터 생성되는 군의 한 종류로, 닐센-슈라이어 정리를 만족하며 바나흐-타르스키 역설 등 다양한 분야에 응용된다.
기하군론 - 종순군
종순군은 하르 측도를 가지며 좌(또는 우) 이동에 대해 불변인 링 측도를 갖는 국소 콤팩트 하우스도르프 군의 일종이며, 가환적인 경우 좌불변 또는 우불변 평균을 허용하고 군의 작용이 종순 작용을 가질 때 해당 작용을 종순 작용이라고 한다.

케일리 그래프
그래프 정보
유형	수학적 그래프
정의	군에서 유도된 그래프
속성	대칭적 꼭짓점-추이적 t-추이적, t ≥ 2
관련 용어
영어	Cayley graph, Cayley diagram
관련 항목	자유군 F₂
예시
군	PSL Z

2. 정의

군 `G`와 그 부분집합 `S`가 주어졌을 때, 케일리 그래프 `Γ(G,S)`는 다음과 같이 정의된다.

`G`의 각 원소를 꼭짓점으로 갖는다.
각각의 원소 `h∈G`와 `s∈S`에 대하여, `h`와 `sh`를 연결하는 변을 갖는다.
`S`가 `G`의 생성집합이면 `Γ(G,S)`는 연결그래프가 되고, 그렇지 않으면 비연결 그래프가 된다.

2. 1. 방향 그래프 및 색칠

`S⁻¹=S` 및 `1∉S`라고 할 때, 케일리 그래프는 `|S|/2`색의 자연스러운 변 색칠을 갖는다. 색의 집합은 `S/(x∼x⁻¹ ∀x∈G)`이며, 변 `gh∈E(Γ(G,S))`의 색은 `{gh⁻¹,hg⁻¹}∈S/(x∼x⁻¹ ∀x∈G)`이다. 케일리 그래프는 `G`의 자연스러운 작용을 가지며, 이는 그래프의 자기동형사상이다.^[2]

군 `G`와 `G`의 생성 집합 `S`가 주어졌을 때, 케일리 그래프 `Γ = Γ(G,S)`는 다음과 같이 구성된 색칠된 방향 그래프이다.^[2]

`G`의 각 원소 `g`는 정점에 할당된다. 즉, `Γ`의 정점 집합은 `G`와 동일시된다.
`S`의 각 원소 `s`는 색상 `cₛ`에 할당된다.
모든 `g ∈ G`와 `s ∈ S`에 대해, `g`에 해당하는 정점에서 `gs`에 해당하는 정점으로 가는 색상 `cₛ`의 방향 간선이 존재한다.

`S`의 원소 `s`가 자기 자신의 역원, 즉 `s = s⁻¹`인 경우, 일반적으로 무방향 간선으로 표현된다.

특히 `Γ`가 국소 유한이고 `G`가 유한 생성되는 기하학적 군론에서는 `S`가 유한 집합이라고 가정하는 경우가 많다.

`S`는 때때로 대칭 집합(`S = S⁻¹`)이며 군의 항등원을 포함하지 않는다고 가정한다. 이 경우, 색칠되지 않은 케일리 그래프는 단순한 무방향 그래프로 표현될 수 있다.

3. 성질

케일리 그래프 `Γ(G,S)`는 `|S|`-정규 그래프이다. 케일리 그래프의 사이클(닫힌 보행)은 `S`의 원소들 간의 관계를 나타낸다.^[1]

임의의 유한 케일리 그래프는 무방향 그래프로 간주되며, 꼭짓점 연결성은 그래프 차수의 2/3 이상이다. 생성 집합이 최소인 경우, 꼭짓점 연결성은 차수와 같다. 간선 연결성은 모든 경우에 차수와 같다.^[6]

3. 1. 자비두시 정리

'''자비두시 정리'''(Sabidussi theorem^영어)에 따르면, 그래프

\Gamma

에 대하여 다음 두 조건은 서로 동치이다.^[16]

$\Gamma\cong\Gamma(G,S)$ 인 $S\subset G$ 가 존재한다.
$\Gamma$ 위에는 $G$ 의 정추이적 작용이 존재하며, 이 작용은 $\Gamma$ 의 그래프 자기동형사상이다.

이는 오스트리아의 수학자 게르트 자비두시(Gert Sabidussi^de)가 증명하였다.

사비두시 정리는 (레이블과 색상이 없는) 방향 그래프

\Gamma

가

G

에 의한 그래프 자기 동형 사상에 의해 단순 추이적 작용을 허용하는 경우(즉, 방향 간선 집합을 보존하는 경우)에만 그룹

G

의 케일리 그래프라는 것을 나타낸다.^[5]

그래프

\Gamma

가 군

G

의 케일리 그래프일 필요충분조건은 그래프가 그래프 자기 동형 사상으로서 군

G

의 단순 추이적 작용을 갖는 것이다.^[14]

3. 2. 국소 유한성, 유한성, 연결성

군

G

및

1\not\in S=S^{-1}\subset G

에 대하여, 다음은 서로 동치이다.^[16]

$\Gamma(G,S)$ 는 국소 유한 그래프이다. (즉, 모든 꼭짓점의 차수가 유한하다.)
$S$ 는 유한 집합이다.

군

G

및

1\not\in S=S^{-1}\subset G

에 대하여, 다음이 서로 동치이다.

$\Gamma(G,S)$ 는 유한 그래프이다. (즉, 꼭짓점의 수가 유한하다.)
$G$ 는 유한군이다.

군

G

및

1\not\in S=S^{-1}\subset G

에 대하여, 다음이 서로 동치이다.

$\Gamma(G,S)$ 는 연결 그래프이다.
$G=\langle S\rangle$ 이다. 즉, $S$ 는 $G$ 의 생성 집합이다.

\Gamma(G,S)

의 연결 성분의 수는 부분군의 지표

|G:\langle S\rangle|

이다.

3. 3. 군 표현 및 스펙트럼

케일리 그래프는 그룹의 표현론 및 스펙트럼 이론과 밀접하게 관련되어 있다.

\rho_{\text{reg}}(g)(x) = gx

가

|G|\times |G|

행렬 형태로

[\rho_{\text{reg}}(g)]

로 표시되는 왼쪽 정규 표현인 경우, 케일리 그래프

\Gamma(G,S)

의 인접 행렬은

A = \sum_{s\in S} [\rho_{\text{reg}}(s)]

이다.

그룹

G

의 모든 문자

\chi

는

\Gamma(G,S)

의 인접 행렬의 고유벡터를 유도한다. 연관된 고유값은

\lambda_\chi=\sum_{s\in S}\chi(s),

이며,

G

가 아벨군일 때, 정수

j = 0,1,\dots,|G|-1.

에 대해

\sum_{s\in S} e^{2\pi ijs/|G|}

의 형태를 취한다. 특히, 자명한 문자(모든 원소를 1로 보내는 문자)의 연관된 고유값은

\Gamma(G,S)

의 차수, 즉

S

의 순서이다.

G

가 아벨군인 경우, 정확히

|G|

개의 문자가 있으며, 모든 고유값을 결정한다. 해당하는 정규 직교 고유벡터 기저는

v_j = \tfrac{1}{\sqrt

}\begin{pmatrix} 1 & e^{2\pi ij/|G|} & e^{2\cdot 2\pi ij/|G|} & e^{3\cdot 2\pi ij/|G|} & \cdots & e^{(|G|-1)2\pi ij/|G|}\end{pmatrix}.로 주어진다.

일반적으로 대칭 생성 집합의 경우,

\rho_1,\dots,\rho_k

를

G

의 완전한 기약 표현 집합으로 하고,

\rho_i(S) = \sum_{s\in S} \rho_i(s)

를 고유값 집합

\Lambda_i(S)

로 둔다. 그러면

\Gamma(G,S)

의 고유값 집합은 정확히

\bigcup_i \Lambda_i(S),

이며, 고유값

\lambda

는

\rho_i(S)

의 고유값으로

\lambda

가 나타날 때마다

\dim(\rho_i)

의 중복도로 나타난다.^[7]

군의 구조에 관한 지식은 그래프의 인접 행렬과 특히 스펙트럼 그래프 이론의 정리를 적용함으로써 얻을 수 있다.

4. 예

무한 순환군

\mathbb Z

의 케일리 그래프는 무한 경로 그래프이다. 순환군의 케일리 그래프는 순환 그래프이다. 임의의 곱군의 케일리 그래프는 각 성분의 케일리 그래프의 데카르트 곱 그래프이다. 자유군의 케일리 그래프는 무한 4차 나무이며, 바나흐-타르스키 역설의 증명에 등장한다.^[3]

$G=\Z$ 가 무한 순환군이고, 집합 $S$ 가 표준 생성자 1과 그 역원(-1)으로 구성되어 있다면, 케일리 그래프는 무한 경로가 된다.
$G=\Z_n$ 이 차수 $n$ 인 유한 순환군이고, 집합 $S$ 가 $G$ 의 표준 생성자와 그 역원으로 구성되어 있다면, 케일리 그래프는 사이클 $C_n$ 이다. 더 일반적으로 유한 순환군의 케일리 그래프는 순환 그래프이다.
군의 직접곱의 케일리 그래프는 해당 케일리 그래프의 데카르트 곱이다.^[3] 따라서, 아벨 군 $\Z^2$ 의 케일리 그래프는 네 개의 원소 $(\pm 1,0),(0,\pm 1)$ 로 구성된 생성 집합을 가지며, 이는 평면 $\R^2$ 상의 무한 격자 그래프이고, 직접곱 $\Z_n \times \Z_m$ 의 경우 유사한 생성자를 가지는 케일리 그래프는 토러스상의 $n\times m$ 유한 격자이다.
두 생성자 $a$ 와 $b$ 에 대한 자유군의 케일리 그래프는 집합 $S = \{a, b, a^{-1}, b^{-1}\}$ 에 해당하며, 문서 상단에 묘사되어 있다. 자유군은 관계가 없기 때문에 케일리 그래프에는 사이클이 없다. 즉, 4-정규 무한 트리이다.
베테 격자 또는 케일리 트리는 $n$ 개의 생성자에 대한 자유군의 케일리 그래프이다.

4. 1. 이면체군

두 생성자

a

와

b

에 대한 이면체군

D_4

의 케일리 그래프가 왼쪽에 묘사되어 있다. 빨간색 화살표는

a

와의 합성을 나타낸다.

b

가 자기 역원이므로

b

와의 합성을 나타내는 파란색 선은 무방향이다. 따라서 그래프는 혼합되어 있으며, 8개의 정점, 8개의 화살표, 4개의 변을 갖는다. 그룹

D_4

의 군 표현은 다음과 같다.

\langle a, b \mid a^4 = b^2 = e, a b = b a^3 \rangle.

다른

D_4

의 케일리 그래프가 오른쪽에 표시되어 있다.

b

는 여전히 수평 반사이며 파란색 선으로 표시되고,

c

는 대각선 반사이며 분홍색 선으로 표시된다. 두 반사 모두 자기 역원이므로, 오른쪽에 있는 케일리 그래프는 완전히 무방향이다. 이 그래프는 다음 표현에 해당한다.

\langle b, c \mid b^2 = c^2 = e, bcbc = cbcb \rangle.

^[3]

4. 2. 하이젠베르크 군

하이젠베르크군의 케일리 그래프의 일부 (색상은 시각적 보조 도구일 뿐이다.)

이산 하이젠베르크군은 다음과 같이 표현될 수 있다.

:

\left\{ \begin{pmatrix}1 & x & z\\0 & 1 & y\\0 & 0 & 1\\\end{pmatrix},\ x,y,z \in \Z\right\}

이 군의 케일리 그래프는 오른쪽에 묘사되어 있다. 그림에 사용된 생성자는

x, y, z

항목에 대해 1, 0, 0의 세 가지 순열로 주어진 세 개의 행렬

X, Y, Z

이다. 이들은 관계

Z = XYX^{-1}Y^{-1}, XZ = ZX, YZ = ZY

를 만족하며, 그림에서도 확인할 수 있다.^[4] 이는 비가환군이며 무한군이고, 3차원 공간에 포함되어 있음에도 불구하고, 케일리 그래프는 4차원 부피 성장을 갖는다.^[4]

5. 역사

아서 케일리가 1878년에 도입하였다.^[1] 1909년에 막스 덴이 이를 재발견하였으며, "군 그림"(Gruppenbild|그루펜빌트^de)이라고 이름붙였다.^[2] 막스 덴은 1909~1910년 그룹 이론에 대한 미발표 강의에서 케일리 그래프를 재도입했으며, 이는 오늘날의 기하학적 군론으로 이어졌다. 그의 가장 중요한 응용 분야는 종수 ≥ 2인 곡면의 기본군에 대한 단어 문제의 해법으로, 이는 표면에서 어떤 닫힌 곡선이 점으로 수축하는지 결정하는 위상학적 문제와 동등하다.^[11]

6. 확장 성질

$S = S^{-1}$ 일 때 케일리 그래프 $\Gamma(G,S)$ 는 $|S|$ -정규 그래프이므로, 스펙트럼 그래프 이론 기법을 사용하여 그래프의 확장 성질을 분석할 수 있다. 특히 아벨 군의 경우 케일리 그래프의 고유값을 더 쉽게 계산할 수 있으며, $\lambda_\chi = \sum_{s\in S} \chi(s)$ 로 주어지고 최대 고유값은 $|S|$ 이다. 따라서 Cheeger의 부등식을 사용하여 스펙트럼 갭을 통해 에지 확장 비율을 제한할 수 있다.

표현론은 이러한 확장 케일리 그래프를 구성하는 데 사용될 수 있다.

6. 1. 카즈단 성질 (T)

이산 군

G

가 카즈단의 성질 (T)를 가지고,

S

가

G

의 유한 대칭 생성 집합이라면,

G, S

에만 의존하는 상수

c>0

가 존재하여,

G

의 모든 유한 몫

Q

에 대해

S

의 상에 대한

Q

의 케일리 그래프는

c

-확장 그래프이다.^[8]

예를 들어, 군

G = \mathrm{SL}_3(\Z)

는 (T) 성질을 가지며 기본 행렬에 의해 생성되므로, 이것은 확장 그래프의 상대적으로 명시적인 예를 제공한다.

7. 케일리 적분 그래프

적분 그래프는 고유값이 모두 정수인 그래프이다. 특정 그룹의 케일리 그래프는 항상 적분 그래프이다. 케일리 그래프 $\Gamma(G,S)$가 적분 그래프가 되기 위한 필요충분조건은 $G$의 모든 표현 $\rho$에 대해 $\rho(S)$의 고유값이 정수인 것이다.

7. 1. 케일리 정수 단순군 (CIS)

군 $G$가 연결된 케일리 그래프 $\Gamma(G,S)$가 대칭 생성 집합 $S$가 $G$의 부분군의 여집합일 때 정확히 정수적이면 케일리 정수 단순(CIS)이라고 한다. Ahmady, Bell, 및 Mohar의 결과에 따르면 모든 CIS 군은 소수 $p$에 대해 $ℤ/^영어pℤ^영어$, $ℤ/^영어p^2ℤ^영어$ 또는 $ℤ^영어_2 \times ℤ^영어_2$와 동형이다.^[9] 케일리 그래프가 연결되려면 $S$가 실제로 전체 군 $G$를 생성하는 것이 중요하다. (만약 $S$가 $G$를 생성하지 않으면 케일리 그래프는 여전히 정수적일 수 있지만, $S$의 여집합은 반드시 부분군일 필요는 없다.)

$G=ℤ/^영어5ℤ^영어$의 예에서, 대칭 생성 집합(그래프 동형까지)은 다음과 같다.

$S = \{1,4\}$: $\Gamma(G,S)$는 고유값 $2, \tfrac{\sqrt{5}-1}{2},\tfrac{\sqrt{5}-1}{2},\tfrac{-\sqrt{5}-1}{2},\tfrac{-\sqrt{5}-1}{2}$를 갖는 $5$-사이클이다.
$S = \{1,2,3,4\}$: $\Gamma(G,S)$는 고유값 $4, -1,-1,-1,-1$를 갖는 $K_5$이다.

$ℤ/^영어5ℤ^영어$의 유일한 부분군은 전체 군과 자명군이며, 정수 그래프를 생성하는 유일한 대칭 생성 집합 $S$는 자명군의 여집합이다. 따라서 $ℤ/^영어5ℤ^영어$는 CIS 군이어야 한다.

완전한 CIS 분류의 증명은 CIS 군의 모든 부분군 및 준동형 이미지가 또한 CIS 군이라는 사실을 사용한다.^[9]

7. 2. 케일리 적분군

어떤 군에서 모든 대칭 부분 집합 S에 대해 케일리 그래프 Γ(G,S)가 적분 그래프이면, 그 군을 케일리 적분군이라고 한다. 여기서 S는 전체 군을 생성할 필요는 없다. 케일리 적분 군의 전체 목록은

\mathbb{Z}_2^n\times \mathbb{Z}_3^m,\mathbb{Z}_2^n\times \mathbb{Z}_4^n, Q_8\times \mathbb{Z}_2^n,S_3

와 12차 디사이클릭 군으로 주어지며, 여기서

m,n\in \mathbb{Z}_{\ge 0}

이고

Q_8

는 사원수 군이다.^[9]

참조

_[1] 서적 Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations https://books.google[...] Courier
_[2] 논문 Desiderata and suggestions: No. 2. The Theory of groups: graphical representation https://babel.hathit[...]
_[3] 학위논문 An extension of the concept of graphically regular representations University of Wisconsin, Madison
_[4] 학회자료 Groups, graphs and random walks: Selected papers from the workshop held in Cortona, June 2–6, 2014 Cambridge Univ. Press, Cambridge
_[5] 논문 On a class of fixed-point-free graphs 1958-10
_[6] 서적 Handbook of Combinatorics https://books.google[...] Elsevier
_[7] 논문 On the genus of a group
_[8] 논문 Expander graphs in pure and applied mathematics
_[9] 논문 Integral Cayley graphs and groups
_[10] 논문 Integral Cayley graphs https://link.springe[...]
_[11] 서적 Papers on Group Theory and Topology Springer-Verlag
_[12] 논문 Desiderata and suggestions: No. 2. The Theory of groups: graphical representation https://babel.hathit[...]
_[13] 학위논문 An extension of the concept of graphically regular representations University of Wisconsin, Madison
_[14] 논문 On a Class of Fixed-Point-Free Graphs 1958-10
_[15] 서적 Papers on Group Theory and Topology Springer-Verlag
_[16] 논문 On a Class of Fixed-Point-Free Graphs
_[17] 논문 Desiderata and suggestions. № 2. The theory of groups: graphical representation https://archive.org/[...] 1878

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

문의하기 : help@durumis.com