（基础数学专业论文）一类图构形和二维非中心构形的φ3不变量.pdf

摘要 一类图构形和二维非中心构形的缟不变量 摘要 1 9 8 9 年m f a l k 定义了超平面构形的一个重要拓扑不变量织，它 是超平面构形余集的基本群的下中心序第三项模去第四项所得到的 a b e l 群的秩。2 0 0 1 年m f a l k 就这不变量提出了一个未决的问题： 给出织一个组合学解释。并指出这个问题“对图拟阵也是未决的”。 本文针对绣进行了研究，并证明不含子图k 。的简单图构形的绝 是图中长度为3 的极小圈个数的2 倍。这就部分地回答了f a l k 的问题。 同时对于射影平面上的直线构形也计算了织。 本文首先对文献中的算法进行了总结与推广，给出了简单图构形 的绣的算法，进而证明了缟= 2 群，为长度为3 的极小圈，群为 长度为3 的极小圈的个数。 织是依赖于基本群的。由z a r i s k i 的一个定理，高维空间中超平 面构形的余集的基本群计算可以化为平面上直线构形的余集的基本群 计算。因此，我们研究了射影平面上非中心构形的织不变量。证明了 射影平面上非中心构形的织不变量等于撑的两倍。 关键词：超平面构形；绣不变量；图构形；直线构形 摘要 f a l k s 呜i n v a r i a n tf o r ac l a s so fg r a p h i c a r r a n g e m e n t sa n dl i n ea r r a n g e m e n t s a b s t r a c t i n19 8 9 ，m f a l kd e f i n e da ni n v a r i a n t 0 3 f o r h y p e r p l a n e a r r a n g e m e n t s ，w h i c hi s t h er a n ko ft h ea b e l i a ng r o u p ( g 3 g 4 ) ，w h e r e g 3 ，g 4a r et h el o w e rc e n t r a ls e q u e n c eo ff u n d a m e n t a lg r o u pg = g lo f t h ec o m p l e m e n to ft h e h y p e r p l a n ea r r a n g e m e n t i n2 0 01 ，m f a l k p r o p o s e dt h ef o l l o w i n go p e np r o b l e m g i v eac o m b i n a t o r i a li n t e r p r e t a t i o no f a n dh ep o i n t so u tt h a tt h ep r o b l e mr e m a i n so p e n ，e v e nf o rg r a p h i c m a t r o i d s i nt h i st h e s i s ，w es t u d yf a l k s 绣i n v a r i a n tf o rg r a p h i ca r r a n g e m e n t s a n dl i n ea r r a n g e m e n t si np r o j e c t i v ep l a n ea n do b t a i n e dt h ef o l l o w i n gr e s u l t i fas i m p l e g r a p h d o e sn o tc o n t a i nt h e c o m p l e t eg r a p hk 4a s a s u b g r a p h ，绣e q u a l st ot w ot i m e so ft h en u m b e ro fc i r c u i t sw i t h3e d g e s t h a ta n s w e r st h eq u e s t i o no f f a l kp a r t i a l l y a n das i m i l a rs t a t e m e n ti st r u e f o rl i n ea r r a n g e m e n t si np r o j e c t i v ep l a n e b yo p t i m i z i n gt h ea l g o r i t h mi nt h er e f e r e n c e s ，w ef o r m u l a t ea n a l g o r i t h mf o rc o m p u t i n g4 3i n v a r i a n t ，a n dp r o v e dt h ef o r m u l a 缟= 2 群 f o rs i m p l eg r a p h i ca r r a n g e m e n t s b yat h e r o md u et oz a r i s k i ，t h ec o m p u t i n go ft h ef u n d a m e n t a lg r o u p i i i 北京化t 人学硕i j 学位论义 o ft h ec o m p l e m e n to fv a r i e t i e si nh i g h e rd i m e n s i o n a ls p a c ec a nb er e d u c e d t oc o m p u t i n gt h a to ft h ec o m p l e m e n to fp l a n ec u v e s f o rt h i sr e a s o nw e s t u d y 织i n v a r i a n tf o rl i n ea r r a n g e m e n t si np r o j e c t i v ep l a n e w eo b t a i n t h ef o l l o w i n gr e s u l t t h ei n v a r i a n t 绣o fl i n ea r r a n g e m e n t si np r o j e c t i v e p l a n ei se q u a lt ot w i c eo f = f e k e yw o r d s ：h y p e r p l a n ea r r a n g e m e n t ；i n v a r i a n t 织；g r a p h i ca r r a n g e m e n t ； l i n ea r r a n g e m e n t s 符0 说l 射 瓦 瓞 y h 彳= h l ，以) m d i m ( 4 ) 三( 彳) r a n k ( a ) g = ( v ，e ) 1 ， s = ( ，l ，) e s ( 彳) 乞= c ( 彳) j | j 乞 e = e 1 ，( 彳) o s ( a ) 墨 缎 ，、 e k 缟 符号说明 数域 实数域 向量窄间 超平面 超平面构形 彳中超、l i 面的个数 彳的维数 彳中超平面的非空交集的集合 彳的秩 图g 图g 的顶点集 图g 的边集 p 元组 e 。a a q 极小圈的全体 长度为n 的极小圈伞体 乞中元素的个数 e 1 的外代数 彳的o s 理想 彳的o s 代数 4 个顶点的完全图 彳的第k 个w h i t n e y 数 删除元素只 缟不变量 i x 北京化工大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文巾已经注明引用的内容外，本论 文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本卢明的法律结果由本人承担。 作者签名：盔盏 日期：丝乡：夕? 关于论文使用授权的说明 学位论文作者完全了解北京化工大学有关保留和使用学位论文 的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北 京化工大学。学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编 学位论文。 保密论文注释：本学位论文属于保密范围，在土年解密后适用本 授权书。非保密论文注释：本学位论文不属于保密范围，适用本授权 书。 作者签名 导师签名 日期：p 、砂 第一章绪论 1 1 背景知识介绍 第一章绪论 超平面构形足数学上一个较新的领域，在物理、代数、拓扑、组合等领域都 有广泛的应用。超i f 面就足数域瓦上的n 维向量空间中的任何一个n 一1 维仿射子 空间。超平面构形彳是指n 维向量空间中有限个超平面的集合，记为 彳= h i ，日。 。 f a l k 3 5 给出了织的定义，并且讨论了织的拓扑学意义。张曦1 6 1 等给出了超甲 面构形绣不变量的一个算法，并且证明了对顶点数大于3 的轮式图有绣等于撑的 两倍，其中z 为长度为3 的极小圈。本文得出了不含子图k 的简单图构形以及二 维非中心构形的仡刁i 变量的表达式。下面给出超平面构形以及与其相关的一些基 本知识，作为研究的知识基础。 1 2 预备知识 定义1 2 1 【1 】设v 为数域赶上向量空间，取定y 的一个基p 。，e 。， v = x i p l + + x l e ，yf - ( x i ，而) ，则h = ( ，) 瓦”f o i x i + + = 6 ) 叫做 一个超平面。当式中的b 0 时，日叫做仿射超平面，简称超平面。b = 0 时， h = x ej l c ”| 口l x l + + = o ) 是赶一的刀一1 维子空间。口= 口l ，一，) 为超平面 日的法向量。 定义1 2 2 t 1 】瓦一中超平面的有限集叫做超平面构彤，简称构形。”个超平面构成 的超平面构形记为彳= h i ，h ) ，- t e l 】_ l ，刀) 。 定义1 2 3 t 1 1 如果n 。一日矽，则称这个构形彳是一个中心超平面构形，否则彳为 非中心超平面构形。 定义1 2 4 川给定构形彳= q ，i - 1 中超平面的线性序 ，对超平面q ，h ， i j 铮e q 。如果s = 何，h p ) 是相关的，但是对任意( p 1 ) 一元组 q ，e ，) 都是无关的，则称s 极小相关。若p 一元组s = ，h p ) 极小相关， 北京化t j 人学帧l j 学位论文 称s 是极小圈。 极小圈的全体记为c ( a ) ，乞= 乞( 彳) 表示k 度为行的极小圈全体。若s 是极 小圈，也称g2e i e 。j , j 极d 、圈。 定义1 2 5 t 1 1 设e e 。为数域赶上向量空问的一组基，定义以它们为荩生成的向 量空间：e 。= 赶，e 12 鲁瓦q ，e 2 2；2如赶qp，e，2。是悸。瓦p，一elp 1 。 ，2 ll s ， s 月 。 s ( ，。s 疗 其中疋q = 口qi 口尼) ，i c e , e , ：气= q ：e i ，l a e 厄，1 由。 并鱼e f ej = 一ej e i ，e 1 1 e | ：e i 3 = - e i 2 e i t e b2e i 2 e i - l l ，e f e i = 一e , e | = 0o e = e ooe 1o oe ”= oe 是数域j ) | c 上向量空间，乘法定义为 缈 口= ( 口l ，e t 气) ( 气厶e j , 气) = 气b j i 厶e j , e ，p e j r 0 ( 劬 e ) ， 并且满足以下条件： 1 e i ( a e s + b e k ) = a e j e + b e j e , t | ； 2 ( t i e ，+ b e s ) e k = a e , e k + 施，气； 3 ( e , e ，e k = e i ( e j e k ) ； 则e = oe 为数域瓦上的外代数。 定义1 2 6 1 q 设彳= 日，以) 为数域瓦上的中心构形，定义q = e l l , ，e n = 咆， e = e ( 彳) 叫做构形彳的外代数。 设e 1 = o 疋乞生成的外代数为e ，即e = e ( 彳) = a e l 。其中e o = | l c ， e 1 = 。塞。| 7 | c q ，e ，2 嘲 2 ，= 1 ，n 。其余的交点都是二重点。 线。 图3 一l 二维非中心构形彳 由定义可知二维非中心构形中： 1 2 = s p a ne q h ir 、hj = d ? u s p a n a e , j 八h lr 、h jn h k = 武。 因为在射影平面中任意两条直线都有交点，因此没有满足目nq = 矽的直 下面讨论生成元的集合 a ien 4n 以刃： e n q n 吼矿等价于， 兰 即三条直线共点。 综上所述，在上述二维非中心构形中，2 = s p a n b e j j kl 耳，h j ，风交与一点) 。 2 l j 、j 彩乃仇魏所巩 北京化t 人学硕i j 学位论文 3 2 二维非中心构形的缟不变量 引理3 2 1 - 设研条直线交于一点。定义向量组f = a i i , ，k e 【所】) ，那么 删尼( 引= 一) o 证明：稍时，e = o a e l 2 3 ，删( 讣- ，满足公加州f ) = ( 肌 所 3 时，拌f = ( ；) 。定义f 的部分组= a e , i i , j e 胁一l 】) ，那么 舟定= ( 历斗 任取元素a ，a = 勺一+ e j m ，由的定义可知勺在向量组砭的展 开式中是唯一出现的，凶此， 中的元素是线性无关的。 任取a 彤 2 ，= 1 ，n 。那么绣不变最可以表示为： 舭冲孔) o 例：设聊条直线交于一点，缟( 彳) _ 2 ( ：) 。 、j 图3 5 朋条直线交于。点 朋条直线交于一点，那么群名= ( ；) ，绝c 彳，= 2 ( ：) 。 2 0 第p q 章总结 第四章总结 织1 i 变量是f a l k 在参考文献 3 】中给出的，他讨论了织的拓扑学意义。张曦6 】 等证明了对顶点数大于3 的轮式图有唬不变量等于撑的两倍。 本文证明了不含子图k 的简单图构形以及射影平面中二维非中心构形的绝不 变量都等于 f 名的两倍。用公式熟( 彳) = 2 f 名，可以较快的得到本文讨论的两种超平 面构形的绣不变量。当简单图g 含有子图巧时，因为忍不是线性无关的，不能用 本文的证明方法得到唬不变量较为简单的计算公式。 下面考虑，用本文求得的公式唬( 彳) = 2 群名进行计算机编程计算绣不变景。 若彳为有m 个顶点，并且不含子图蜀的简单图构形，它的定义矩阵彳为m 行 m 列的矩阵，且每行只有两个非零元，一个为l 一个为1 ，矩阵中其它元素全部 为0 。例如超平而：葺一= o 所在的行，第i 列为l ，第j 列为- l ，其余列为0 。 例4 1 ：考虑图4 一l 的简单图定义的图构形 1 23 图4 一l 简单图 上图定义的超平面构形一个有四个超平面： q ：葺一x 2 = 0 彳( g ) ：只t t 2 ：吃x , - 一x 而3 = ：三 风：为一而= 0 2 l 4 北京化t 人学顺i ：学化论义 它的定义矩阵彳为4 行4 列的矩阵： a = 11 jo 0l o o o0 - 10 - l0 1 1 定义c 表示 仁。从a 中取m3 行，如线性相关则为极小圈，c 加l 。遍历所 么= l 从么中取出3 行，分别记系数矩阵4 = ( 兰墨 和增广矩阵4 = 兰乏墨 ( a ) 如果删七( 4 ) = r a n k ( a 2 ) = 2 ，那么三条直线交与一点，为极小圈，c 加1 。 ( b ) 如果r a n k ( a i ) = 1 ，r a n k ( a z ) = 2 ，那么二二条直线平行，在无穷远点相交，为 由( a ) ( b ) 可知，只要增广矩阵满足阳础( 4 ) = 2 ，就有编号为i , j ，k 的三个超平 不变量： a = 【l - 100 ；10 - 10 ；01 10 ；001 一l 】； m = s i z e ( a ，1 ) ； 平面数 n = s i z e ( a ，2 ) ； c = 0 ； o f o r i = 1 ：m 2 超平面构形的定义矩阵 矩阵a 的行数，也就是超平面构形的超 矩阵a 的列数 长度为3 的极小圈的个数，初始值设为 第p u 争总 a = z e r o s ( 3 ，n ) ；a ( 1 ，：) = a ( i ，：) ； f o r j = i + 1 ：m - l a ( 2 ，：) = a ( j ，：) ； f o r k _ j + i - m a ( 3 ，：) = a ( k ，：) ； i fr a n k ( a ) = = 2 c = c + i ： e n d e n d e n d e n d p h i 一3 = 2 宰c ； a c p h i _ 3 矩阵a 为任取a 中三行得到的矩阵，列数 和a 相同，行数为3 。 如果矩阵a 的秩为2 极小斟数加1 长度为3 的极小圈的两倍 输出超平面构形的定义矩阵 输出长度为3 的极小圈 输卅超、i 面构形的p h i _ 3 不变量 用这个程序计算例4 1 中图构形的绝不变量，程序中输入它的定义矩阵a = 【l - 1o 0 ；l0 - l0 ；0l - l0 ；00l l 】，运行程序，输出的结果为： a = 11 l0 o1 00 c2 1 p h i _ 3 = 0 1 1 l 0 0 0 - l 2 那么例4 1 中图构形长度为3 的极小圈个数为1 ，唬不变量为2 。 2 3 北京化t 人学坝i ：学位论义 例4 2 考虑如图4 2 的简单图定义的图构形，当顶点数n 大于5 时，这个简单图 不含完伞图心。 2 6 2 6 图4 2 当n = 6 和n = 8 时的图 当顶点数为n ，边数为3 x ( n 一2 ) ，将这些边对应的超平面分为三组： 们仁纛 j 只一l ：镌一毛= 0 2 ；3 i i 如( 帕) ：x 2 一20 皿，一3 ：x 3 一= 0 吼柚：x 3 一x 4 = 0 砘) ：一l 一20 第一组是与顶点l 相连的边对应的超平面，第二组是与顶点2 相连的边对应 的超平面，第三组是与项点l 和顶点2 都不相连的边对应的超平面。 用下面的m a t l a b 语句生成这个图构形的定义矩阵a ： n = 6 ：顶点个数 m = ( n 2 ) 木3 ； 边，即图构形中超平而个数 a = z e r o s ( m ，n ) ； 图构形定义矩阵为m 行n 列的 f o ri _ l ：n 2 a ( i ，1 ) = 1 ；a ( i ，i + 2 ) = - 1 ； 与顶点1 相连的边在矩阵中的表示 a ( i + n 2 ，2 ) = l ；a ( i + n 2 ，i + 2 ) = 1 ； 与顶点2 相连的边在矩阵中的表示 e n d a ( 2 * n 3 ，3 ) = l ；a ( 2 木n 3 ，n ) = 1 ； 与顶点l 和顶点2 都不相连的边在矩阵 f o ri = 2 ：n 2 中的表示 a ( i + 2 宰n 一4 ，i + 1 ) = l ； a ( i + 2 宰n 4 ，i + 2 ) = - 1