K_5,5− 5K₂覆盖变换群为S₄的正则覆盖的分类

2-Arc-Transitive Regular Covers of K_5,5 − 5K₂ with the Covering Transformation Group S₄

摘要: 研究对称图的正则覆盖是代数图论的重要课题。为了更深入了解对称图的性质与分类，利用群论的基本知识，本文分类了K_5,5 − 5K₂的正则覆盖，其中覆盖变换群同构于S₄，且保纤维自同构群的作用是2-弧传递的。最后，证明了满足条件的覆盖图是不存在的。

Abstract: Studying the regular covering of symmetric graphs is an important topic in algebraic graph theory. In order to have a deeper understanding of the properties and classification of symmetric graphs, using the basic knowledge of group theory, in this paper, a classification is achieved for all the regular covers of K_5,5 − 5K₂ whose covering transformation group is isomorphic to S₄ and whose fiber-preserving automorphism group acts 2-arc-transitively. It is proved that the covering graph that satisfies the conditions does not exist.

1. 引言

1.1. 研究背景

群论的历史来源主要有三个方向：数论、几何学和代数方程。由于在数论和几何中，人们虽然运用到了群论的观点，但并未明显地提出“群”这个概念，所以从群的发展历史来看，以拉格朗日，柯西，伽罗瓦等人从代数方程角度出发所衍生出来的群论更为人所熟知，它是人们对代数方程求解问题逻辑考察的结果。拉格朗日在研究高次方程的求根问题时第一次正确的指出方程的根的排列与置换关系，1830年伽罗瓦首次提出“群”的概念，并将群论与域论联合起来发展为“伽罗瓦理论”。英国数学家凯莱提出具有一般性的群的概念，作为群抽象化的先驱人物，他摆脱了柯西，伽罗瓦以置换为中心内容的群的概念，向更具高度及一般化的表达推广。1870年，数学家克隆尼科类比凯莱给出的抽象群的概念，提出了相当于现在的有限阿贝尔群的定义。群论的起源不同，导致产生了不同的群论记法。19世纪末，数学家们对不同种类的群已经有了一定的研究积累，基本认清了群的本质，约1880年开始，群的理论开始得到了统一，具有了公理化的定义，群论开辟了全新的研究领域，以结构研究代替计算，把从偏重计算研究的思维方式转变为用结构观念研究的思维方式，并把数学运算归类，迅速发展成为一门全新的数学分支，对近世代数的形成与发展产生了巨大的影响，同时这种理论对于物理学，化学的发展，甚至对于二十世纪结构主义哲学的产生和发展都发生了巨大的影响。

图是由若干给定的顶点及连接两顶点的边所构成的图形，通常用来描述事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。图能把纷杂的信息变的有序、直观、清晰。由于我们感兴趣的是两个对象之间是否有某种特定关系，所以图形中两点间连接与否尤为重要，而图形的位置、大小、形状及连接线的曲直长短则无关紧要。图论起源于著名的“柯尼斯堡七桥问题”，该问题于1736年被欧拉解决。图论作为组合数学的一个分支，和其他数学分支如群论、矩阵论、拓扑学有着密切关系，随着科学的发展，以及生产管理、军事、交通运输等方面提出了大量实际的需要，图论的理论及其应用研究得到飞速发展。

对称性原始意义是指组成一种事物或对象的两个部分的对等性，对称美是数学美的一种特征。随着数学的发展，对称的概念得到了不断地发展，由一个含糊的概念发展为精确的几何概念，至今更为一般的概念是指，元素的构形在自相变换下的不变性。在数学发展史中，可以感受到对于对称性的追求在数学研究中发挥了很大的作用，如代数的多项式方程的虚根的成对出现，线性方程的矩阵和克莱姆法则齐次轮换对称式等。

图是图论的主要研究对象，研究图的对称性一直是图论中的热点问题，研究对称图不仅仅是注重其客观外在的美感，得到许多有意义的图例，更着重追求其蕴含的对称思想和研究问题的方法，对其他和对称性关系密切的学科也有着推动作用。近年来，随着大规模计算机系统和互连网络的飞速发展，图的对称性研究显得尤为重要。一个大型计算机处理系统是由多个处理器组成的，处理器之间的连接模式称为该系统的互连网络，或者简称网络。众所周知，网络可由一个无环的无向图F来模拟，其中顶点集合 $V\left(F\right)$ 表示处理器，边集合 $E\left(F\right)$ 表示处理器之间的连线关系。这样的图称为是网络的拓扑结构。在网络设计中，人们总是希望网络中的所有组件都以相同的方式启动和连接，使得在各结点的容量和连线的负载至少保持某些平衡，这就要求对应的图具有一定的对称性，这也是网络设计的基本原则之一。网络的设计不仅要求其对应图具有一定的对称性，而且还要求其具有一定的容错性，即容许网络中有若干数目的结点和连线发生故障。迄今为止，绝大多数大型计算机系统的网络拓扑都是借助于具有高度对称性的图来表示的，而且借助高度对称性的图设计的网络往往具有很好的容错性。例如，著名的超立方体网络和平衡超立方体网络的拓扑结构都具有较强的对称性和较好的容错性性质。

Higman-Sims单群是作为图的自同构而被发现的，它对于完成有限单群的分类做出了巨大的贡献，同时解答了抽象群和置换群的一些重大问题。随着有限单群分类的完成，群论成为研究图的性质的一种很好的工具。用群论现有的思路和方法来研究组合数学会使其充满新的活力，这也成为如今群论界研究的一个新趋势。R. Frucht (1938)证明了任意给定一个群都存在一个图以它为自同构群，见文献 [1] 。这项重要的工作拉开了群论与图论结合起来进行数学研究的帷幕。图的对称性主要是通过图的全自同构群在图的各个对象上的作用来描述，是关于对称图的研究的重要方面。而弧–传递图是一种具有高度对称性的图例，1960年以后，关于s-弧传递图和s-距离传递图，成果极为丰富。R. Weiss (1981)得到的当 $s\ge 8$ 的时候，不存在s-弧传递的图，见文献 [2] 。更进一步地，对于每一个 $s\in \left\{1,2,3,4,5,7\right\}$ 都存在s-弧传递图。很明显的一件事情是，如果一个群在某个图上的作用是s-弧传递的，其中 $s\ge 2$ ，则任意一个点在此群中的点稳定子群在这个点的邻域上面的作用是2-弧传递的。因为这个条件对于2-弧传递群来说是充分的，所以从群论的观点来看，分类所有的有2-弧传递图是一个非常吸引人的问题。

著名的数学家Praeger把所有的2-弧传递图分为以下三类：

1) 拟本原型： $Aut\left(X\right)$ 的每一个非平凡的正规子群在点集上的作用是传递的；

2) 二部图型： $Aut\left(X\right)$ 的每一个非平凡的正规子群在点集上最多有两个轨道且至少有一个正规子群在点集上的作用有两个轨道；

3) 覆盖型： $Aut\left(X\right)$ 存在一个正规子群在点集上至少有三个轨道，则X是子类1)或者2)中某个图的正则覆盖。

在子类1)中， $Aut\left(X\right)$ 在 $V\left(X\right)$ 上的作用是拟本原的。在子类2)中，X必是一个二部图且在文献 [3] 中给出了关于这种情形的推导定理。近年来，子类3) (也即图的正则覆盖的问题)这种情形也就成为了图论领域国内外同行非常关注的问题。在文献 [4] 中，决定了完全图 $K_n$ 所有的2-弧传递的正则覆盖，其中覆盖变换群要么是 $Z_d$ 要么是 $Z_p^2$ (p是素数)。而文献 [5] 则研究了与文献 [4] 一样的问题，在这里覆盖变换群被推广为 $Z_p^3$ (p是素数)。进一步，在文献 [6] 中，覆盖变换群被推广为亚循环群。尽管循环群和秩为2的初等交换p-群都是亚循环群，但大多数亚循环群都是非交换的。在文献 [7] ， [8] 和 [9] 中则完全分类了 $K_{n,n}-n{K}_2$ 所有的2-弧传递的正则覆盖，其中覆盖变换群分别为循环群， $Z_p^2$ 和 $Z_p^3$ 。在文献 [10] 和 [11] 中，研究了 $K_{n,n}$ 的覆盖变换群为循环群和 $Z_p^2$ 的2-弧传递的正则覆盖，得到了其完整分类。注意到，在上述研究中覆盖变换群大多是交换群，目前关于覆盖变换群是非交换群的研究成果相对较少。

1.2. 主要结果

本文旨在研究 $K_{5,5}-5K_2$ 的正则覆盖的分类，其中覆盖变换群是 $S_4$ ，且保纤维自同构子群的作用是2-弧传递的。下面就是本文的主要结果，并将在本文的第三部分给予证明。

定理1设X是 $Y=K_{5,5}-5K_2$ 的连通正则覆盖，其中覆盖变换群K同构于 $S_4$ ，且保纤维自同构子群的作用是2-弧传递的，那么满足条件的覆盖图X是不存在的。

2. 基本概念

本文所涉及的图都是简单的，无向的以及连通的。对于群和图的相关术语，我们建议读者参考文献 [12] [13] [14] 。对于一个图X，它的每条边都可以对应于一对方向相反的弧。我们用 $V\left(X\right)$ 、 $E\left(X\right)$ 、 $A\left(X\right)$ 、 $Aut\left(X\right)$ 来表示图X的点集、边集、弧集以及全自同构群。用 $K_{n,n}-n{K}_2$ 表示完全图减去一个完美匹配，其点集 $V\left(K_{n,n}-n{K}_2\right)=\left\{1,2,\cdots ,n\right\}\cup \left\{1^{\prime },2^{\prime },\cdots ,n^{\prime }\right\}$ ，边集 $E\left(K_{n,n}-n{K}_2\right)=\left\{i{j}^{\prime }|i\ne j,1\le i,j^{\prime }\le n\right\}$ 。对于任意的 $v\in V\left(X\right)$ ，我们用 $N\left(v\right)$ 来表示点v在X中的邻域。图X的一个s-弧，其中 $s\ge 1$ ，指的是图X的 $s+1$ 个点构成的序列 $\left(v_0,v_1,\cdots ,v_s\right)$ ，使得对于所有的 $1\le i\le s$ ， $\left(v_{i-1},v_i\right)$ 是一条弧，且对于所有 $1\le i\le s$ ， $v_{i-1}\ne v_{i+1}$ 。图X称为是s-弧传递的，如果 $Aut\left(X\right)$ 在X的所有s-弧组成的集合上是传递的；称 $Aut\left(X\right)$ 的子群G在X上是s-弧传递的，如果G在X的所有s-弧组成的集合上是传递的。图X的一个2-弧，指的是图X的3个点构成的序列 $\left(v_0,v_1,v_3\right)$ ，使得对于 $\left(v_0,v_1\right)$ 、 $\left(v_1,v_2\right)$ 都是一条弧，且 $v_0\ne v_2$ 。图X称为是2-弧传递的，如果 $Aut\left(X\right)$ 在X的所有2-弧组成的集合上是传递的；称 $Aut\left(X\right)$ 的子群G在X上是2-弧传递的，如果G在X的所有2-弧组成的集合上是传递的。特别地，1-弧传递图又称作弧传递图或者对称图。

设X是一个图，将 $V\left(X\right)$ 分成大小相等的m个独立集 $\mathcal{P}$ 。商图 $Y:=X/\mathcal{P}$ 的点集是 $\mathcal{P}$ ，且图Y的两个点集 $P_1$ 和 $P_2$ 是相邻的，指的是在X中 $P_1$ 和 $P_2$ 之间至少有一条边。我们说X是Y的m-重覆盖，如果 $P_1{P}_2\in E\left(Y\right)$ 时，X的 $P_1$ 和 $P_2$ 之间的边集是匹配的。在这种情况下，Y称为X的基图，集合 $P_i$ 称为X的纤维。将纤维映射到纤维的X的自同构，称为是X的一个保纤维的自同构。X的固定每个纤维集合不变的所有自同构构成的群K称为X的覆盖变换群。容易得出，如果X是连通的，那么K在X的纤维上的作用必然是半正则的；也就是说，对于任意的 $v\in V\left(X\right)$ ，都有 $K_v=1$ 。特别地，如果K作用在每个纤维上都是正则的，我们就说X是Y的一个正则覆盖。

下面我们介绍一些符号：设G是一个群，H是G的一个子群，我们分别用 $G^{\prime }$ 、 $C_G\left(H\right)$ 、 $N_G\left(H\right)$ 表示G的导群、H在G中的中心化子以及H在G中的正规化子。设M和N是两个群，我们用 $\left[M,N\right]$ 表示M和N的换位子群，再分别用 $M\times N$ 和 $M⋊N$ 来表示M和N的直积和半直积。

下面是群论中的一个基本的结论。

引理2.1 [15] (Satz4.5)设H是G的一个子群，则 $C_G\left(H\right)$ 是 $N_G\left(H\right)$ 的一个正规子群，且商群 $N_G\left(H\right)/C_G\left(H\right)$ 同构于 $Aut\left(H\right)$ 的一个子群。

设G是一个有限群，H是G的一个真子群，设D是 $G-H$ 中H的某些双陪集的并集，且满足 $D=D^{-1}$ ，则可定义陪集图 $X=X\left(G;H,D\right)$ ，其点集为 $X\left(X\right)=\left\{Hg|g\in G\right\}$ ，而边集 $E\left(X\right)=\left\{H{g}_1,H{g}_2|g_2{g}_1{}^{-1}\in G\right\}$ 。根据定义，图X的顶点数就是H在G中右陪集的个数，它的度数是H在D中右陪集的个数。显然，G在 $V\left(X\right)$ 上的右乘作用是传递的，并且这个作用的核就是H在G中所有共轭的交。如果这个核是平凡的，那么我们称子群H是无核的。特别地，如果 $H=1$ ，我们得到一个Cayley图。反之，每一个点传递图都同构于一个陪集图，见文献 [16] 。

设G是一个有限群，L和R都是G的子群，且D是R和L在G中若干双陪集图的并，也即 $D={\cup }_{i}R{d}_{i}L$ 。我们用 $\left[G:L\right]$ 和 $\left[G:R\right]$ 来分别表示G关于L和R的陪集。定义一个二部图 $X=\left(G,L,R;D\right)$ ，它的点集为 $V\left(X\right)=\left[G:L\right]\cup \left[G:R\right]$ ，边集为 $E\left(X\right)=\left\{Lg,Rdg|g\in G,d\in D\right\}$ 。这个图就称为G的关于L，R和D的双陪集图，见文献 [17] 。

引理2.2 [17] (引理2.3，2.4)

(i) 双陪集图 $X=B\left(G,L,R;D\right)$ 是连通的当且仅当 $G=\langle D^{-1}D\rangle$ 。

(ii) 设Y是一个二部图，它的点集为 $V\left(Y\right)=U\left(Y\right)\cup W\left(Y\right)$ 。设G是 $Aut\left(Y\right)$ 的子群，它在两个部集U和W上的作用是传递的。设 $u\in U\left(Y\right)$ 和 $w\in W\left(Y\right)$ ，且设 $D=\left\{g\in G|w^g\in Y_1\left(u\right)\right\}$ ，则有D是 $G_w$ 和 $G_u$ 在G中的若干双陪集的并，且有 $Y\cong B\left(G,G_u,G_w;D\right)$ ，特别地，若 $uw\in E\left(Y\right)$ 且 $G_u$ 在u的邻域上的作用是传递的，则 $D=G_u,G_w$ 。

3. K_5,5 − 5K₂的正则覆盖

在这一节我们证明定理1，即基图 $Y=K_{5,5}-5K_2$ 。设 $p:X\to Y$ 是从X到Y的覆盖投影，其中覆盖变换群K同构于 $S_4$ ，且保纤维自同构群的作用是2-弧传递的。下面我们证明定理1。

定理1 设X是 $Y=K_{5,5}-5K_2$ 的连通正则覆盖，其中覆盖变换群K同构于 $S_4$ ，且保纤维自同构群的作用是2-弧传递的，那么满足条件的覆盖图X是不存在的。

证明 对于基图 $Y=K_{5,5}-5K_2$ ，显然 $Aut\left(Y\right)\cong S_5\times Z_2$ 。设 $A_5\cong G\le Aut\left(Y\right)$ 且 $\tilde{G}$ 为G的提升，即 $\tilde{G}/K=G$ 。根据引理2.1，可得

$\tilde{G}/C_{\tilde{G}}\left(K\right)\le Aut\left(K\right)\cong S_4$ .

故有，

$C_{\tilde{G}}\left(K\right)\ne 1$ . (1)

由于覆盖变换群K同构于 $S_4$ ，故有 $Z\left(K\right)=1$ 。进一步，可得

$C_{\tilde{G}}\left(K\right)\cap K=1$ . (2)

结合(1)式和(2)式，可得

$1\ne C_{\tilde{G}}\left(K\right)\cong C_{\tilde{G}}\left(K\right)/C_{\tilde{G}}\left(K\right)\cap K\cong C_{\tilde{G}}\left(K\right)K/K⊳\tilde{G}/K\cong A_5$ .

因为 $A_5$ 是单群，所以 $C_{\tilde{G}}\left(K\right)\cong A_5$ 。因此，

$\tilde{G}=C_{\tilde{G}}\left(K\right)\times K\cong A_5\times S_4$ .

设 $V\left(Y\right)=\left\{1,2,3,4,5\right\}\cup \left\{1^{\prime },2^{\prime },3^{\prime },4^{\prime },5^{\prime }\right\}$ ， $E\left(Y\right)=\left\{i{j}^{\prime }|i\ne j,1\le i,j^{\prime }\le 5\right\}$ 。现在我们有 $C_{\tilde{G}}\left(K\right)\cong A_5$ ，可把 $C_{\tilde{G}}\left(K\right)$ 等同于 $A_5$ 。在 $C_{\tilde{G}}\left(K\right)$ 中，设

$x=\left(23\right)\left(45\right)$ , $y=\left(25\right)\left(34\right)$ , $z=\left(234\right)$ , $b=\left(15\right)\left(23\right)$ ,

则有 ${\tilde{G}}_F=\left(\langle x,y\rangle :z\right)\times K$ ，其中 $F=p^{-1}\left(1\right)$ 是点1的纤维。取 $\tilde{u}\in F$ ，则可设 $L:={\tilde{G}}_{\tilde{u}}=\langle x{k}_1,y{k}_2\rangle ⋊\langle z{k}_3\rangle$ ，其中 $k_1,k_2,k_3,\in K$ 。由于 $L\cong A_4$ 且 $\left[C_{\tilde{G}}\left(K\right),K\right]=1$ ，可得 $\langle k_1,k_2\rangle ⋊\langle k_3\rangle \le A_4$ 。显然， ${\tilde{G}}_F={\tilde{G}}_{F^{\prime }}$ ，其中 $F^{\prime }=p^{-1}\left(1^{\prime }\right)$ 是点 $1^{\prime }$ 的纤维。故，可以假设， $R:={\tilde{G}}_{\tilde{w}}=\langle x{k^{\prime }}_1,y{k^{\prime }}_2\rangle ⋊\langle z{k^{\prime }}_3\rangle$ ，其中 ${k^{\prime }}_1,{k^{\prime }}_2,{k^{\prime }}_3,\in K^{\prime }$ ，且 $\tilde{w}\in F^{\prime }$ 。

根据引理2.2，我们知道覆盖图X一定同构于某一个双陪集图 $X^{\prime }=B\left(\tilde{G},L,R;D\right)$ ，其中 $D=RbkL$ 且 $k\in K$ ，并且双陪集图D的两个部集分别为：

${\tilde{U}}^{\prime }=\left\{Lk|k\in K\right\}\cup \left\{Lb{x}^i{y}^{j}k|i,j=0,1;k\in K\right\}$

${\tilde{W}}^{\prime }=\left\{Rk|k\in K\right\}\cup \left\{Rb{x}^i{y}^{j}k|i,j=0,1;k\in K\right\}$ .

而且， $X^{\prime }$ 要满足下列两个条件：

1) $d\left(X^{\prime }\right)=4$ ：

因为L包含点Rbk的次轨道长为4，故我们有 $z{k}_3$ 必固定点Rbk，即 $Rbkz{k}_3=Rbk$ ，则有

$bkz{k}_3{k}^{-1}{b}^{-1}=k{z}^b{k}_3{k}^{-1}=z^{-1}k{k}_3{k}^{-1}={\left(z{k^{\prime }}_3\right)}^{-1}{k^{\prime }}_{3}k{k}_3{k}^{-1}\in R$ .

因此， ${k^{\prime }}_{3}k{k}_3{k}^{-1}=1$ ，即

${\left({k^{\prime }}_3\right)}^k=k_3^{-1}$ . (3)

2) 连通性：

由(3)式，我们有

$\begin{array}{c}\langle D^{-1}D\rangle =\langle x{k}_1,y{k}_2,z{k}_3,R^{bk}\rangle =\langle x{k}_1,y{k}_2,z{k}_3,{\left(x{k^{\prime }}_1\right)}^{bk},{\left(y{k^{\prime }}_2\right)}^{bk},{\left(z{k^{\prime }}_3\right)}^{bk}\rangle \\ =\langle x{k}_1,y{k}_2,z{k}_3,x^b{k^{\prime }}_1{}^k,y^b{k^{\prime }}_2{}^k,z^{-1}{k^{\prime }}_3{}^{-1}\rangle \\ \le C_{\tilde{G}}\left(K\right)\times \langle k_1,k_2,k_3\rangle \le A_5\times A_4<\tilde{G}.\end{array}$

根据引理2.2(i)可知，双陪集图 $X^{\prime }$ 不连通，所以连通的覆盖图X是不存在的。□

4. 结语

在众多学者的努力下，建立了一套刻画对称图的正则覆盖的电压理论，用来确定小阶数对称图的循环和初等交换正则覆盖，利用这个理论众多小阶数对称图的边传递或弧传递和初等交换正则覆盖被完全分类，两类对称图类完全二部图和完全二部图减去一个完美匹配的具有高对称性(2-弧传递)的循环和部分初等交换正则覆盖被确定。本文分类了 $K_{5,5}-5K_2$ 的正则覆盖，其中覆盖变换群是 $S_4$ ，且保纤维自同构子群的作用是2-弧传递的，最后证明满足条件的连通覆盖图是不存在的。根据本文的证明思路，为覆盖变换群是其他对称群时的正则覆盖提供了理论参考。 $K_{5,5}-5K_2$ 是较为典型的高对称性图， $S_4$ 属于“小阶数”非交换群，对于 $K_{n,n}-n{K}_2$ ，当n取更大的数值时，覆盖变换群是非交换群的分类还有待完成。且迄今得到的正则覆盖结果基本都具有以下特征：

1) 主要是刻画“小阶数”对称图的“交换”(主要是循环和初等交换)正则覆盖。

2) 图的无穷类的正则覆盖结果还很少，且基本上都是在具有高对称性(2-弧传递)的假设下完成的。

因此，刻画小阶数对称图的“非交换”正则覆盖和图的无穷类的具有较弱对称性的正则覆盖就成为了很有意义的研究课题，也是未来将要努力的方向。

致谢

感谢参考文献中的知识对于本文提供的理论支持和我的导师在本论文中给予的写作帮助，也非常感谢评审老师提出的宝贵修改意见。