（基础数学专业论文）具有单群作用的1因子块图的对称性研究.pdf

具有单群作用的1 因子块图的 对称性研究 摘要 在群与图的研究中，图的对称性一直是一个热门问题，它主要通过图 的自同构群具有某些传递性来描述，这类图的典型代表有c a y l e y 图和 s a b i d u s s i 陪集图 关于c a y l e y 图，一个比较有意思的情况是，当群g 的连通3 度非弧 传递c a y l e y 图不是g 的g r r 时，其自同构群的作用非本原，于是可得到 原图的两个块图，即1 因子块图和基本圈块图经研究发现，这两个块图 有许多有意思的对称性，比如1 正则性，高弧传递性等事实上，这两个 块图都是群g 的s a b i d u s s i 陪集图此外，具体研究某些群的小度数c a y l e y 图的对称性在群与图研究中仍然占有比较重要的地位 本文主要围绕上述问题进行研究，即我们得到具有有限非交换单群传 递作用的1 因子块图的一些基本的性质，同时我们也给出了某些群的小度 数c a y l e y 图的分类及其基本性质具体地，本文的主要结果有： 1 研究具有有限非交换单群传递作用的1 因子块图的结构，特别是 1 - 正则性以及非c a y i e y 图性； 2 利用有限非交换单群构造了4 度1 传递图的无限族的例子； 3 交错群a 6 的3 、4 度弧传递c a y l e y 图的完全的分类及其对称性的 描述； 4 构造了一些交错群4 6 的3 、4 度g r r 的例； 5 确定了对称群s 的3 度弧传递图及其性质 本文主要采用群论方法文中有关群论及代数图论的概念可参考文 献【1 ，2 ，3 1 关键词：单群点传递图块图1 正则s 弧传递图, - v g l j 表示 t h ei n v e s t i g a t l 0 nf o r0 n e f a c t o rb l o c kg r a p hw i t ht h e a c t l 0 n0 fs i m p l eg r o u p a b s t r a c t t h es y m m e t r yo fg r a p h sh a sb e e nb e i n gav e r yh o ti s s u ep r 曲l e mi ns t u d y i n g g r o u p sa n dg r a p h sa n di tm a i n l yd e p e n d so ns o m et r a n s i t i v ep r o p e r t i e so fa c t i n g b yt h ea u t o m e r p h i a mg r o u p so ft h eg r a p h st od e s c r i b e t h ec a y l e yg r a p ha n dt h e s a b i d u s s ic o s e tg r a p ha r et w oc l a s s i c a lr e p r e s e n t a t i v e sf o rt h e s eg r a p h s f o rc a y l e yg r a p h , av e r yi n t e r e s t i n gs i t u a t i o ni st h a ti t sa u t o m o r p h i s m g r o u pi si m p r i m i t i v ea si ta c t so nv ( x ) w h e nt h en o n s y m m e t r i cc u b i cg r a p h so f g o u pgi sn o tg i 况s ow ec a ng e tt w od i f f e r e n tk i n d so fb l o c kg r a p ho ft h eg r a p h ： 1 一f a c t o rb l o c kg r a p ha n da n o t h e rb a s i cc y c l eb l o c kg r a p h w ew i l lf i n ds o m e i n t e r e s t i n gs y m m e t r yp r o p e r t i e sf o rt h et w ok i n d so fb l o c kg r a p hb ys t u d y i n g f o re x a m p l e ，t h eo n e r e g u l a rp r o p e r t ya n dh i g ha r c t r a n s i t i v ep r o p e r t y ，a n d s oo n i nf a c t ，t h et w od i f f e r e n tk i n d so fb l o c kg r a p hr r ea l ls a b i d u s s ic o s e t g r a p h so fg r o u pg f u r t h e r m o r e ，t h em a t e r i a ls y m m e t r ys t u d y i n go fc a y l e yg r a p h s o fs m a l lv a l e n c i e sf o rs o m eg r o u p st a k e sav e r yi m p o r t a n tp l a c ei ns t u d y i n g g r o u p sa n dg r a p h s t h o s eq u e s t i o n sa r et h em a i np u r p o s eo fm yt h e s i s ，w eg e ts o m ee l e m e n t a r y p r o p e r t i e so fo n e f a c t o rb l o c kg r a p ha n dw ea l s og i v eac o m p l e t ec l a s s i f i c a t i o n a n ds o m ee l e m e n t a r yp r o p e r t i e so ft h ec a y l e yg r a p h so fs m a l lv a l e n c i e so fs o m e g r o u p s w eh a v et h ef o l l o w i n gt h e o r e m sa st h em a i nr e s u l t so ft h i st h e s i s 1 w es t u d yt h ec o n s t r u c t i o no f1 一f a c t o rb l o c kg r a p hw i t ht h ea c t i o no f s i m p l eg r o u pg ，e s p e c i a l l yt h e1 一r e g u l a ra n dn o n c a y l e yg r a p hp r o p e r i t i e s ： 2 w ec o n s t r u c tt h ei n f i n i t ef a m i l i e so f1 一t r a n s i t i v ew i t hv a l e n c i e s3 b yf i n i t en o n a b e l i a ns i m p l eg r o u p s ： 3 w eg i v eac o m p l e t ec l a s s i f i c a t i o no fa l la r c _ t r a n s i t i v ec a y l e yg r a p h s o n4o fv a l e n c i e s3a n d4a n dt h ed e s c r i p t i o no fs o m es y m m e t r i cp r o p e r t i e s ； 4 - w eg i v es o m ee x a m p l e so fg r ro f 4 ： 5 w ec o n f i r mt h e 缸c - t r a n s i t i v ec a y l e yg r a p h so ns t o fv a l e n c i e s3a n dt h e d e s c r i p t i o no ft h e i rp r o p e r t i e s t h em e t h o du s e di nt h i st h e s i si sm a i n l yg r o u p - t h e o r e t i c f o rc o n c e p t s o fg r o u pt h e o r ya n da l g e b r a i cg r a p ht h e o r yw er e f e rr e a d e r st o 1 ，2 ，3 k e yw o r d s ：s i m p l eg r o u pv e r t e x t r a n s i t i v e g r a p h b l o c kg r a p h 1 r e g u l a r s a l ct r a n s i t i v eg r 广西大学学位论文原创性声明和使用授权说明 原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相 关知识产权属广西大学所有，本人保证不以其它单位为第一署名单位发表或使用本论文 的研究内容。除已注明部分外，论文中不包含其他人已经发表过的研究成果，也不包含 本人为获得其它学位而使用过的内容。对本文的研究工作提供过重要帮助的个人和集 体，均已在论文中明确说明并致谢。 论文作者签名： 渤枣 z 哆“臌日 学位论文使用授权说明 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本： 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 函口时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：乃涉奔之导 砂眸石月日 广- d - ，t t 学硕士学位论丈 具有单肆作用的1 一日子块田的对称隹研究 第一章基本概念及基本结果 1 1 基本概念 本文讨论的图都指有限简单无向图，主要采用群论方法，有关的定义和符号可参 阅文献【1 ，2 ，3 】 定义1 1 1 【1 】1 一个有限简单无向图r 是指一个顶点数有限且无环无重边的无向 图，即顶点集v ( r ) 有限，边集e ( r ) c _ v t 2 ：= u ，口) l u ，v e v , u 口) 通常记作r = ( k e ) 如果一个图r 各顶点的度数都相等。则称为正则图 口 定义1 1 2 【3 】设r = ( k e ) 和r ，- ( ，) 是两个图，口是y 到上的一一映射， 满足对于所有的t ，v e k ( ，v ) e e = = ( 矿，矿) ， 则称口为图r 到图r 7 上的同构映射，并称图r 与图f 7 同构，记作r 皇r ， 我们较常讨论的是顶点集相同的两个图的同构问题，即y ，_ k 这时有 口 命题1 1 3 3 】图f = ( k e ) 与图r ，_ ( v ) 同构当且便当； 存在矩s y m ( v ) ，使得( “，v ) e e = 亭( 矿，矿) f 口 定义1 1 4 3 1 图r 到自身上的同构映射称为图r 的自同构 口 定义1 1 5 【1 图r 的全体自同构的集合在置换乘法之下构成一个群，称为图r 的 全自同构群，记作a u t ( r ) a u t ( r ) 的子群统称为r 的自同构群 口 定义1 1 6 【4 】一个图r 如果a u t ( r ) 作用在其顶点集v ( r ) 上传递，则称为点传 递圉如果a u t ( r ) 在r 的弧集上的作用是传递的，则称为孤侍递图弧传递图也称 1 - 弧传递图或者对称图，如果此时i a u t ( r ) l = i a r c ( r ) l ，则称之为1 - 正则图 口 定义1 1 7 5 设8 是一个正整数，取白r 中s + 1 个顶点的序列，v l ，) 如果对所有t ，满足( 地一1 ，v , ) e e ( r ) 及仇一1 v i + l ，则称为r 的一条s 一弧 口 1 广西夫粤硬士学位论戈 具有簟肆作用的1 因子块圉的对称隹研究 定义1 1 8 【3 1 图r 的一个自同构群h 如果作用在其s 弧集上传递，则称为( h ，s ) 一 弧传递图特别地，( e1 ) 弧传递图简称日一弧传递图如果只是( 日，8 ) 一弧传递而非 ( 日 8 + 1 ) 一弧传递，则称为( 日，s ) 一传递图 口 定义1 1 9 【1 】设。y ( r ) ，则与口邻接的顶点集合称为口的邻域，记作r l ( 口 定义1 1 1 0f 1 图r 的一个自同构群日中作用 不变的元素集合构成日的个 子群，通常称为日关于点口的点稳定子，记作风 口 龠韪1 1 1 1 【6 】图r 是j 孤传递图当且仅当h 作用在f 的顶点集y ( r ) 上是传递 的，并且任意一点v e v ( r ) 在h 中的穆定予群风在的邻城r l ( 口) 上也是待递的。 d 特别地，还有 命题1 1 1 2f 6 】谩a ：= a u t ( r ) 是工的全自同构群，图j 1 是弧传递图当且便当a 在r 的顶点集v ( r ) 上是传递的，并且任意一点t ，e v ( r ) 在a 中的稳定子群a ，在口 的邻域f a ( v ) 上也是传递的 口 定义1 1 1 3 闭设g 是一个群，记g 带：= g 1 任取g 社的一个子集s 则g 的 一个关于s 的c a y l e y 图r ：= c a y ( g ，s ) 定义为 y ( r ) = g ，e ( r ) = ( g ，s 9 ) ig e g ，s e s 显然，c a y l e y 图r = c a y ( g ，s ) 是点传递图，并且，r 是无向图当且仅当s = s - 1 ：= s 。f s e s ( 这样的s 称为逆封闭) ，r 为( 强) 连通当且仅当( s ) = g 口 关于c a y l e y 图r ：= c a y ( g ，s ) 的全自同构群a ：= a u t ( r ) 显然有a 冗( g ) ，这 里r ( g ) 是g 的右正则表示，因此c a y l e y 图都是点传递的设 a u t ( g ，= 扣a u t ( g ) j 铲= 母 显然a r ( g ) a u t ( g ，s ) 定义1 1 1 4m 设g 是一个有限群，t 是其真子群，d 是若千个形如t d t ( d 隹即 的双陪集的并定义g 关于丁和d 的s a b i d t m s i 陪集图r ：= s a b ( g ，z d ) 如下， y ( r ) = 【g ：刁，( t 在g 中的全体右陪集的集合) ， e ( r ) = ( 乃，t d g ) ig e g ，d e d 2 广首尢拳硕士学位论丈鼻有单群作用的1 一园子堍田的对称性研究 口 当d 是单个双陪集d = t d r 时，简记f = s a b ( g ，zd ) 注：因为不考虑重边，所以当t d g = t d g 时认为边 t g ，t d g 与边 t g ，t d g 相 同 由此定义可以看出c a y l e y 图是s a b i d u s s i 陪集图的特殊情形( 对应于日= 1 ) 命题1 1 1 5 【7 1 每个点传递图r 一定同构于其全自同构群a ：= a u t ( r ) 的一个 s a b i d u s s i 陪集图 口 事实上，设r = ( k 目是点传递图，取g = a u t ( d ，t ：= ( 0 为g 在顶点v e v 上 的点稳定子以及d ：= g e gi 如，v g ) e 则易知d 是若干个形如t g t ( g 隹t ) 的双 陪集的并，且满足d n 日= ，并且这时有f 竺s a b ( g ，正d ) 定义1 1 1 6 8 】设g 是一个有限群，t 是其子群，取q 为r 的所有右陪集的集 合，作用p ( g ) 取右乘变换，则称p ( g ) 为g 在子群t 上的置换表示该表示的核 k e r p ( g ) = t g ，为子群t 在g 中的核 口 因此有 命题1 1 1 7 【9 】a t a 兰p ( g ) ，其中t c = n 口g 2 v 是右乘置换表示p 的核 考虑群g 关于子群t 的陪集图s a b ( g ，正d ) 则还有 口 命题1 - 1 1 8 2 1g 同构于a u t ( s a b ( g ，e d ) ) 的子群p ( g ) 等价于= 1 口 定义1 1 1 9 【1 0 1 右乘置换表示p 的核t c = l ，则称t 是g 的无核子群 口 定义1 1 2 0 3 6 1a ：= a u t ( r ) 是s a b i d u s s i 陪集图f ：= s a b ( g ，zd ) 的全自同构 群若p ( g ) 璺a ，则称s a b i d u s s i 陪集图r ：= s a b ( g ，z d ) 关于g 是正规的如果 p ( g ) = a ，则称r 是g 的一个图正则表示，简称g r ， 口 注；为使g 作为a u t ( s a b ( g ，正d ) ) 的子群，今后r 要求取自g 的无核子群，并简 记p ( c ) 为g 3 广西大拳累士学位论文具有簟群作用的l 一日子块圈的对称隹研充 1 2 基本结果 为方便读者，在这一节，我们列出了部分与本文有关或在以后章节都要引用的已 知定理，它们均以引理的形式给出，只对某一章需要的结果。不在这里给出 引理1 2 1 【7 】设r = s a b ( g ，z d ) 是g 关于t 和d 的s a b i d u s s i 陪皋图，则 ( 1 ) r 是良定义的度数为ld ：? i 的无向图 ( 2 ) a u t ( r ) 包含g ( e z 乘变换) ，于是r 是点传递图又。顶点t g 在g 中的稳 定子群是g - i 勋 ( 3 ) r 是连通的当且仅当g = ( d ) ( 4 ) r 是g - 弧传递的当且仅当d = t g | t 是一个单个的双陪集 口 引理1 2 2 3 】谩r 是连通3 度( 甄s ) 一传递图，因而1 s 5 取v e v ( r ) ，并记 月。为日的点稳定子，则； ( 1 ) 当s = l 时，日；竺z o ； ( 2 ) 当s = 2 时，嚣。兰s s ； ( 3 ) 当s = 3 时，日；兰d r 2 ； ( 4 ) 当s = 4 时，日j 型s 4 ； ( 5 ) 当s = 5 时，凰垒s 4 z 2 口 引理1 2 3 3 】设r 是连通3 度弧传递图，a ：= a u t ( r ) 是图r 1 的全自同构群则 对任一璜点 y ( r ) ，u 在a 中的点稳定子群a 。的阶整除4 8 = 2 4 3 口 4 广百大学硕士学位论丈具有单群作用的1 一日子块田的对称性研究 第二章具有单群作用的l - 因子块图的对称性研究 2 1 引言 我们知道，连通3 度点传递图可分为两大类；一类是对称图，即弧传递图；另一 类是非对称图目前关于连通3 度点传递图的研究绝大多数是针对前一类的，并已获 得丰富且深刻的结果其中最有代表性的结果是给出了连通3 度p 弧传递图中s 的上 界，即设r 为s 弧传递图( s 一传递图) ，则，任意点的点稳定子的阶一定整除3 2 ”1 ，其 中8 为不超过5 的正整数这个著名的结果是1 9 4 7 年t u t t e 在文献【1 1 】中提出的 后来被s i m s 1 2 ( 1 9 6 7 ) 和d j o k o v i c 1 3 ( 1 9 7 2 ) 进一步推广了d i o k o v i c 和m i l l e r 在文 献 1 4 】还描述了七个3 度对称图的图自同构群 然而针对第二类情况，即连通3 度非对称图的研究相对较少一个极端的情形是 其图自同构群的点稳定子为1 ，即所谓的图正则表示( g r r ) 问题，这时图的全自同 构群恰好同构于g 本身关于有限群是否存在g r r 的问题在1 9 7 0 年已经完全解决， 但如果限制图的度效。比如构造一个给定的群的3 度或4 度g r r ，这类问题还远没有 解决 在具有高度对称性的图中，1 一正则图一直是主要的研究对象之一，并且大都围绕 着小度数的情形进行白1 9 5 2 年f r u c h t 1 5 1 给出第一个3 度1 正则图的例子后，文 献 2 ，1 6 ，1 7 ，1 8 ，1 9 ，2 0 】和f 2 1 也陆续给出3 度1 一正则图的例子 关于4 度1 一正则图，赵中云【2 2 】给出阶为素数p 的4 度1 一正则循环图，其中 pil ( m o d 4 ) ，j u - m o ko h 等2 3 ，2 4 1 构造了二面体群上偶数度的1 一正则无限族然而 对于非可解群上的4 度1 一正则图还不多见，在目前已有结果中，m a r u i i 5 2 5 1 发现了 交错群a 。( n 为奇数) 的4 度1 正则c a y l e y 图以及曲海鹏( 见文献 2 6 ) 构造的几个 单群上的4 度l 一正则c a y l e y 图的无限族总体来看，4 度1 一正则图的例子，特别是 对于非c a y l e y 图的4 度1 一正则的例子还是比较稀少的，即使是4 度1 传递的例子也 不多见 当连通3 度非对称c a y l e y 图的全自同构群的点稳定子不是1 时，情况相当复杂， 事实上它是无界的，见文献 2 7 】，这时图自同构群的作用是非本原的，并得到两个块 图，即1 一因子块图和基本圈块图本文主要研究了l 一因子块图的一些基本的性质 5 广西大学囊士掌位论丈具有单群作用的l 一日子块田的对称性研究 2 2 预备知识 定义2 2 1 设r 是一个简单固，a ：= a u t ( f ) 非本原，并谩f = b o ，b 1 ，玩一1 ) 是a 的非本原块系针对这个非本原块系，我们可定义r 的一个块图t v ( - ) _ _ ， e 厅) = b ，岛) ijv i e b | ，马，慨，v j ) e e ( r ) 口 图r 中。任意两条都不相邻的边组成的集合叫做圉r 的匹配图r 的一个匹配 如果包含了图r 的每一个顶点，则称之为图r 中的1 - 因子 设a 关于y ( r ) 中某个点u 的点稳定子群a u # 1 由于i r l ( “) i = 3 及正1 ( 岫不传 递，所以a 。必稳定f i ( u ) 中一个点口( 今后称口为f i ( u ) 的不动点) ，互换f l ( u ) 中 的另外两个点这就是说，对任意t y ( r ) ，存在v e r l ( u ) ，使得a 。= a 。我们定义 f = ，v e e ( r ) l 也= 也 我们可以证明，f 不仅是图r 的l - 因子，而且还是4 作用于r 上的一个块系 我们把有块系f 做成的块图称为图r 的1 一因子块图，记做f 显然，r - f 为若干个不相交豳的并因为a 作用于r 为点传递的，所以我们可 以知道，这些圈组成r 的一个完全块系，我们把这些圈称为图r 的基本圈，由这些基 本圈组成的r 的块系称之为图r 的基本圈块系，由这个基本圈块系做成的块图称为 图r 的基本圈块图 设r = s a b ( g ，正d ) 是陪集图，陪集功是其中一个顶点，如果不计较代表元的选 取，乃在a ：= a u t ( f ) 中的点稳定子简记作如于是有； 引理2 2 2 【2 】( 1 ) i v ( r ) i = i a ：如i = l a ：t i ； ( 2 ) a = g a g 及g n a 9 = t g 特别g n a i = t ( 3 ) l a ：a l = l a l ：t i 证明t ( 1 ) 显然 ( 2 ) 由g 的右乘置换表示在v ( r ) 上传递，i z p 得, a = g 如此外， g e g n a g 号功矿= 功铮9 9 ，9 1 e t v = g p ， 即g n a g = t g ( 3 ) 由( 2 ) ，i a ：a i = i g a s ：a l = l a l ：a n a l l = l a , ：t j 对于一个一般的连通3 度点传递图r ，由于每个顶点都有3 条弧以其为始点，而 每条边又包含两条方向相反的弧，所以3 1 v ( r ) t = l a r c ( r ) l = 2 1 e ( r ) 1 6 广酉太掌硕士拳位论文鼻有单肆作用的l 一因子块雷的对称性研究 考虑图r 的自同构群a 在弧集a r c ( r ) 上的作用，设轨道为l ，a 2 ，其 中r 为轨道数 由于r 是点传递的，如果取定 y ( r ) ，则每个弧的轨道i 至少包含一条起点是 口的弧，即( ， ) “得 e r l ( v ) ，这导致r l r l ( ) i _ 3 如果r = l ，那么r 为弧传递，所以l a l l4 8 【3 】； 如果r = 3 ，那么a i _ 1 我们只研究r 一2 的情况，并首先有如下重要结论t 引理2 2 3 【2 1 7 】谩r 是一个连通3 度非对称点传递图，a = a u t ( r ) ， y ( r ) ，则a ， 是一个2 一群 口 由于a 。在r l ( v ) 上有两个轨道， ( 口，v 1 ) ，( 口，v 2 ) e a 2 因为r 是点传递的， 不妨记为 伽) 和 q ，地) ，并设( 口，v o ) e a l ， 容易得i 2 i = 2 i lj 引理2 2 4 【2 8 】对轨道1 或2 ，如果包含( 口，) ，那么就一定包含( 7 ，口) 口 这就是说轨道l 或2 正好包含一条边我们也用1 ，2 来表示a 作用在边 集e ( r ) 上的轨道 定义2 2 5 2 8 】v ( r ) 中的序列( v o ，仇，一，钆) 称之为1 1 中的一条l - 路，如果 地一1 ，仇 e ( r ) 且口t i v i + i ，i 任意如果对i i - j l 1 9 时存在3 度g r r 徐明曜和徐尚进在文献【3 3 中提出了以下猜想和问题- 猜想3 1 4 每个有限群都存在3 、4 度的g r r 口 问题3 1 5 决定非交换单群的所有3 ，4 度争弧传递图 口 文献f 3 4 ) 的作者等人也对这些问题作了许多研究，但是由于交错群a 6 的群自周 构群的特殊性，所以关于的这方面的问题还没有很好的解决 本文围绕着交错群a 6 的3 ，4 度的弧传递c a y l e y 图的完整分类和3 4 度 g r r 做了一些研究 本文主要采用群论的方法，文中某些未定义而引用的群论及代数图论的概念请读 者参考文献1 1 ，3 1 3 1 2 预备知识 第一个引理是关于a 6 的小度数c a y l e y 的正规性和g r r 的存在性的 引理3 1 6 2 ，2 1 ，2 6 】交镨群a 6 的3 、4 度连通无向c a y l e y 图必为正规的若图 为g r r 当且便当a u t ( g ，s ) = 1 口 关于非交换单群的小度致c a y l e y 的c i - 子集的问题，我们给出了第二个引理 引理3 1 7 谩g 是有限非交换单群，且r = c a y ( g ，研寿g 的连通无向c a y l e y 图， 且i s l = 3 或4 ，则s 为g 的c i 一子集 证明： 由引理3 1 6 知f 正规，即g g 4 ：= a u t ( r ) ，这时对任意a e s y m ( g