CayLey引自Wikipedia

凯莱图

在数学中，凯莱图也叫做凯莱着色图是编码离散群的图。它的定义是凯莱定理(以阿瑟·凯莱命名)所暗含的，并使用这个群的特定的通常有限的生成元集合。它是组合群论与几何群论的中心工具。

在两个生成元 a 和 b 上的的凯莱图

二面体群 D₄ 在两个生成元 α 和 β 上的凯莱图。

定义

假设 G \, 是群而 S \, 是生成集。凯莱图 \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} \,，并且不包含这个群的单位元。在这种情况下，凯莱图是正常的图: 它的边没有方向并且不包含环路。

例子

    * 假设 G = Z 是无限循环群而集合 S 有标准生成元 1 和它的逆元(用加法符号为 −1)构成，则它的凯莱图是无穷链。

    * 类似的，如果 G = Zn 是 n 阶循环群而 S 由两个元素构成，G 的标准生成元和它的逆元，则凯莱图是环图 Cn。

    * 群的直积的凯莱图是对应的凯莱图的笛卡尔积。因此带有四个元素(±1, ±1)组成的生成集的阿贝尔群 Z2 的凯莱图是在平面 R2 上无穷网格，而带有类似的生成集的直积 Zn × Zm 的凯莱图是在环面上 n 乘 m 有限网格。

二面体群 D4 在两个生成元 α 和 β 上的凯莱图。

    * 二面体群 D4 在两个生成元 α 和 β 上的凯莱图列于右侧。红色箭头表示左乘元素 α。因此元素 β 是自我逆转的，表示左乘元素 β 蓝色线是无方向的。因此这个图是混合的: 它有 8 个顶点，8 个有向边，4 个边。群 D4 的凯莱表可以从群展示得出:

    \langle \alpha, \beta | \alpha^4 = \beta^2 = e, \alpha \beta = \beta \alpha^3 \rangle 。

    * 在对应于集合 S = {a, b, a−1, b−1} 的两个生成元 a, b 上的自由群的凯莱图列出在文章开头，这里的 e 表示单位元。沿着边向右走表示右乘 a，而沿着变向上走表示乘以 b。因为自由群没有关系，它的凯莱图中没有环。这个凯莱图是证明巴拿赫-塔斯基悖论的关键因素。

特征

群 G 通过左乘作用在自身上(参见凯莱定理)。这个作用可以看作 G 作用在它的凯莱图上。明显的，一个元素 h\in G 映射一个顶点 g\in V(\Gamma) 到顶点 hg\in V(\Gamma)。凯莱图的边集合被这个作用所保存: 边 (g,gs) 变换成边 (hg,hgs)。任何群在自身上的左乘作用是简单传递的，特别是凯莱图是顶点传递的。这导致了凯莱图的下列特征:

    图 Γ 是群 G 的凯莱图，当且仅当它通过图自同构许可 G 的简单传递作用(就是保存边的集合)。

要从一个凯莱图 Γ = Γ(G,S) 恢复群 G 和生成集 S，选择一个顶点 v_1\in V(\Gamma) 并标记上这个群的单位元。接着对每个 Γ 的顶点 v 标记上变换 v1 到 v 的 G 的唯一元素。产生 Γ 为凯莱图的 G 的生成元的集合 S 是毗连到选择的顶点的顶点的标记的集合。生成集合是有限(这是凯莱图的共同假定)当且仅当这个图是局部有限的(就是说每个顶点毗连与有限多个边)。

基本性质

    * 如果生成集合的成员 s 是自身的逆元，即 s = s − 1，则它一般被表示为无向边。

    * 凯莱图 Γ(G,S) 本质上依赖于生成元的集合 S 的选择方式。例如，如果生成集合 S 有 k 个元素，则凯莱图的每个顶点都有 k 个进入和 k 个外出的有向边。在有 r 个元素的对称生成集合 S 的情况下，凯莱图是 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，则凯莱图 Γ(G,S) 由对应于在相同生成集合的自由群的 2k 度无限正则树所覆盖。

    * 图 Γ(G,S) 可以被构造即使集合 S 不生成群 G。但是，它是连通的并不被认为是凯莱图。在这种情况下，这个图的每个连通部件表示一个 S 生成子群的陪集。

    * 对于被认为是无向的凯莱图，顶点连通性等于这个图的度。[1]

Schreier陪集图

如果转而把顶点作为固定子群 H 的右陪集，就得到了一个有关的构造Schreier陪集图，它是陪集枚举或Todd-Coxeter算法的基础。

与群论的关系

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

参见

    * 群的生成集合

    * 群的展示

注释

   1. ^ Babai, L.（1996）．Technical Report TR-94-10．University of Chicago． [1]