凱萊圖

<image>

凱萊圖（Cayley graph），也叫做凱萊著色圖，是將離散群的抽象結構畫出的一種圖。它的定義是凱萊定理（以阿瑟·凱萊命名）所暗含的。畫凱萊圖時，要選定群的一個生成元集合（通常有限），不同選法可能得到不同的凱萊圖。凱萊圖是組合群論與幾何群論的中心工具。

## 定義

假設$G$是群，而$S$是G的生成集。凱萊圖$\Gamma=\Gamma(G,S)$，是如下構造的著色的有向圖：

- $G$的每個元素$g$對應一個頂點。換言之，圖$\Gamma$的頂點集合$V(\Gamma)$視為與$G$等同。
- $S$中每個生成元$s$，對應一種顏色$c_s$。
- 對於任何$g\in G, s\in S$，畫一條由元素$g$至$gs$的有向邊，染成$c_s$色。換言之，邊集合$E(\Gamma)$由形如$(g, gs)$的有序對構成，邊的顏色由$s\in S$確定。

在幾何群論中，集合$S$通常取為有限、對稱（即滿足$S=S^{-1}$），並且不包含這個群的單位元$e$。在這種情況下，凱萊圖是簡單無向圖：它的邊沒有方向（由對稱性），並且不包含自環（因為$e \notin S$）。

## 例子

- 假設$G = \mathbb Z$是無限循環群（即整數的加法群），而集合$S$由標準生成元$1$和它的逆元（用加法符號為$-1$）構成，則它的凱萊圖是道路圖。
- 類似地，如果$G = \mathbb Z_n$是$n$階循環群（模$n$的加法群），而$S$仍由$G$的標準生成元$1$與逆元$-1$構成，則凱萊圖是環圖$C_n$。
- 群的直積的凱萊圖（新生成集取為原生成集之笛卡爾積），是對應的凱萊圖的圖的笛卡爾積。因此阿貝爾群$\mathbb Z^2$，關於四個元素$(\pm 1, \pm 1)$組成的生成集的凱萊圖，是平面$\mathbb R^2$上的無窮網格，而帶有類似的生成集的直積$\mathbb Z_n \times \mathbb Z_m$的凱萊圖，是環面上的$n$乘$m$有限網格。
- 二面體群$D_4$有群展示：$$\langle a, b | a^4 = b^2 = e, a b = b a^3 \rangle.$$左圖是關於兩個生成元$a$和$b$的凱萊圖，其中紅色箭頭表示左乘元素$a$（順時針旋轉$90^\circ$）。而因為元素$b$（左右反射）自反，所以表示左乘元素$b$的藍色線是無方向的，故左圖混合了有向邊與無向邊：它有$8$個頂點、$8$條有向邊、$4$條無向邊。

<image>

<image>

同一個群$D_4$，亦可畫出不同的凱萊圖，如右圖。$b$仍表示左右反射，而$c$則是關於主對角線的反射，以粉紅色線表示。由於兩個反射皆自反，右邊的凱萊圖完全無向。對應的群展示是$$\langle b, c \mid b^2 = c^2 = e, bcbc = cbcb \rangle.$$
- 條目開頭的圖，是兩個生成元$a, b$上的自由群，關於生成集合$S = \{a, b, a^{-1}, b^{-1}\}$的凱萊圖，而正中央的黑點，是單位元$e$。沿著邊向右走表示右乘$a$，而沿著邊向上走表示乘以$b$。因為自由群沒有關係，它的凱萊圖中沒有環。這個凱萊圖是證明巴拿赫-塔斯基悖論的關鍵。
- 右邊有離散海森堡群

<image>

$$\left\{ \begin{pmatrix} <pre> 1 & x & z\\ 0 & 1 & y\\ 0 & 0 & 1\\ </pre> \end{pmatrix},\ x,y,z \in \Z\right\}$$ 的凱萊圖。所用的三個生成元$X, Y, Z$，分別對應$(x, y, z) = (1, 0, 0),\ (0, 1, 0),\ (0, 0, 1)$。其關係為$Z = XYX^{-1}Y^{-1},\ XZ = ZX,\ YZ = ZY$，亦可從圖中看出。本群為非交換無窮群。雖然是三維空間，其凱萊圖的增長率 (群論)卻是$4$階的。

## 特徵

群$G$通過左乘作用在自身上（參見凱萊定理）。這個作用可以看作$G$作用在它的凱萊圖上。明確而言，一個元素$h\in G$映射一個頂點$g\in V(\Gamma)$到另一個頂點$hg\in V(\Gamma)$。凱萊圖的邊集合被這個作用所保存：邊$(g,gs)$變換成邊$(hg,hgs)$。任何群在自身上的左乘作用是簡單傳遞的，特別是凱萊圖是頂點傳遞圖的。事實上，反向的結論也成立，即有下列等價刻劃，稱為扎比杜西定理（Sabidussi's Theorem）：

（無標記又無著色）有向圖$\Gamma$是群$G$的某個凱萊圖，當且僅當$G$可作為圖自同構（就是要保存邊的集合）作用在$\Gamma$上，且該作用簡單傳遞。

要從一個凱萊圖$\Gamma=\Gamma(G,S)$找回群$G$和生成集$S$，先選擇一個頂點$v_1\in V(\Gamma)$，標上群的單位元$e$。接著，對$\Gamma$的每個頂點$v$，$G$中有唯一元素將$v_1$變換到$v$，於是可以在$v$處標記該唯一元素。最後要確定$G$的哪個生成集$S$，產生凱萊圖$\Gamma$，而所求的$S$就是毗連$v_1$的頂點標記的集合。生成集合是有限（這是凱萊圖的共同假定）當且僅當這個圖是局部有限的（就是說每個頂點僅毗連於有限多條邊）。

## 基本性質

- 如果生成集合的成員$s$是自身的逆元，即$s=s^{-1}$，則它一般被表示為無向邊。
- 凱萊圖$\Gamma(G,S)$本質上依賴於如何選擇生成集$S$。例如，如果生成集合$S$有$k$個元素，則凱萊圖的每個頂點都有$k$條有向邊進入，$k$條有向邊外出。當生成集合$S$為對稱集，且有$r$個元素時，凱萊圖是$r$度的正則圖。
- 在凱萊圖中的環（「閉合路徑」）指示$S$的元素之間的關係。在群的凱萊複形此一更複雜的構造中，對應於關係的閉合路徑被用多邊形「填充」。
- 如果$f: G'\to G$是滿射群同態並且$G'$的生成集合$S'$的元素的像是不同的，則導出圖覆疊映射$$\bar{f}: \Gamma(G',S')\to \Gamma(G,S),\quad$$這里的$S=f(S')$，特別是，如果群$G$有$k$個生成元，階均不為$2$，並且這些生成元和它們的逆元構成集合$S$，則該集合生成的自由群$F(S)$有到$G$的滿同態（商映射），故$\Gamma(G,S)$被自由群的凱萊圖覆蓋，即$2k$度的無限正則樹。
- 即使集合$S$不生成群$G$，仍可以構造圖$\Gamma(G,S)$。但是，此情況下，所得的圖並不連通。在這種情況下，這個圖的每個連通分支對應$S$所生成子群的一個陪集。
- 對於有限凱萊圖（視為無向），其頂點連通性等於這個圖的度的$2/3$。若生成集極小（即移除任一元素及其逆元，就不再生成整個群），則其頂點連通性等於度數。至於邊連通性，則在任何情況下皆等於度數。
- 群$G$的每個乘性特徵標$\chi$都給出$\Gamma(G,S)$鄰接矩陣的特徵向量。若$G$為交換群，則對應的特徵值為$\lambda_\chi=\sum_{s\in S}\chi(s).$特別地，平凡特徵標（將所有元素映至常數$1$）對應的特徵值，等於$\Gamma(G,S)$的度數，即$S$的元素個數。若$G$為交換群，則恰有$|G|$個特徵標，故已足以確定全部特徵值。

## Schreier陪集圖

如果轉而把頂點作為固定子群$H$的右陪集，就得到了一個有關的構造Schreier陪集圖，它是陪集枚舉或Todd-Coxeter演算法的基礎。

## 與群論的關係

研究圖的鄰接矩陣特別是應用譜圖理論的定理能洞察群的結構。