케일리 그래프

틀:위키데이터 속성 추적 군론과 그래프 이론에서 케일리 그래프(틀:Llang)는 군의 구조를 반영하는 그래프이다.

정의

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

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

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

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

$\{g{h}^{-1},h{g}^{-1}\}\in S/(x\sim x^{-1}\mathrm{\forall }x\in G)$

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

성질

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

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

이는 오스트리아의 수학자 게르트 자비두시(틀:Llang)가 증명하였다.

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

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

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

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

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

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

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

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

예

자유군의 케일리 그래프 $\mathrm{\Gamma }(⟨a,b⟩,\{a,b,a^{-1},b^{-1}\})$

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

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

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

$\mathrm{\Gamma }(G\times H,S_G\times S_H)\cong \mathrm{\Gamma }(G,S_G)◻\mathrm{\Gamma }(H,S_H)$

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

역사

아서 케일리가 1878년에 도입하였다. 막스 덴이 1909년에 이를 재발견하였으며, "군 그림"(틀:Llang, 틀:Llang(군) + 틀:Llang(그림))이라고 이름붙였다.

같이 보기

• 대수적 그래프 이론

외부 링크

• 틀:매스월드