（应用数学专业论文）超可解构形与二次构形的关系及其相关问题.pdf

摘要 超可解构形与二次构形的关系及其相关问题 摘要 本文研究了超可解构形与二次构形的关系及其相关问题，主要由 两部分组成：( 1 ) 超可解构形与二次构形的关系。这部分中主要讨论了 一类特殊的超可解构形由破轮图所决定的图构形为二次构形的 充要条件，并通过应用举例列举出6 个顶点的破轮图所决定的图构形 为二次构形的所有排序；( 2 ) 超可解构形与二次构形的相关问题。这部 分中我们选取了5 类有趣的弦图来计算由其决定的图构形的模元极 大链的个数。 在第一部分中，我们分别得到了由破轮图所决定的图构形为二次 构形的必要条件和充分条件。然后得到了由破轮图所决定的构形为二 次构形的充要条件：由破轮图所决定的构形4 l + 。在序 下为二次构形 当且仅当构形4 l 在序 l 下为二次构形，且构形4 + 。的排序 满足下列 两种情形之一：( 1 ) 前3 个超平面所构成的有序集合为咄中或 一乙中或一中或一q - 中或乞一乞中或k 一中的 元素；( 2 ) 排序 的前3 个超平面所构成的有序集合为s h 中的元素，, 4 且超平面( 1 ，刀) ( 1 ，力+ 1 ) ，( 1 ，刀) ( 刀，刀+ 1 ) 。 在第二部分中，我们研究了由弦图所决定的图构形的模元极大链 的个数。我们首先得到：弦图的模元极大链的个数= m 链的个数= 顶 点消去序个数的一半。这样就把对弦图所决定构形的模元极大链个数 的讨论转化成对弦图的顶点消去序个数的讨论。我们计算了5 类有趣 的弦图的模元极大链的个数。 关键词：超可解构形，二次构形，破轮图，弦图，模元极大链 北京化t 大学硕士学位论文 t h er e l a t i o n s h i pb e t w e e ns u p e r s o l 、後b l e a r r a n g e m e n t sa n d q u a d r a t i c a r r a n g e m e n t sa n dt h e i rr e l a t e dq u e s t i o n s a b s t r a c t w es t u d yt h er e l a t i o n s h i pb e t w e e ns u p e r s o l v a b l ea r r a n g e m e n t sa n d q u a d r a t i ca r r a n g e m e n t sa n dr e l a t e dq u e s t i o n s t h i st h e s i si sc o m p o s e do f t w om a i np a r t s i nt h ef i r s t p a r t w es t u d yt h er e l a t i o n s h i pb e t w e e n s u p e r s o l v a b l ea r r a n g e m e n t sa n dq u a d r a t i ca r r a n g e m e n t s w em a i n l y c o n s i d e r a s p e c i a l c l a s so f s u p e r s o l v a b l ea r r a n g e m e n t s c a l l e d b r o k e n - w h e e lg r a p h i ca r r a n g e m e n t s i ti so b t a i n e dt h a tt h es u f f i c i e n ta n d n e c e s s a r yc o n d i t i o n s f o rb r o k e n - w h e e l g r a p h i ca r r a n g e m e n t s t ob e q u a d r a t i c w el i s ta l lt h eo r d e r su n d e rw h i c ht h ea r r a n g e m e n ta s s o c i a t e d t ot h es i x v e r t e xb r o k e n w h e e li sq u a d r a t i c i nt h es e c o n dp a r t ，w ed i s c u s s t h er e l a t e dq u e s t i o n sb e t w e e ns u p e r s o l v a b l ea r r a n g e m e n t sa n dq u a d r a t i c a r r a n g e m e n t s f i v ei n t e r e s t i n gc h o r dg r a p h sa r ep i c k e do u tt oc o m p u t e t h en u m b e ro ft h em a x i m a lm o d u l a rc h a i n s w ep r o v e dt h a ta r r a n g e m e n ta i sq u a d r a t i cu n d e ro r d e r i fa n d 一一 n 1 - i o n l yi fa r r a n g e m e n t4i sq u a d r a t i cu n d e ro r d e r la n dt h eo r d e r o f 4 胂ls a t i s f ye i t h e ro ft h ef o l l o w i n gc o n d i t i o n s ：1 ) t h eo r d e r e ds e t c o m p o s i n gb yt h ef i r s tt h r e eh y p e r p l a n e so fo r d e r i st h ee l e m e n to fs e t 摘要 一级o rs e t 乙一乙o rs e t 一o rs e t 一绞o rs e t k 一毛o rs e t x 石一k ；2 ) t h e o r d e r e ds e tc o m p o s i n gb yt h ef i r s tt h r e e h y p e r p l a n e so fo r d e r i st h ee l e m e n to fs e ts h a n dh y p e r p l a n e s 一一一月 一一 一 ( 1 ，刀) a n d ( 1 ，n + 1 ) a n d ( 刀，n + 1 ) s a t i s f y ( 1 ，1 ) ( 1 ，刀+ 1 ) ，( 1 ，刀) ( 刀，n + 1 ) w e l i s ta l lt h e o r d e r su n d e rw h i c ht h e a r r a n g e m e n ta s s o c i a t e d t ot h e s i x - v e r t e xb r o k e n - w h e e li sq u a d r a t i c i n t h es e c o n dp a r t ，w es t u d yt h en u m b e ro ft h em a x i m a lm o d u l a r c h a i n sf o ra r r a n g e m e n t sd e t e r m i n e db yc h o r dg r a p h s i ti sf o u n dt h a tt h e n u m b e ro ft h em a x i m a lm o d u l a rc h a i n sf o rc h o r dg r a p h se q u a l st ot h e n u m b e ro fm c h a i n sa n de q u a l st oh a l fo ft h en u m b e ro ft h ev e r t e x e l i m i n a t i o no r d e r s t h e r e f o r e ，c o m p u t i n gt h en u m b e ro ft h em a x i m a l m o d u l a rc h a i n si st r a n s f e r r e dt oc o m p u t i n gt h en u m b e ro ft h ev e r t e x e l i m i n a t i o no r d e r s w ec o m p u t et h en u m b e ro ft h em a x i m a lm o d u l a r c h a i n sf o ra r r a n g e m e n t sd e t e r m i n e db yf i v ei n t e r e s t i n gc h o r dg r a p h s k e y w o r d s ：s u p e r s o l v a b l ea r r a n g e m e n t ，q u a d r a t i ca r r a n g e m e n t ， b r o k e n w h e e lg r a p h ，c h o r dg r a p h ，m a x i m a lm o d u l a rc h a i n m 北京化工人学硕 ：学位论文 符号说明 ，域 以，h = ( f ，a i 八超平面构形 g = ( 矿，e ) 图 由n 个顶点的破轮图所决定的图构形，它 a和破轮图是等价的，所以也可称其为n 个 顶点的破轮图 h = ( f ，力，i j ，且( f ，j ) 是 以中的边 b c ，t 乙 级 x 吒，饥，q ，以，巳 图构形彳中的超平面 构形彳的破圈集 构形彳的元素个数为2 的破圈所构成的集 厶 口 构形以的有序竹子的集合 构形以的有序圈的集合 构形以的有序星的集合 弦图的模元极大链的个数 v u i 北京化工大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 作者签名：i 垂旦& &日期：2 旦立金。匹兰翌 关于论文使用授权的说明 学位论文作者完全了解北京化工大学有关保留和使用学位论文 的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北 京化工大学。学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编 学位论文。 保密论文注释：本学位论文属于保密范围，在土年解密后适用 本授权书。非保密论文注释：本学位论文不属于保密范围，适用本授 权书。 作者签名：主! 壶i 惑圣 导师签 日期：圣q 旦刍：堇兰望 日期：2 争虬 第一章绪论 1 1 背景知识简介 第一章绪论 令f 是一个域，超平面就是f 7 中余维数为1 的仿射子空间。f 7 中的超平面构 形就是f 中有限个超平面的集合，记作彳= 羁，1 - i 。如果超平面构形彳满 足n 封“日9 ，则称构形么是中心的。 令彳是矿= ，。中的超平面构形。我们定义一个偏序集厶( 彳) ，其中的元素为 n 茸嚣h ，满足器c _ a ，且n 封专矗h 掌彩；规定五( 彳) 中元素的序为反包含关系。注 意到彩彳，所以vee ( 彳) ，且对vxl ( m ) ，v x 。对于x l ( m ) ，我们 定义凇放z ) ：= c o d i m x ，且定义翮彳) 擞a x 盖e “，r a n k ( x ) 囝。 令彳= q ，纪 是矿= f 7 上的超平面构形，这里f 是一个域。我们规定彳 上的序如下：鼍 q 当且仪当i 歹，垦彳，鳞彳。令s = 氓，气是彳的 子集，如果n s a 且旭刀后( n s ) i s l ，则称s 是相关的。令s = q ，取) 是么的子集，如果s 是相关的，且对p 惫， 墨，心，心 是无关魄，雯l l 称s 是极小相关的。 令彳是一个中心超平面构形，把彳中超平面的序记作。令 君c 掣爷a ：3 h m i n s 使褥艘 u s 是极小相关的 。如果对蝣e b c , s t e b c 使得r s 且例：2 ，则称彳关于序 是二次的【2 】。 令彳是一个中心超平面梅形。如果对泡l ( m ) ，豆zg y ， z v ( x y ) = ( z v 肖) 】，成立，则称( x ，y ) l ( m ) x l ( m ) 是一个模对。如果对 v 7el ( m ) ，( x ，d 都是模对，则称x ( 彳) 是模元。令r a n k ( m ) = l 。如果三( 棚 有一个模元极大链矿= x o 五 五= f l 打“曰，则称构形彳是超可解构形。 北京化t 大学硕f j 学位论文 令彳是中心超平面构形，其中超平面的序为 。如果彳是超可解的，且满 足：对于三( 彳) 中的模元极大链v = 五 x 。 l ，五= n 工。q ，且若超平面日 五，则 日 q ，只。 。则我们称序 代表超可解的结构【2 1 。 图g = ( 矿，e ) 是一个序对，这里矿= v ( g ) = 1 ，2 ，n ) = n 】，e = e ( g ) 是由矿 中2 个元素的子集构成的集合。集合y 称作顶点集，e 称作边集。我们用e 表 示有刀个顶点且每两个顶点之间都有边的完全图。对于每一个 ，矿，它都有一 个邻域，n ( v ) - - j y l v ，办e ) 。如果ucv ，f e ，则我们称日= ( u ，f ) 是g 的子图。假定u v ，令e ( u ) = p ，y l i ，歹u 且p ，歹) 毋，图q = ( u ，e ( u ) ) 称 作u 的顶点诱导的子图。如果v 矿，则我们用g - v 来表示诱导的子图g ，。如 果p e ，则我们用g p 来表示顶点集是矿，边集是e e 的刚3 1 。 图g 中的圈c 是顶点v o ，m ，u 的序列，且满足对0 f l - 1 ， v t , v f + j e ， 且除了= m 外，对v f ，j ，m 。圈c 的弦是边如，屹) ，这里k ，是圈中不相 邻的顶点。如果图g ( v ，切的每一个长度大于3 的圈都有一个弦，则称图g 为弦 图【3 】o 令g = ( 矿，e ) 是图，v ，如果g 是完全图，则称，是单纯形点。如果图 g 有一个顶点序，h ，满足：对v 1 f n - 1 ，顶点k 是图g 一“，唯) 的单 纯形点，则称图g 有个顶点消去序，m ，匕【射。 1 2 研究现状 超平面构形是最近3 0 几年才开始发展起来的- i 新兴的数学分支，且得到 越来越多的学者关注m 。超可解构形是超平面构形中一个很重要的概念。相应 地学者们也得到了很多关于超可解构形的结论。p a u lh e d e l m a n 和v i c t o rr e i n e r 2 第一章绪论 得到了关于超可解构形的两个重要结论，即( 1 ) 令g = ( y ，e ) 是图，则下面两条等 价：g 是弦图；g 有一个顶点消去序，而且g 的任意一个单纯形点都可以作 为这个顶点消去序的开头顶点。( 2 ) 令g = ( y ，e ) 是图，则下面两条等价：g 是 弦图，且有顶点消去序，h ，；彳( g ) 是超可解构形，且有m - 链o 彳( g 一“，屹一。) ) c c 彳( g 一“) ) c a ( g ) 嘲。通过这两个定理我们知道，如果 一个图为弦图，则它一定有一个顶点消去序，相应地这个弦图所决定的构形为超 可解构形，且对应一个m 链。那么我们是否可以通过计算弦图的顶点消去序的 个数来计算弦图所决定的构形的模元极大链的个数呢? 二次构形也是超平面构形中很重要的概念，对于超可解构形与二次构形这两 个概念单独的研究，我们得到了很多结果，但把他们联系起来进行研究的却很少。 y u z v i n s k ys 对二次o r l i k - s o l o m o n 代数进行了讨论，并得到结论：o r l i k - s o l o m o n 代数么：钐是二次的当且仅当o r l i k - s o l o m o n 理想i 由厶生成引，这相当于把对 二次构形的讨论转化成对二次o r l i k s o l o m o n 代数的讨论了。而p e a r s o nk j 直接 给出了超可解构形与二次构形的关系，即：中心超平面构形彳为超可解构形当且 仅当么在某个序下为二次的，并且这个序能代表超可解的结构 2 1 。这个定理的详 细证明是由b j o i n e r a 和z i e g l e rg 给出的 9 1 ，即若一个中心构形是超可解的，则 它在某个序下是二次的，并且这个序能代表超可解的结构f 2 l 。那么也就是说此时 存在这样一个序，使得这个中心超可解构形在这个序下为二次的，那么这个序是 什么样子的，此时有多少个序能使得这个中心的超可解构形为二次的呢? 对于这 个问题，我们直接从二次构形的定义出发来研究，即着眼于研究二次构形的序， 这就提出了本文的研究内容。 1 3 本文主要内容 本文主要研究的是超可解构形与二次构形的关系及其相关问题。在研究超可 解构形与二次构形的关系中，我主要是选取了一类特殊的超可解构形由破轮 图所决定的构形，研究这类构形在什么样的序下为二次构形，讨论这些序具有什 么样的规律，最后得到这类构形为二次构形的一个充要条件，即由破轮图所决定 3 北京化工人学硕仁学位论文 的构形以+ ，在序 下为二次构形当且仅当构形4 在序 。下为二次构形，且4 + 。的 排序 满足下列两种情形之一：( 1 ) 前3 个超平面所构成的有序集合为。一线中 或z 钿一z 中或k 一中或一线中或乞一z u 中或k k 中的元 素；( 2 ) 排序 的前3 个超平面所构成的有序集合为，中的元素，且超平面 ( 1 ，刀) ( 1 ，月+ 1 ) ，( 1 ，刀) ( 刀，n + 1 ) 。在研究超可解构形与二次构形的相关问题中，我 主要是计算了另一类特殊的超可解构形由弦图所决定的超可解构形的模元 极大链的个数。我选取了5 类弦图，每类弦图都有一定的规律，并且这5 类弦图 之问也具有一定的规律。在计算的过程中，主要是通过计算弦图的顶点消去序的 个数来计算模元极大链的个数的。最后发现不仅每类弦图的模元极大链的个数有 规律，类与类之间的弦图的模元极大链的个数也有一定的规律。具体结果如下： 第一类弦图的模元极大链的个数为a 。= 6 * 2 n - 4 , 捍= 4 ，5 ，6 ，：第二类弦图的模元极 大链的个数为吃= 1 2 2 ”- 5 , 刀= 5 ，6 ，7 ，；第三类弦图的模元极大链的个数为 岛= 1 2 ，巳= 3 奉2 ”2 - 1 2 ，n = 6 ，7 ，；第四类弦图的模元极大链的个数为 以= 2 4 , 2 - e , n = 6 ，7 ，； 第五类弦图的模元极大链的个数为 吃= 7 2 * 2 ”一6 + 2 4 1 2 宰栉，刀= 6 ，7 ，。 1 4 本文结构安排 本文结构主要分为两个部分。 第一部分是第二章，首先介绍了一些基本知识，然后通过一个引理和4 个定 理的证明，最后给出了由破轮图所决定的图构形为二次构形的一个充要条件。最 后对定理5 进行了应用，即通过应用定理5 来给出当顶点个数为5 时的破论图所 决定的构形为二次构形的所有排序。 第二部分是第三章，主要研究了由弦图所决定的构形的模元极大链的个数。 我们找出了5 类呈现一定规律的弦图，计算其模元极大链的个数，并找出其中的 规律。 4 第二章破轮图所决定构形为二次构形的证明 第二章破轮图所决定构形为二次构形的证明 2 1 预备知识 把破轮图按照图2 - 1 ( a ) 所示对顶点进行编号，记由r 1 个顶点的破轮图所决定的 图构形为以，所以可以把以看成以+ 的子构形：- 4 - 4 + 。把由边( f ，) ( 如 果内) 所对应的超平面记作o ，) ，其中蝎为破轮图中的顶点。这就把对于构形 问题的讨论转化成对破论图直接进行讨论。设 为的有序竹子。 称只的有序星( 竹子) 都为构形以的有序星( 竹子) ，k = 2 ，n - 2 。 设s = z ，破，马) 瓯，有序集 日。，马) ， h 。，马，4 ，慨，q ，马) ， 4 ，吼，。) ，眠，日。，) ， 玛，皿，q ) 称为s 的有序圈。称s 的有序圈都为 构形以的有序圈。 有序星、有序竹子、有序圈的定义中都是按照每个子图书写的顺序规定其中 超平面的序的。 令级，叛，乞分别为构形以中有序圈，有序星，有序竹子的集合。若以+ 。 中的序为 ，记以的序为 。，序 。是在排序 中去掉超平面( 1 ，以+ 1 ) ，( 刀，”+ 1 ) 之 后剩下的超平面的排序。 2 2 由破轮图所决定的图构形为二次构形的必要条件 引理：若4 。在序 下为二次构形，则以在 。下也为二次构形。 证明：因为以+ 。为二次构形，所以对vs b c ，3z 。，使得r s 。显 见b c _ s 男，所以对v 墨曰c - ，3 墨，使得互冬墨。下证墨致。 因为墨曰，所以墨中不包含超平面( ，l ，以+ 1 ) 和( 1 ，n + 1 ) 。所以互不可能是极 小圈( ( 1 ，行) ，o ，刀+ 1 ) ，( 1 ，捍+ 1 ) ) 所形成的破圈，所以互幺，即以为二次构形。 定理1 ：设 为构形以的一个序。若构形4 在序 下为二次构形，则序 需满足： 前3 个超平面或构成有序圈，或构成有序星，或构成有序竹子。 证明：当k = 4 时，此时破轮图如图2 2 所示，并把图中每一条边按照如图所示进 行编号，通过编写程序我们得出了此时的图构形在哪些序下为二次构形，具体 的结果和具体的程序见附录。由附录知此时结论成立。 6 第二章破轮图所决定构形为二次构形的证明 2 图2 - 2标上号的5 个顶点的破轮图 f i g 2 2 b r o k e n w h e e ls i g n e dw i t hf o u rv e r t e x e $ 假设当随时结论成立。当k - - n + 1 时，因为以+ 。为二次构形，所以j 以+ 。的一个 序 满足二次构形的定义，且由引理1 可知，构形以在序 。下也为二次构形。 ( 1 ) 记口= ( 1 ，2 ) ，( 1 ，3 ) ，( 1 ，以一2 ) ，( 2 ，3 ) ，( 3 ，4 ) ，0 2 ，以一1 ) ) 4 。若序 以b 中的 一个超平面开头，因为以为二次构形，所以序 l 中的前3 个超平面构成有序圈 或有序星或有序竹子，要想证明序 满足定理的结论，则需证明此时超平面 ( 1 ，n + 1 ) 与( ，l ，n + 1 ) 都不能在序 的第2 和第3 个位置。- 用反证法：不妨设超平面( 1 ，n + 1 ) ，即( 1 ，1 ) ( 1 ，刀一1 ) ，( 1 ，甩) ( 以一1 ，厅) 。讨论极小圈 ( 1 ，刀一2 ) ，( 1 ，刀+ 1 ) ，o 一2 ，刀一1 ) ，仰一l ，以) ，( 玎，疗+ 1 ) ) ，它可形成以下几种破圈a ， ( 1 ， + 1 ) ，( n - 2 ，n - 1 ) ，( 刀- 1 ，疗) ，( 以，刀+ 1 ) ) 或者b ，( ( 1 ，以- 2 ) ，( n - 2 ，刀- 1 ) ， ( n 一1 ，以) ，( 拧，l + 1 ) ) 或者c ， ( 1 ，以一2 ) ，( 1 ，以+ 1 ) ，( 订一1 ，刀) ，( 刀，刀+ 1 ) ) 或者也 0 ，刀一2 ) ，( 1 ，刀+ 1 ) ，( y - - 2 ，刀一1 ) ，( 刀，刀+ 1 ) ) ( 此时超平面( 刀一1 ，刀) ( 1 ，n + 1 ) 在第一位 置，( n - 1 ，疗) 诺b 矛盾) 或者e ， ( 1 ，疗一2 ) ，( 1 ，玎+ 1 ) ，一2 ，以一1 ) ，( n - 1 ，力) ) ( 这表明超 平面( ，l ，l + 1 ) 在( 1 ，n + 1 ) 前面，矛盾) ，因为情况a 和c 的元素个数为2 的子集都不 属于砜，所以为了满足二次构形的定义，只剩下情况b ，而情况b 中，能属于 的只有 ( 1 ，n - 2 ) ，( 刀一2 ，即一1 ) ) ，即超平面( 1 ，n - 1 ) ( 1 ，n - 2 ) ，( 1 ，n - 1 ) ( n - 2 ，n - 1 ) 。 7 北京化工大学硕上学位论文 讨论极d 、圈 ( 1 ，n 一3 ) ，0 ，刀+ 1 ) ，( n - 3 ，n 一2 ) ，( 刀一2 ，l 1 ) ( 万一1 ，刀) ，( 刀，疗+ 1 ) ) ， 得到超平面( 1 ，以一2 ) ( 1 ，刀一3 ) ，( 1 ，n - 2 ) ( n - 3 ，n - 2 ) ，讨论完( 。一屯) 中的所 有元素之后，可得超平面( 1 ，刀) 日，对vh ( 以- 0 ，n ) ) ) ，又因为 ( 1 ，咒+ 1 ) ( 刀，刀+ 1 ) 且( 1 ，力+ 1 ) 排在第2 位置，矛盾。 超平面( 1 ，力+ 1 ) 在第3 个位置。再分3 种情况讨论：a ，( 1 ，刀) 在序 下排在第1 位置，因为( 1 ，z ) 仨召，矛盾。b ，( 1 ，刀) 在序 下排在第2 位置，而超平面( 1 ，栉) 在 第2 个位置的有序星，有序竹子和有序圈都是以超平面( 1 ，n 一1 ) 在第1 位置的， 而( 1 ，聆一1 ) 诺召，矛盾。c ，( 1 ，刀+ 1 ) ( 1 ，疗) 。所以 ( 1 ，刀) ，( 刀，刀+ 1 ) ) 。考虑极 小圈琏= ( 1 ，刀一1 ) ，( n - l ，以) ，( 1 ，万+ 1 ) ，( 以，刀+ 1 ) ) 所形成的破圈，只有当( 1 ，聆+ 1 ) s ， 对vs ( 琏一 ( 1 ，刀+ 1 ) ) ) 时，琏形成的破圈为 ( 1 ，n - 1 ) ，( n 一1 ，n ) ，( 咒，以+ 1 ) ) 才可满 足二次构形的定义，且必须有 ( 1 ，n 一1 ) ，( n 一1 ，n ) ) 。，即( 1 ，以) ( 1 ，以一1 ) ， ( 1 ，n ) q 一1 ，n ) 。再讨论由极小圈强= ( 1 ，万一2 ) o 一2 ，刀一1 ) ，o 一1 ，刀) ，0 ，刀+ 1 ) ， ( 刀，疗+ 1 ) ) 所形成的破圈。因为( 1 ，阼+ 1 ) s ，对vs 琏一 ( 1 ，刀+ 1 ) ) ，所以只有当 ( 1 ，以+ 1 ) ) 时，毋所形成的破圈才可满足二次构形的定 义，且必须有 ( 1 ，n - 2 ) ，( 以一2 ，万一1 ) ) 。即( 1 ，孵一1 ) ( 1 ，万一2 ) ，( 1 ，刀一1 ) 一2 ，n - 1 ) ，讨论完( 一屯) 中的所有元素之后，可得( 1 ，以) 日，对 v 日( 以一 ( 1 ，以) ) ) 。又因为( 1 ，万+ 1 ) ( 1 ，刀) ，( 1 ，以+ 1 ) ( 理，厅+ 1 ) ，所以( 1 ，”+ 1 ) 日， 对v 日( 4 + 。一 ( 1 ，刀+ 1 ) ) ) ，这与( 1 ，玎+ 1 ) 排在序 中第3 个位置矛盾。 ( 2 ) 若序 ) 。依次讨论上述b c 中的元素，可以得到：( 1 ，n ) ( 1 ，咒一1 ) ，( 1 ，帕 第二章破轮图所决定构形为二次构形的证明 ( 力一1 ，以) ，( 1 ，刀一1 ) ( 1 ，刀一2 ) ，( 1 ，n 一1 ) ( 以一2 ，n 一1 ) ，( 1 ，3 ) ( 1 ，2 ) ，( 1 ，3 ) ( 2 ，3 ) 综合 以上结果，可以得出前3 个超平面可以形成有如下几种有序集合： 冬 ( 1 ，以+ 1 ) ，( 1 ，1 ) ，( 1 ，万一1 ) ) 为有序星b ， ( 1 ，刀+ 1 ) ，( 1 ，刀) ，0 一l ，以) ) 为有序竹子，c ， ( 1 ，以+ 1 ) ，( 玎，疗+ 1 ) ，( 1 ，以) 为有序圈，d ( 1 ，刀+ i ) ，( 1 ，z ) ，( 咒，甩+ 1 ) ) 为有序圈，则结论 成立。 以( ，l ，n + 1 ) 开头的；证明同，把中的超平面( 1 ，刀+ 1 ) ，( 刀，n + 1 ) 对换即可。 以( 1 ，n ) 开头的；分为3 种情况：不妨设( 1 ，n + 1 ) ( 栉，n + 1 ) 。a ，( 1 ，n + 1 ) 排在序 中的第2 个位置。所以b c i q 一曰c i = ( 1 ，咒+ 1 ) ，( 力，l + 1 ) ) ， ( 1 ，刀一1 ) ，o 一1 ，刀) ， ( 拧，以+ 1 ) ， ( 1 ，2 ) ，( 2 ，3 ) ，( n - 1 ，刀) ，( 刀，订+ 1 ) ) ) 考虑鼠= ( 1 ，n 一后) ， ( n - k ，n 一七+ 1 ) ，( ，l ，l + 1 ) ) ，k = 1 ，2 ，n - 2 ，因为( 1 ，万) 在序 l 下排在第1 位置，所 以色= ( 1 ，刀一后) ，( 刀一k ，刀一后+ 1 ) 9 0 0 9 0 1 ，刀) ) 曰c i ，又因为 在序 下为二次 的，所以了正致轧，使得砭甄量最，所以b c l b c i 中的元都满足二 次构形的定义。因为序 i 中的前3 个超平面为有序星，有序竹子，有序圈，注意 到以超平面( 1 ，n ) 开头的有序星，有序圈，有序竹子中都是以超平面( 1 ，n 一1 ) 或 ( n - l ，刀) 排在第2 个位置的，所以序 中前3 个超平面可以形成如下几种有序集 合 ( 1 ，以) ，( 1 ，l + 1 ) ，( 刀，刀+ 1 ) ) ( 有序圈) 或者 ( 1 ，疗) ，( 1 ，刀+ 1 ) ，( 1 ，玎一1 ) ) ( 有序星) 或 者 ( 1 ，1 ) ，( 1 ，以+ 1 ) ，( n - l ，以) ) ( 有序竹子) 。b ，( 1 ，n + 1 ) 排在序 中的第3 个位置。 所以 ( 1 ，刀+ 1 ) ，( 刀，以+ 1 ) ) 瓦讨论由极小圈瓯= ( 1 ，行一后) ，o k ，n 一后+ 1 ) ， ( 玎，珂+ 1 ) ，( 1 ，刀+ 1 ) ) 所形成的破圈忍，k = 2 ，n - 2 。若( 1 ，n - k ) h ，对 v h ( 瓯一 ( 1 ，刀一尼) ) ) ，则琏中含有( 1 ，刀+ 1 ) ，0 ，n + 1 ) ，因为 ( 1 ，刀+ 1 ) ，( 行，以+ 1 ) ) 钆，所以巨满足二次构形的定义；记皿= 0 一k + i ，n 一七+ 1 + i ) ，i = 0 ，1 ，k - 1 ， 若q h ，对vh ( 一县) ，则最中含有0 ，刀+ 1 ) ，( 刀，刀+ 1 ) ，因为 ( 1 ，刀+ 1 ) ，( 万，以+ 1 ) ) 九，所以琏满足二次构形的定义；若( 1 ，珂+ 1 ) 日，对v o 北京化工大学硕十学位论文 h ( 瓯一 ( 1 ，咒+ 1 ) ) ) ，则鼠= ( 1 ，疗一七) ，( n - k ，n - k + 1 ) ，( n - 1 ，玎) ) 琏，又因为 ( 1 ，刀) 在序 。下排在第l 位置，所以了鼠口c i ，又因为 在序 。下为二次的， 所以互& t 厶i1 1 使得互统甄，所以琶也满足二次构形的定义。所以序 中前3 个超平面可以形成如下几种有序集合 ( 1 ，刀) ， ( 1 ，万一1 ) ，( 1 ，一十1 ) ) ( 有序星) 或者 ( 1 ，刀) ， ( n - 1 ，疗) ，( 1 ，刀+ 1 ) ) ( 有序竹子) 。c ，其他情况，因为序 。中的前3 个超 平面所构成的有序集合为有序星，有序竹子，有序圈，所以结论成立。 以 一1 ，疗) 开头的；分为3 种情况：不妨设( 1 ，n + 1 ) ( 刀，n + 1 ) 。a ，( 1 ，n + 1 ) 排在 序 中的第2 个位置，所以 ( 1 ，靠) ，( 以，刀+ 1 ) ) 瓦。， ( 1 ，行一1 ) ，( 刀，刀+ 1 ) ，( 1 ，刀+ 1 ) ) 召c k 。，因为这个破圈的任意含有2 个元素的子集都不可能属于瓦。，即这个 破圈不满足二次构形的定义，矛盾。b ，( 1 ，n + 1 ) 排在序 中的第3 个位置。若( 1 ，n ) 不在序 中第2 个位置，讨论同上；若( 1 ，刀) 在序 中第2 个位置，则 口c l 州一艿c i2 ( 1 ，疗+ 1 ) ，( 刀，n + 1 ) ) ， ( 1 ，刀一1 ) ，( ，l ，丹+ 1 ) ，( 1 ，疗+ 1 ) ， ( 1 ，2 ) ，( 2 ，3 ) ， o 一2 ，n 1 ) ，( 刀，拧+ 1 ) ，( 1 ，刀+ 1 ) ) ) 。则每一个破圈都满足二次构形的定义，在序 中 前3 个超平面可以形成有序集合 0 1 ，疗) ，( 1 ，疗) ，( 1 ，以+ 1 ) ) ( 有序竹子) 。c ，其他 情况。证明同中的c 。 以( 1 ，万一1 ) 开头的。讨论同，证明过程和结果中把( n - 1 ，n ) 与( 1 ，n - 1 ) 对换即 可。 2 3 由破论图所决定的图构形为二次构形的充分条件和结论 定理1 - 对于构形s t + 。，若它有一个序 的前3 个超平面所构成的有序集合为 一纵中或乙一z i 中或扎。一奴中的元素，且a 在序 。下为二次构形， 则a + ，在序 下也为二次构形。 证明：因为a 在序 。下为二次构形，所以要证 + 在序 下为二次构形，只要 1 0 第二章破轮图所决定构形为二次构形的证明 证对vs ( 曰一曰q ) ，jt e 轧，使得r s 。 ( 1 ) 序 的前3 个超平面所构成的有序集合为一级中的元素。设这个元素为s ， 则i 有以下几种情况。 s = ( 1 ，咒+ 1 ) ，( 刀，刀+ 1 ) ，0 ，1 ) ) 或 ( 1 ，刀+ 1 ) ，( 1 ，甩) ，( 靠，万+ 1 ) ) 。则b c 0 - b c i = ，证明同上。 s = ( 1 ，玎) ，( 刀，疗+ 1 ) ，( 1 ，拧+ 1 ) ) ，证明同j ! 。 ( 2 ) 序 ，证明同( 1 ) 中。 ( 9 s = ( 1 ，以一1 ) ，( 1 ，刀) ，( 以，刀+ 1 ) ) 或 ( 1 ，以) ，( 1 ，以一1 ) ，( 咒，疗+ 1 ) ) ，贝i j b c l 一口c i = 北京化t 大学硕士学位论文 ( 1 ，l + 1 ) ，( 以，玎+ 1 ) ) ， ( n 一1 ，z ) ，( 刀，忍+ 1 ) ，( 1 ，l + 1 ) ) ， ( 1 ，2 ) ，( 2 ，3 ) ，( 以一1 ，门) ， ( 1 ，n + 1 ) ) ) 。显然 ( n ，n + 1 ) ，( 1 ，n + 1 ) s ( n - 1 ，n ) ，( n ，n + 1 ) ，( 1 ，n + 1 ) ) ， 且 ( 靠，万+ 1 ) ，( 1 ，万+ 1 ) ) 九。，所以( q 一1 ，行) ，( 刀，n + 1 ) ，( 1 ，以+ 1 ) ) 满足二次构形的定义。 因为在序 下，超平面( 1 ，刀一1 ) 排在前面，所以 ( 1 ，刀一2 ) ， 一2 ，刀一1 ) ) 。，且 ( 1 ，n - 2 ) ，( n - 2 ，n - 1 ) ) ( 1 ，n - 2 ) ，( n - 2 ，n - 1 ) ，( n - 1 ，刀) ，( 1 ，厅+ 1 ) ) ，所以 ( 1 ，n - 2 ) , ( n - 2 ，万一1 ) ，( n - 1 ，挖) ，( 1 ，刀+ 1 ) ) 满足定义。因为在序 下，超平面( 1 ，以一1 ) 排在前面， 所以 ( 1 ，以一3 ) ， 一3 ，刀一2 ) ，一2 ，刀一1 ) ) b q 。又因为 在序 。下为二次构形， 所以了t & 使得丁 ( 1 ，刀一3 ) ，( 行一3 ，刀一2 ) ，( 刀一2 ，靠一1 ) ) ( 1 ，l 一3 ) ， ( 刀一3 ，疗一2 ) ，( 刀一2 ，力一1 ) ，( 万一1 ，刀) ，( 1 ，刀+ 1 ) ，所以 ( 1 ，n - 3 ) ，( n - 3 ，n - 2 ) ，( n - 2 ，n - 1 ) ， 仰一1 ，疗) ，( 1 ，刀+ 1 ) ) 满足定义。依次有曰c l 一曰c 中的元都满足定义。 ( 自s = ( 刀一l ，以) ，( 1 ，咒) ，( 1 ，万+ 1 ) ) 或 ( 1 ，厅) ，( 以一1 ，以) ，( 1 ，刀+ 1 ) ) ，贝u 曰c _ 州一b c = ( 1 ，l + 1 ) ，( 刀，捍+ 1 ) ) ， ( 1 ，n - 1 ) ，( 疗，l + 1 ) ，( 1 ，刀+ 1 ) ) ， ( 1 ，咒一2 ) ，( 疗一2 , n 一1 ) ，( 1 ，n + 1 ) ， ( 刀，刀+ 1 ) ) ， ( 1 ，2 ) ，( 2 ，3 ) ，( n - 2 ，n - 1 ) ，( 刀，刀+ 1 ) ，( 1 ，以+ 1 ) ) ) ，因为( ( 1 ，行+ 1 ) ，( 刀，刀+ 1 ) ) 孔。，且 ( 1 ，珂+ 1 ) ，( 刀，刀+ 1 ) ) 为曰c 0 一曰c 凡中其他元素的子集，所以 曰c 0 一b c a 中的元素都满足二次构形的定义。 3 ) 序 的前3 个超平面所构成的有序集合为置一k 中的元素，设这个元素 为j ，则否有以下几种情况。 s = ( 1 ，_ ，l + 1 ) ，( 1 ，甩) ，( 1 ，n - 1 ) ) ，证明同( 1 ) 中； s = ( 1 ，刀) ，( 1 ，以+ 1 ) ，( 1 ，n - 1 ) ) ，证明同( 1 ) 中； s = ( 1 ，1 ) ，( 刀，以+ 1 ) ，( 万一1 ，力) ) ，证明同( 1 ) 中； s = ( ，l ，l + 1 ) ，( 1 ，刀) ，( 刀一1 ，以) ) ，证明同( 1 ) 中； s = ( 1 ，n 一1 ) ，( 1 ，以) ，( 1 ，以+ 1 ) ) 或 ( 1 ，力) ，( 1 , n 一1 ) ，( 1 ，刀+ 1 ) ) ，证明同( 2 ) 中； 1 2 第二章破轮图所决定构形为二