凯莱图

凯莱图(英语:Cayley graph),也叫做凯莱着色图,是将离散群的抽象结构画出的一种。它的定义是凯莱定理(以阿瑟·凯莱命名)所暗含的。画凯莱图时,要选定群的一个生成元集合(通常有限),不同选法可能得到不同的凯莱图。凯莱图是组合群论英语Combinatorial group theory几何群论英语Geometric group theory的中心工具。

在两个生成元ab上的自由群的凯莱图

定义

假设 ,而 G的生成集。凯莱图 ,是如下构造的着色的有向图

  •  的每个元素 对应一个顶点。换言之,图 的顶点集合 视为与 等同;
  •  中每个生成元 ,对应一种颜色 
  • 对于任何 ,画一条由元素  有向边,染成 色。换言之,边集合 由形如 的有序对构成,边的颜色由 确定。

在几何群论中,集合 通常取为有限、对称(即满足 ),并且不包含这个群的单位元 。在这种情况下,凯莱图是简单无向图:它的边没有方向(由对称性),并且不包含自环(因为 )。

例子

 
的凯莱图。所用的三个生成元 ,分别对应 。其关系为 ,亦可从图中看出。本群为非交换无穷群。虽然是三维空间,其凯莱图的增长英语Growth rate (group theory)却是 阶的。[来源请求]

特征

 通过左乘作用在自身上(参见凯莱定理)。这个作用可以看作 作用在它的凯莱图上。明确而言,一个元素 映射一个顶点 到另一个顶点 。凯莱图的边集合被这个作用所保存:边 变换成边 。任何群在自身上的左乘作用是简单传递的,特别是凯莱图是顶点传递英语Vertex-transitive graph的。事实上,反向的结论也成立,即有下列等价刻划,称为扎比杜西定理(英语:Sabidussi's Theorem):

(无标记又无着色)有向图 是群 的某个凯莱图,当且仅当 可作为图自同构(就是要保存边的集合)作用在 上,且该作用简单传递。[1]

要从一个凯莱图 找回群 和生成集 ,先选择一个顶点 ,标上群的单位元 。接着,对 的每个顶点  中有唯一元素将 变换到 ,于是可以在 处标记该唯一元素。最后要确定 的哪个生成集 ,产生凯莱图 ,而所求的 就是毗连 的顶点标记的集合。生成集合是有限(这是凯莱图的共同假定)当且仅当这个图是局部有限的(就是说每个顶点仅毗连于有限多条边)。

基本性质

  • 如果生成集合的成员 是自身的逆元,即 ,则它一般被表示为无向边
  • 凯莱图 本质上依赖于如何选择生成集 。例如,如果生成集合  个元素,则凯莱图的每个顶点都有 有向边进入, 条有向边外出。当生成集合 为对称集,且有 个元素时,凯莱图是 度的正则图
  • 在凯莱图中的(“闭合路径”)指示 的元素之间的关系。在群的凯莱复形此一更复杂的构造中,对应于关系的闭合路径被用多边形“填充”。
  • 如果 满射群同态并且 的生成集合 的元素的像是不同的,则导出图覆叠英语Covering graph映射
     
    这里的 ,特别是,如果群  个生成元,阶均不为 ,并且这些生成元和它们的逆元构成集合 ,则该集合生成的自由群 有到 的满同态(商映射),故 被自由群的凯莱图覆盖,即 度的无限正则
  • 即使集合 不生成群 ,仍可以构造图 。但是,此情况下,所得的图并不连通。在这种情况下,这个图的每个连通分支对应 所生成子群的一个陪集。
  • 对于有限凯莱图(视为无向),其顶点连通性等于这个图的 。若生成集极小(即移除任一元素及其逆元,就不再生成整个群),则其顶点连通性等于度数。[2]至于边连通性,则在任何情况下皆等于度数。[3]
  •  的每个乘性特征标英语Multiplicative character 都给出 邻接矩阵特征向量。若 为交换群,则对应的特征值 特别地,平凡特征标(将所有元素映至常数 )对应的特征值,等于 的度数,即 的元素个数。若 为交换群,则恰有 个特征标,故已足以确定全部特征值。

Schreier陪集图

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

与群论的关系

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

参见

注释

  1. ^ Sabidussi, Gert. On a class of fixed-point-free graphs [论一类无不动点的图]. Proceedings of the American Mathematical Society. October 1958, 9 (5): 800–4. JSTOR 2033090. doi:10.1090/s0002-9939-1958-0097068-7  (英语). 
  2. ^ Babai, L. Technical Report TR-94-10. University of Chicago. 1996. 存档副本. [2010-08-29]. (原始内容存档于2010-06-11). 
  3. ^ 见定理3.7,Babai, László. 27. Automorphism groups, isomorphism, reconstruction [第27章:自同构群、同构、重构] (PDF). Graham, Ronald L.; Grötschel, Martin; Lovász, László (编). Handbook of Combinatorics [组合手册] 1. Elsevier. 1995: 1447–1540 [2021-09-29]. ISBN 9780444823465. (原始内容存档于2021-04-22).