凯莱图

<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算法的基础。

## 与群论的关系

研究图的邻接矩阵特别是应用谱图理论的定理能洞察群的结构。