케일리 그래프

군론과 그래프 이론에서 케일리 그래프(영어: Cayley graph)는 군의 구조를 반영하는 그래프이다.

정의

군 ${\displaystyle G}$ 및 부분집합 ${\displaystyle S\subset G}$가 주어졌다고 하자. 케일리 그래프 ${\displaystyle \Gamma (G,S)}$는 다음과 같은 그래프이다.

• ${\displaystyle G}$의 원소를 꼭짓점으로 갖는다. 즉 ${\displaystyle V(\Gamma (G,S))=G}$.
• 각각의 원소 ${\displaystyle h\subset G}$와 ${\displaystyle s\subset S}$에 대하여, ${\displaystyle h}$와 ${\displaystyle sh}$를 연결하는 변을 갖는다. 즉 ${\displaystyle (g,h)\in E(\Gamma (G,S))\iff gh^{-1}\in S}$.

${\displaystyle S}$가 ${\displaystyle G}$의 생성집합일 때, ${\displaystyle \Gamma (G,S)}$는 연결그래프가 되고, 그렇지 않을 때 비연결 그래프가 된다.

${\displaystyle S^{-1}=S}$ 및 ${\displaystyle 1\not \in S}$라고 할 때, 케일리 그래프는 ${\displaystyle |S|/2}$색의 자연스러운 변 색칠을 갖는다. 색의 집합은 ${\displaystyle S/(x\sim x^{-1}\;\forall x\in G)}$이며, 변 ${\displaystyle gh\in E(\Gamma (G,S))}$의 색은

${\displaystyle \{gh^{-1},hg^{-1}\}\in S/(x\sim x^{-1}\;\forall x\in G)}$

이다. 또한, 케일리 그래프는 ${\displaystyle G}$의 자연스러운 작용을 가지며, 이는 그래프의 자기동형사상이다.

성질

자비두시 정리(영어: Sabidussi theorem)에 따르면, 그래프 ${\displaystyle \Gamma }$에 대하여, 다음 두 조건이 서로 동치이다.

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

이는 오스트리아의 수학자 게르트 자비두시(독일어: Gert Sabidussi)가 증명하였다.^[1]

케일리 그래프 ${\displaystyle \Gamma (G,S)}$는 ${\displaystyle |S|}$-정규 그래프이다.

군 ${\displaystyle G}$ 및 ${\displaystyle 1\not \in S=S^{-1}\subset G}$에 대하여, 다음이 서로 동치이다.

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

군 ${\displaystyle G}$ 및 ${\displaystyle 1\not \in S=S^{-1}\subset G}$에 대하여, 다음이 서로 동치이다.

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

군 ${\displaystyle G}$ 및 ${\displaystyle 1\not \in S=S^{-1}\subset G}$에 대하여, 다음이 서로 동치이다.

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

${\displaystyle \Gamma (G,S)}$의 연결 성분의 수는 부분군의 지표 ${\displaystyle |G:\langle S\rangle |}$이다.

예

자유군의 케일리 그래프 ${\displaystyle \Gamma (\langle a,b\rangle ,\{a,b,a^{-1},b^{-1}\})}$

무한 순환군 ${\displaystyle \mathbb {Z} }$의 케일리 그래프 ${\displaystyle \Gamma (\mathbb {Z} ,\{\pm 1\})\cong P_{\infty }}$는 무한 경로 그래프이다.

순환군의 케일리 그래프 ${\displaystyle \Gamma (\mathbb {Z} /n,\{\pm 1\})\cong C_{n}}$는 순환 그래프이다.

임의의 곱군 ${\displaystyle G\times H}$의 케일리 그래프는 각 성분의 케일리 그래프의 데카르트 곱 그래프이다.

${\displaystyle \Gamma (G\times H,S_{G}\times S_{H})\cong \Gamma (G,S_{G})\square \Gamma (H,S_{H})}$

자유군 ${\displaystyle \langle a,b\rangle }$의 케일리 그래프 ${\displaystyle \Gamma (\langle a,b\rangle ,\{a,b,a^{-1},b^{-1}\})}$는 무한 4차 나무이다. 이 케일리 그래프는 바나흐-타르스키 역설의 증명에 등장한다.

역사

아서 케일리가 1878년에 도입하였다.^[2] 막스 덴이 1909년에 이를 재발견하였으며, "군 그림"(독일어: Gruppenbild 그루펜빌트^[*], 독일어: Gruppe 그루페^[*](군) + 독일어: Bild 빌트^[*](그림))이라고 이름붙였다.

같이 보기

• 대수적 그래프 이론