凯莱图

维基百科,自由的百科全书
跳转至: 导航搜索
在两个生成元ab上的自由群的凯莱图

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

定义[编辑]

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

  • ,每个元素,指派一个顶点:,的顶点集合,同一于,。
  • ,的每个生成元,指派一种颜色,。
  • 对于任何,对应于元素,和,的顶点用颜色,的有向边连接。因此边集合,由形如,的有序对构成,带着提供的颜色。

在几何群论中,集合,通常被假定为有限的、“对称的”也就是,并且不包含这个群的单位元。在这种情况下,凯莱图是正常的:它的边没有方向并且不包含环路。

例子[编辑]

  • 假设G = Z是无限循环群而集合S有标准生成元1和它的逆元(用加法符号为−1)构成,则它的凯莱图是无穷链。
  • 类似的,如果G = Znn循环群S由两个元素构成,G的标准生成元和它的逆元,则凯莱图是环图Cn
  • 群的直积的凯莱图是对应的凯莱图的笛卡尔积。因此带有四个元素(±1, ±1)组成的生成集的阿贝尔群Z2的凯莱图是在平面R2上无穷网格,而带有类似的生成集的直积Zn×Zm的凯莱图是在环面nm有限网格。
二面体群D4在两个生成元ab上的凯莱图。
  • 二面体群D4在两个生成元ab上的凯莱图列于右侧。红色箭头表示左乘元素a。因此元素b自我逆转的,表示左乘元素b蓝色线是无方向的。因此这个图是混合的:它有8个顶点,8个有向边,4个边。群D4凯莱表可以从群展示得出:
  • 在对应于集合S = {a, b, a−1, b−1}的两个生成元a, b上的自由群的凯莱图列出在文章开头,这里的e表示单位元。沿着边向右走表示右乘a,而沿着变向上走表示乘以b。因为自由群没有关系,它的凯莱图中没有。这个凯莱图是证明巴拿赫-塔斯基悖论的关键因素。

特征[编辑]

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

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

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

基本性质[编辑]

  • 如果生成集合的成员是自身的逆元,即,则它一般被表示为无向边。
  • 凯莱图本质上依赖于生成元的集合的选择方式。例如,如果生成集合个元素,则凯莱图的每个顶点都有个进入和个外出的有向边。在有个元素的对称生成集合的情况下,凯莱图是度的正则图
  • 在凯莱图中的(“闭合路径”)指示在的两个元素之间的关系。在群的凯莱复形的更精细构造中,对应于关系的闭合路径被用多边形“填充”。
  • 如果满射群同态并且的生成集合的元素的像是不同的,则它引发一个图的覆盖
这里的,。
特别是,如果群个生成元,都有不是2的阶,并且这些生成元和它们的逆元构成集合,则凯莱图由对应于在相同生成集合的自由群度无限正则所覆盖。
  • 可以被构造即使集合不生成群。但是,它是连通的并不被认为是凯莱图。在这种情况下,这个图的每个连通部件表示一个生成子群的陪集。

Schreier陪集图[编辑]

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

与群论的关系[编辑]

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

参见[编辑]

注释[编辑]

  1. ^ Babai, L. Technical Report TR-94-10. University of Chicago. 1996. 存档副本. [2010-08-29]. (原始内容存档于2010-06-11).