（基础数学专业论文）可分解三元系的大集和超大集.pdf

河北师范大学博士学位论文 摘要 1 8 4 7 年，t p k i r k m a n 提出了“1 5 个女学生问题”之后，j j s y l v e s t e r 又连一步提出 了著名的 s y l v e s t e r 问题：其一般情形( 将女生数1 5 推广为正整数 ) 即是现今所称的 柯克曼三元系大集( l k t s ( v ) ) 问题这是组合设计史上的第一个大集问题，迄今已有 长达一百五十多年的历史由于它的高难度，至今距完全解决还相去甚远 1 9 9 1 年，m j s h a r r y 和a p s t r e e t 首先提出了超大集的概念并确定了s t s ( v ) 超大集o l s t s ( v ) 存在的充要条件之后，m t s ( v ) 超大集o l m t s ( v ) ，d t s ( v ) 超大 集o l d t s ( v ) 以及一些图设计超大集等类问题也都有广泛的研究但迄今为止，关于 i f t s ( v ) 超大集o l k t s ( v ) 的讨论还很少 本文从讨论o l k t s ( v ) 的3 倍构造着手，引入了广义k i r k m a n 三元系的超大集 o l g k 只给出了这个新概念与o l k t s ( v ) 间的关系，以及它的递归构适和一些存在性 结果进而得到了o l k t s ( v ) 的一些新结论，找到了完全解决o l k t s ( v ) 的一条有效 途径。并利用f ( 3 ，4 ，扣+ 1 ) 2 ) ) 和带有特殊性质的o l k t s ( 2 v + i ) 扩大了l k t s ( 6 v + 3 ) 的存在性结果本文还得到了有向三元系大集和超大集存在的新结果，并对2 长链p 3 ， 有向2 长链焉，露，霹和混合三长围码等图，得到了相应图设计超大集的一系列存 在性结论 关键词：柯克曼三元系。大集，超大集。广义柯克曼三元系超大集 河北师范大学博士学位论文 l a r g es e t sa n do v e r l a r g es e t so ft r i p l es y s t e m sw i t hr e s o l v a b i l i t y a b s t r a c t i n1 8 4 7 t e k i r k m a n p o s e d t h e p r o b l e m a b o u t l 5 s c h o o l g i r l s a f t e r t h a t 。j j s y l v e s t e r p o s e d t h ef a m o u ss y l v e s t e r sp m b & mi n1 8 5 0 t h eg e n e r a l i z e dc a s eo ft h i sp r o b l e mi sc a l l e dl a r g es e to f d i s j o i n tk i r k m a nt r i p l es y s t e m sl k t s ( v ) ，w h i c hi st h ef i r s tl a r g es e tp r o b l e mo nc o m b i n a m d a l d e s i g l l s b u t , t h er e s e a r c hf o rl k t s ( v ) i sf a rf r o mi t sb e i n gs o l v e dc o m p l e t e l y , d u et oi t sh i g h d i f f i c u l t y i n1 9 9 1 ，m j s h a r r ya n da p s t r e e ti n t r o d u c e dt h eo o n c e p 【o v e d a r g es e ta n dc o m p l e t e d t h ee x i s t e n c es p e c t r u mf o ro l s t s ( v ) 。o v e r l a r g es e to fs t s ( v ) f o l l o w i n gi t , o v e r l a r g es e t so f m t s ( v ) ( d t s ( v ) ) a n do v e r l a r g es e t so fs o m es p e c i a lg r a p hd e s i g n sh a v eb e e nm s e a r c b e d b u t u pt on o w , t h er e s u l ta b o u to l k t s ( v ) i sl e s s i nt h i sd i s s e r t a t i o n ，w ef i r s tg i v eat r i p l i n gc o n s t r u c t i o nf o ro l k t s ( v ) t h e n , i n t r o d u c e an e wr o n c e 肚d l g k s ，g e n e r a l i z e do v e r l a r g es e t so fk i r k m a nt r i p l es y s t e m s ，a n ds h o wt h e r e l a t i o n s h i pb e t w e e nt h en e wc o n c e p ta n do l k t s 扣) n e x t , s o m er e c u r s i v ec o n s t r u c t i o n sf o r o l g k s a r e # v e n ，a n ds o m ef l e we x i s t e n c er e s u l t so fo l k t s ( v ) a r eo b t a i n e d m e a n w h i l e ，w e g i v ea l le f f e c t i v ea p p r o a c hw h i c hc a nb eu s e dt os o l v et h ee x i s t e n c ef o ro l k t s ( v ) c o m p l e t e l y f u r t h e r , w er e s e a r c ht h ee x i s t e n c eo fl k t s ( 6 v + 3 ) v i af ( 3 ，4 ，扣+ 1 ) 2 ) ) a n do l k t s ( 2 v + 1 ) w i t has p e c i a lp r o p e r t ya n dg i v es o m ei n f i n i t ef a m i l i e so fl a r g es e t so fl k t s ( 6 v + 3 ) i n a d d i t i o n , s o m en e wr e s u l t sf o rt h ee x i s t e n c eo fl r m t s ( v ) ，l r d t s ( v ) ，o l r m t s ( v ) a n d o l r d t s ( v ) 批g o t t e n f i n a l ，w ed i s c u s so v e d a r g es e t so f g r a p hd e s i g n sf o rt h eg r a p h s 玛，焉， 瑶，露a n d 乃，a n do b t a i na s e r i e so fn e wr e s u l t s k e yw o r d s ：k i r k m a nt r i p l es y s t e m s 。l a r g es e t s 。o v e d a r g es e t s ，g e n e r a l i z e do v e r l a r g es e t so fl 【i r k - m a l lt r j p l es y s t e m s 。 学位论文原创性声明 本人所提交的学位论文可分解三元系的大集和超大集，是在 导师的指导下，独立进行研究工作所取得的原创性成果。除文中已经 注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰 写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在 文中标明。 本声明的法律后果由本人承担。 论文作者( 签名) ：私乞 少) 年月7 日 | 学位论文原创性确认书 学生重兰堂所提交的学位论文司分解三兀系的大集和超大 集，是在本人的指导下，由其独立进行研究工作所取得的原创性成 果。除文中已经注明引用的内容外，该论文不包含任何其他个人或集 体已经发表或撰写过的研究成果。 指导剥币。签鼽腺启恧 1 年p 月，日 | 河北师范大学博士学位论文 l l 引言 1 1 研究背景 s t e i n e r 三元系s t s ( v ) 是一个序偶( x ，8 ) ，其中x 是一个口元集t 3 是集合x 上 三元组( 称为区组) 的族，使得x 中每个2 子集均恰出现在1 3 的一个区组中一个 s t s ( v ) = ( x ，b ) 称为是可分解的，即k i r k m a n 三元系k t s ( v ) ，若存在b 的一个分拆 r = t 只 。使得每个毋都是一个平行类( 即x 的一个分拆) 它们的存在性如下( 见 【3 8 。5 l 】) ： 定理l 1 ( 1 ) 存在s t s ( v ) 当且仅当口兰1 ，3 m o d 6 且口3 ； ( 2 ) 存在k t s ( v ) 当且仅当口13 m o d 6 1 8 4 7 年t e k i r k m a n 在【3 8 1 中提出了这样的问题：“1 5 个女学生每天以三人一排 共五排的队形外出散步今要求安排七天的队形使得任意两个人恰好有一天出现在 同一排竹在他和a c a y l e y 分别给出了这个问题的答案后，j ls y l v e s t e r 又提出了进一 步的问题：“请作出1 3 周的散步安排，使得每周的队形方案都满足上面的条件，且任意 三个女生在1 3 周中恰有一天被安排在一排”这就是著名的s y l v c s t e r 女生问题作为 组合设计史上的第一个大集问题，它的一般提法是( 祷女生数1 5 推广为正整数”) ： 若口元集x 的所有3 子集( 三元组) 可分拆为”一2 个族鼠，使碍每个( 五段) 都 是一个k t s ( v ) ，则称t ( x ，鼠) ：1 is 口一2 ，是一个k i r k m a n 三元系大集l k t s ( v ) ， 当时称l k t s ( v ) 为双可分解的完全3 设i t - 上述s y l v e s t e r 女生问题即是求一个 l k t s ( 1 5 ) 直到1 9 7 4 年，r h ed e n n i s t o n 才在1 7 1 中给出了第一个答案：l i ( t s ( 1 5 ) = ( z 1 3 u 口，6 ) ，最) ： z 1 3 ) ，其中既= 6 0 + i m o d l 3 ，而岛由如下的7 个平行类组成( f f 别表示第一周中各天的队形安排) ： l 4 1 0 8 6 9 1 2 1 l 口 b 27 o31 l 48171 2 61 2 681 0 1 l口254 1 0b496 o4 18 29 31 2 57 605 l ll2 1 0 6 7 口41 0 b1 11 2 o1 01 2 3 5 9 471 1 16口 286 5 1 1 1 0 1 2 6 几乎同时。人们也开始提出并研究了比之条件稍弱( 即每个( x ，玩) 改为是- - - i - s t s ( v ) ) 的另一类大集一s t e i n e r 三元系大集l s t s ( v ) 显然，l s t s ( v ) 和l k t s ( v ) 的可能存在 范围分别是 ii ，3 m o d 6 和口i3 m o d 6 1 8 5 0 年。c a y l e y 3 1 证明了不存在l s t s ( 7 ) ，而彼此不交的s t s ( 7 ) 最大个数为2 k i r k m a n 3 9 1 在同年又给出了l s t s o ) ，s y l v e s t e r1 5 8 1 在1 8 9 3 年给出了l k t s ( 3 ”) 的构 2 可分解三元系的大集和超大集 造此后直到二十世纪七十年代，l s t s 和l k t s 的存在性问题几乎毫无进展由1 9 7 2 年开始，d o y e n ( 1 1 1 k o t z i g 4 1 1 等引进了递归方法，d e n n i s t o n 给出了l k t s 的三倍构造 ( 见【9 】j 同时，s s c h r e i b e r 【1 4 1 给出了l k t s ( 3 3 ) 进而，在得到一些无穷类后，d e n n i s t o n 【7 】 1 0 1 ，s c h r e i b e r 【5 3 1 - 1 5 5 】和w i l s o n 6 4 】陆续解决了os2 0 5 的一些阶数而t e i r l i n c k 【6 0 】和r o s a 【5 2 】则分别对于l s t s ( v ) 给出了 一3 u 和u 一2 u + 1 的重要递归方法 但直到1 9 8 0 年为止，l s t s ( v ) 的存在性结果依旧是零散的，距完全解次还很遥 远( 有关研究还可见【5 0 ，6 0 ，1 9 8 3 1 9 8 4 年，j o u r n a lo f c o m b i n a t o r i a lt h e o r y 陆续发表了 陆家羲的六篇论文【4 6 ，4 7 】，基本上完成了l s t s ( v ) 的存在谱而因他不幸早逝遗留的 六个阶数口= 1 4 1 ，2 8 3 ，5 0 1 ，7 8 9 ，1 5 0 1 ，2 3 6 5 则在1 9 9 1 年由t e i r l i n c k 最后完成【5 9 】从而宣 告了历时1 4 0 年之久的s t e i n e r 三元系大集的完全解决，这是组合设计理论上完全解决 的第一个大集系列 另一方面，l k t s ( v ) 研究长时间没有进展的局面在上个世纪末也出现了转机：朱 烈教授的学生张胜元【6 7 】改进了d e n n i s t o n 对于l k t s 如) 给出的三倍构造，去掉了原 有的附加条件：雷建国教授则引入了一些新的概念，给出了几个新的递归构造，从而得 到了新的存在性结果( 见【4 3 1 【4 5 】) ；而季利均博士在3 设计和3 闭包方面的一系列进 展又进一步推动了各类三元系大集的讨论( 见【1 8 1 ) 迄今为止，l s t s ( v ) 和l k t s ( v ) 的已知结果可总结如下： 定理1 2 ( 1 ) 存在l s t s ( v ) 铮v j l ，3 m o d6 口23 ，口7 ； ( 2 ) 存在l k t s ( 3 a 5 b m 矗( 2 1 3 r i + 1 ) 而( 2 冲+ 1 ) ) 。其中 i = l j = l m m = 1 ，1 1 ，1 7 ，3 5 ，4 3 ，6 7 ，9 1 ，1 2 3 u 2 2 1 + 1 2 5 + 1 ：z ，t 0 吼n ，s j 之1 ，b ，p ，q 兰0 ，且b 1 ，m 1 时口+ p + 口2 所谓s t s ( 1 ) 的超大集o l s t s ( v ) 是一个集族 ( x z ，岛) ：z x ) ，其中x 是一 个0 + 1 ) 元集，每个( x 缸) ，玩) 是一个s ? s ( 口) ，而诸玩恰构成x 土全部三元组的 分拆1 9 9 1 年。m j s h a r r y 和a 只s t r e e t 提出了上述概念：并确定了s t s ( v ) 的超大集 o l s t s ( v ) 存在的充要条件( 见1 5 6 1 ) 类似地，k t s ( v ) 的超大集o l k t s ( v ) 是扣+ 1 ) 元集x 上的一个集族 ( x 扛) ，岛) ：。x ，每个( x 扛 ，& ) 是一个k t s ( v ) ，且诸& 亦构成x 上全部三元组的分拆关于超大集的已知结果( 见【3 5 ，5 6 】) 可列如下： 定理1 3 ( 1 ) 存在o l s t s ( v ) 当且仅当口兰i ，3 m o d 6 且口3 ； ( 2 ) 存在o l k t s ( v ) ，其中口= 9 ，4 ”一1 ，2 一严+ 1 ，2 3 1 “+ 1 ，2 1 2 7 ，l + 1 ，n 1 河北师范大学博士学位论文 3 毽x 是一个有限集合以下，有序对( z ，v ) 是集合x 的一个有序2 - 子集。其中 z x 集合x 的循惩三垂丝是一个含三个有序对( 叠) ，( ，z ) 和( z ，z ) 的有向三 元组，记为z ，y ，z ) ( 或白，孑筇，或( 毛毛i ，) ) 集合x 的! 堑三墨丝是一个含三个有序对 ( z ，) ，( y ，z ) 和( ，z ) 的有向三元组，记为( 曩，z ) m e n d e l s o h n ( 或d i r e c t e d ) 三元系m t s ( 口) ( 或d t f l ( v ) ) 是一个序偶僻，嚣) ，其中x 是 一个口元集，b 是集合x 中的循环( 或可迁) 三元组( 称为区组) 的一个族，使得集合x 中的每个有序对恰出现在b 盼一个区组中一个m t s c v ) ( 或d t s ( v ) ) 称为! 坌壁箜， 如果它的区组可以被分拆为平行类，记为r m t s ( v ) ( 或r d t s ( v ) ) 它们的存在性如下： 定理1 4 【2 ，1 5 ，删 ( 1 ) 存在m t s ( v ) 当且仅当口i 0 ，1 m o d3 且口3 ，口6 ； ( 2 ) 存在d t s ( v ) 当且仅当u 0 ，1 m o d3 且u 3 ； ( 3 ) 存在r m t s ( v ) 当且仅当口兰0 m o d3 且口23 ，t ，6 ； ( 4 ) 存在r d t s ( v ) 当且仅当u i o m o d3 且t ，3 m e n d e l s o h n ( 或d i r e c t e d ) 三元系的大集，记为l m t s ( v ) ( 或l d t s ( v ) ) ，是一个集族 ( x ，玩) ) i 其中每个( x ，晚) 是一个m t s ( v ) ( 或d t s ( v ) ) ，而诸岛构成集合x 上所有循 环( 或可迁) 三元组的分拆类似地。可分解的m e n d c l s o h n 【塞里! ! ! 堕! 尘三垄垒箜盘叁，记 为l r m t s 0 ) ( 或l r d t s ( v ) ) ，是一个集族 ( 五鼠) ) t 。其中每个( x ，鼠) 是一个r m t s ( v ) ( 或r d t s ( v ) ) ，而诸甄构成集合x 上所有循环( 或可迁) 三元组的分拆易见，l m t s ( v ) ( 或l r m t s ( v ) ) 含。一2 个不相交的m t s ( v ) ( 或r m t s ( 功) ，而l d t s ( v ) ( 或l a d t s ( v ) ) 含3 ( v 一2 ) 个不相交的d t s ( v ) ( 或r d t s ( v ) ) 关于l m t s ( v ) 和l d t s ( v ) 的存在性问题已由康庆德教授，雷建国教授和常彦勋 教授完全解决( 见【2 3 ，2 5 ，2 6 ，2 7 ，2 8 ，2 9 】等) ： 定理1 5 ( 1 ) 存在l m t s ( v ) 当且仅当t ，；0 ，1m o d3 ，口23 ，口6 ( 2 ) 存在l d t s ( v ) 当且彼当口! o 1 r o o d 3 , 口之3 关于可分解的m e n d e l s o h n ( 或d i r e r , d ) 三元系大集存在性问题的讨论可见【2 4 3 0 ， 3 5 ，7 0 ，7 l ，3 7 ，5 】 已知结果可综述如下： 定理1 6 存在l r m t s ( v ) 和l r d t s ( v ) , 这里 ( 1 ) 口= 3 巩其中1 且m ( 1 ，4 ，5 ，7 ，1 1 ，1 3 ，1 7 ，2 3 ，2 5 ，3 5 ，3 7 ，4 1 ，4 3 ，4 7 ，5 3 ，5 5 ，5 7 ，6 1 ， 6 5 ，6 7 ，9 1 ，1 2 3 l , j ( 7 5 + 2 ) 3 ，( 1 3 。1 + 2 ) 3 ，( 2 5 。2 + 2 ) 3 ，2 甜+ 1 2 驴+ 1 ：矗，8 1 ，8 2 ，t ，歹o ，； 4 可分解三元系的大集和超大集 ( 2 ) 妒；2 4 + 2 ，2 6 + 2 ，其中奄20 ； ( 3 ) v = 1 2 ( t + 1 ) ，其中t o ，1 ，2 ，3 ，4 ，j ，7 ，8 ，9 ，1 4 ，1 6 ，1 8 ，2 0 ，2 2 ，2 4 ，2 8 ，3 2 ( 4 ) ”= 3 ( 2 t + 1 ) ，其中t 3 5 ，3 8 ，4 6 ，4 7 ，4 8 ，5 1 ，5 6 ，6 0 ) m t s ( v ) 的超大集，记为o l m t s ( v ) ，是一个集族 和) ，玩) ：。x ，其中x 是一个扣+ 1 ) 元集，每个扛 ，岛) 是一个m t s ( v ) ，而诸如恰构成集合x 中全部 循环三元组的分拆里三曼! 虫鱼整查叁，记为o l d t s ( v ) ，是一个集族 ( x 扛) ，砭) ：z x ，1 i s3 ，其中x 是一个0 + 1 ) 元集，每个( x 扛 ，砭) 是一个d t s ( v ) ，而诸嘭构 成集合x 中全部可迁三元组的分拆 类似地，r m t s ( v ) 的超大集，记为o l r m t s ( v ) ，是一个集族 僻扛) ，瓯) ：z x ，其中x 是一个扣+ 1 ) 元集，每个( x z ) ，玩) 是一个r m t s ( v ) ，而诸岛构成集 合x 上所有循环三元组的分拆r d t s ( v ) 的超大集，记为o l r d t s ( v ) ，是一个集族 僻 ) ，琏) ：z x ，1 i 3 ，其中x 是一个0 + 1 ) 元集。每个僻和 ，磁) 是一个 r d t s ( v ) ，而诸磁构成集合x 上所有可迁三元组的分拆 关于有向三元系超大集的讨论可见【l ，3 5 ，6 3 ，6 5 ，6 6 已知结果可综述如下： 定理1 7 ( 1 ) 对于以下的阶数”存在o l m t s ( v ) 和o l d t s ( v ) ， 1 。 e 1 ，3 r o o d 6 ，口1 0 ，4 m o d l 2 ，口兰1 0 ，5 4 r o o d l 3 2 ， 2 。 = 7 1 1 1 ”1 3 ”兀( 4 + 1 ) 一1 ，m ，扎，s ，t 0 ，且l = 0 时存在o l m t s ( v ) ， 0 ，t f 0 时存在o l d t s ( v ) ， 3 。钉= 3 4 2 5 ”+ 4 k 20 ，f l 1 ) ，钌= 6 3 5 “+ l ( n o ) ； ( 2 ) 对于以下的阶数协存在o l r m t s ( v ) 和o l r d t s ( v ) ， t ，= 9 ，铲一1 ，2 7 l 十1 ，2 3 1 4 + 1 ，2 1 2 p + 1 ，t l 1 a 重 阶完全图a j 0 是一个口点无向图，其任二不同顶点z 和问都恰有a 条无 向边 订相连对于有限简单图g ，所谓的图设计g - g d ( 口) 是一个序偶( x ，b ) 。其中 x 是j 0 的顶点集，尽是与g 同构的一些子图( 称为区组) ，使得中任二不同顶点问 的无向边恰出现在8 的a 个区组中显然，存在g g 以( u ) 的必要条件为： 口2n ，a v ( v 一1 ) 三0 r o o d2 e ，a 扣一1 ) i0 r o o d d ， 其中n ，e 分别表示g 的顶点数和边数，d 表示g 中各顶点度的最大公因数 查重! 堕查鱼窒全里a d k v 是一个”点有向图，其任二不同顶点z 和间都恰有 a 条有向边( z ，) 和a 条有向边( ，。) 相连对于有向简单图d ，所谓的有向图设计d g 仇( ) 是一个序偶( x ，b ) ，其中x 是d j 0 的顶点集，b 是与d 同构的一些子图( 称为 河北师范大学博士学位论文 5 区组) ，使得编中任二不同顶点和p 问的有向边( ，g ) 和( y ，刁均恰出现在b 的a 个 区组中显然，存在d g o ( v ) 的必要条件为： t ，n ，a 移p 1 ) 兰0 r o o de ，a 扣一1 ) 三0 r o o d 扩，a 和一1 ) 兰0 r o o d d 一 其中n ，e 分别表示d 的顶点数和边数。d + 表示d 中各顶点入度的最大公因数，d 一表 示d 中各顶点出度的最大公因数 图设计g g d a ( v ) 的超大集g - o l g d ( v ) 是指口+ 1 元集x 上的a 凰+ l 中所有与 g 同构的子图的一个分拆 罐) ，使得每个俾 ) ，磋) 为一个g - g d ( v ) ( 称为小集) 有向图设计d g d ( v ) 的超大集d - o l g d a ( v ) 是指口+ 1 元集x 上的a d 凰+ l 中 所有与d 同构的子图的一个分拆 磁 使得每个僻 z ) ，磷) 为一个d g 仇( 。) ( 称为 小集) 以下诸图分别是( 无向) 二长链b 和三类有向二长链露，碍与霹 b ：( z ，f ，z ) f 2 ：( z ，口，z ) lf 2 ：( 。，薯，z hp i ：( z ，z ) 3 z 翟 =墨 馨 zz y ；z 譬 茹 其中2 长链忍包含两个无序对p ， 和 ，z ，；而有向2 长链碍包含两个有序对 0 ，们，( z ，) ，瑶包含两个有序对( ，z ，( y ，z ) ，曰包含两个有序对扛，p ) ，白，z ) 它们的 图设计及超大集的己知结果( 见1 3 6 ，6 9 】) 如下： 定理1 8 ( 1 ) 存在p 3 g d ( v ) 当且仅当口e0 ，1 m o d4 口4 ； ( 2 ) 存在p 3 一g d 2 ( ) 当且仅当口4 ； c s ，对于t = ，z 存在焉- g d ( ”，当且仅当 i 主荨：芝主3 ( 4 ) 存在霹g z ) ( ”) 当且仅当”2 & 且口= 3 时，a 为偶数； ( 5 ) 当口为3 的奇数吨存在马o l g d u ( ) 混合三元系是口元集x 上的一些i 型( 型或m 型) 三元组的族鼠使得x 中的 任一个无序对和任一个有序对均恰被包含鹰疗的a 个区组中，e s , i z 为噩一g d ( 口) ， 乃g d x ( v ) 及马一 ( 口) 可yy i 型乃：扛，挈，刁1 无序对伽，z ) 有序对( ”，z ) ，0 ，。) 型乃：k 鲈，2 4 2 无序对t 毛z 有序对( z ，口) ，0 ，p ) o z 型乃：p ，玑卅3 无序对 z ，z ) 有序对( ，) ，0 ，= ) 6可分解三元系的大集和超大集 混合三元系的超大集正一o l g d ( v ) 是指口+ l 元集x 上的a + 1 中所有与正同构 的子图的一个分拆 磁 ，使得每个僻扛) ，磁) 是一个正- g d ( v ) ( 称为小集) i = 1 2 ，3 已知结果如下( 见 1 2 ，6 2 】) ： 定理1 9 ( 1 ) 对于i = 1 ，2 存在正g d ( v ) 当且仅当”i l m o d 2 且”23 ； c z ，存在死g 巩c ”，当且仅当 ：袤薯：羔i 7 ， ( 3 ) 对于i = 1 ，2 ，存在正o l g d ( v ) 当且仅当 i 1m o d 2 ，口3 ； ( 4 ) 存在t 3 一o l g d 2 ( v ) ， 3 ，唯一可能例外的值。= 6 1 2 主要结果 本文将主要讨论o l k t s ( v ) 和l k t s ( v ) 的存在性 第二章中，讨论o l k t s ( v ) 的存在性首先给出了o l k t s ( v ) 的3 倍构适，进 而，引入了一个新概念一广义k i r k m a n 三元系的超大集o l g k s ，给出了这个概念与 o l k t s ( v ) 间的关系以及o l g k s 的递归构造，并得到了o l g k s 的一些结果最后 给出了o l k t s ( v ) 的一些新的存在性结果，并且找到了完全解决这个问题的一条有效 途径 第三章中，利用f ( 3 ，4 ，0 + 1 ) 2 ) ) 和带有一种特殊性质的o l k t s ( 2 v + 1 ) ，进一步 扩大了l k t s ( f v + 3 ) 的存在性结果 第四章中。通过l r m t s ( v ) ，l r d t s ( v ) 与l k t s ( v ) 之间的关系，o l r m t s ( v ) ， o l r d t s ( v ) 与o l k t s ( v ) 之间的关系，得到了有向可分解三元系大集和超大集一些 新的存在性结果 第五章中。对于2 长链p 3 ，有向2 长链聪，砖，露和混合三元系乃，讨论了图设计 的超大集，得到了一系列结果 全文得到的主要结果是： a 对以下的阶数 ，存在o l k t s ( v ) ，o l r m t s ( v ) 和o l r d t s ( v ) ： ( 1 ) 口= 6 “+ 3 ，其中知1 ，“= 4 “2 5 m ，m + n l ； ( 2 ) 口= 2 - 1 3 ”+ 1 ，其中，l 0 ； ( 3 ) t = 驴n ( 2 q r + 1 ) 1 3 一1 ) ，其中k o ，r ，5 2 1 ，q = 1 2 t + 7 ( t o ) 且为素数幂 b 存在l k t s ( v ) ，l r m t s ( v ) 和l r d t s ( v ) ，其中口= 3 1 - i ( 2 q + 1 ) 1 - i ( 4 8 1 ) 。其中 k ，r ，s 2 1 ，q = 1 2 t + 7 ( t 20 ) 且为素数幂 河北师范大学博士学位论文 7 c 若对每个( 6 ，7 ，4 0 i 8 ，1 7 , 2 1 ，2 2 ，2 5 ，2 6 ，3 2 。存在o l k f ( 6 ) 和3 - o l g k s ( 6 k - 14 ) ，则存在o l k t s ( v ) ，口i3 m o d6 口2 1 d ( 1 ) 存在p 3 一o l g d ( v ) ，口= 5 k , ( 4 5 n + 坐产) 且k l , 自20 ，n 2 i ( 2 ) 存在p 3 一o l g d 2 ( 口) ， 兰0 ，1 ，3 m o d 4 且口3 e ( 1 ) 对于i = 1 ，2 ，存在只- o l g d ( v ) ，其中口 1 m o d 2 且口3 ( 2 ) 存在碍- o l g d 2 ( v ) ，口苦o ，1 ，3 m o d 4 且口23 r 存在t a - o l g d ( v ) ，v = 7 t i ，9 “，t i 1 8 可分解三元系的大集和超大集 2 1 基本概念 2 柯克曼三元系的超大集 ! 坌丝亟! g d d ( t ，k ，蛾r 1 m 1 ，n m ，) ) 是一个( x ，分，层) ，其中t ，u 和诸n ，m i 均为正整数，k 为t 的一些正整数的集合，壹r 。m i ：奶x 是一个口元点集，且 i = i 1 ) 岔是x 的一个分拆，分拆为n 个帆元子集( 称为组) 1 i ss ； 2 ) 8 是x 的子集( 称为区组) 的族，满足i b n gj 1 ，v b b 和g 蛋： 3 ) x 的任意t 元子集t ( 1 t n g i 1 ，y g g ) 恰含于一个区组中 通常。可书g d d ( t , j t t ，；r l m 1 ) ，珞 m ，) ) 记为( ，耳) g d d ( m ：1 m r ) ，而当m l = = m 。= m 且口= m u 时，则简记为( t ，k ) - g d d ( m “) 特别，当t = 2 时( ，) 可 简记为耳、当k = 伽) 时，( 2 ，k ) - 可简记为k 、称k - g d d ( m 。) 为横截设计t d ( k , m ) 。 而可分解的可分组设计( 横截设计) ，记为r g d d ( r t d ) ，指的是其区组集可分拆为点 集上若干平行类的g d d ( t d ) ! ：堡2 旦i 鲨) 箜叁叁! ：墨堡2 望i 竺= = 2 是同一点集和同一组集合上若干个- g d d ( m ) 的一个集族 ( x ，9 ，岛) ) ，r ，使得x 的任一元子集b ( i b a g i 1 ，v g 彩都恰出现 在某个耳中容易验证，i 引= ( ：二；) m 扣2 类似可以定5 l r g d d ( m ”) 和l r t d ( k , m ) 引理2 1 1 8 1 存在l r t d ( 3 , m ) ，其中m 3 ，m 6 例2 2 集合x = 历忍上以量= 磅历：i 历) 为组集合的 l r t d ( 3 3 ) = ( x ，玩c ( ) ) ：女历) ， 其中c ( 动= ( o ，o ) ，( 1 ，( 2 ，c ) ：8 + 6 + cekm o d3 ，局z 3 容易验证每个 ( x ，g ，c ( ) ) 都是一个r r m ( 3 ，3 ) ，z 3 显然，它们互不相交 称( t ，耳) - g d d ( i ”) = ( x ，g ，且) 为盟鱼玉! 堂。记为s ( f ，k , v ) = ( x ，b ) 而s ( 2 ，k t ，) 称为叁苎堑堡盐，s ( t ， ) ， ) 称为s t e i n e r $ , , 并且简记为s ( t ， ) s ( 2 ，3 ， ) 即是 s t e i n e r 三元系s t s ( v ) ，而s ( 3 ，4 ，口) 称为s t e i n e r 四元系s q s ( v ) 如果一个s e s ( 川i = 僻，b ) 的区组集嚣可被分拆为8 l ，玩，8 ：摹，使得每个( x ，岛) 都是一个s ( 2 ，4 ，口) ，1 s i 与2 ，则称该s q s ( 口) 为2 - 可分的 引理2 3 嗣设口是素数幂 ( 1 ) 存在s ( 3 ，5 ，2 6 ) ； ( 2 ) 存在s ( 3 ，q + l ，g ”+ 1 ) 其中n 2 1 ； 河北师范大学博士学位论文 9 ( 3 ) 若存在s ( 3 ，口+ 1 ，口+ 1 ) 和s ( 3 ，口+ 1 ， + 1 ) 则存在s ( 3 ，口+ l ，口 + 1 ) ( 4 ) 若存在s ( 3 ，6 ， + 1 ) ，则存在s ( 3 ，6 ，4 v + 2 ) ； ( 5 ) 存在s ( 3 ，k ) ，其中。25 且k = 5 ，6 ，4 0 i 7 ，2 1 ，2 2 ，2 5 ，2 6 ； ( 6 ) 对于t ，i0 ，1 ，3 m o d 4 ，口8 ，1 2 , 存在s ( 3 ， 4 ，5 ，6 ，口+ 1 ) ； ( 7 ) 对于t ，1 m o d2 存在s ( 3 ， 4 ，6 ，t ，+ 1 ) 引理“1 3 5 6 1 l ( 1 ) 若存在2 可分的s q s ( v + 1 ) 则 3 m o d l 2 ； ( 2 ) 存在2 可分的s q s ( v + 1 ) ，口= 4 n 一1 ，2 p + l ，2 3 1 ”+ 1 ，2 1 2 严+ 1 且n l ； ( 3 ) 若存在2 可分的s ( 3 ，4 ，v + 1 ) ，则存在o l k t s ( v ) 为了应用可分解条件。文0 4 3 】中引进了一类带有广义可分解性的设计m r s ( 蜀”) ， 它是一个满足以下条件的s ( 2 ，k ) = ( x ，b ) ： 1 ) 宦中存在一组平行类r m - f p l ，忍，最，每个只是集合x 的一个分拆， 2 ) 4 4 b b 恰出现在半个最中， 3 ) r 中所有只的并恰是b 显然，在m r s ( k ， ) 中。k 的元必为大于l 的奇数。而m r s ( 3 ，口) 即是一个k t s ( v ) 设k 3 ，m r s ( 3 ，k + ，表示其中仅有唯一的k 长区组易见，m r s ( 3 ，k ，计含 一个长区组和( ( ；) 一( ! ) ) 3 个三元组特别，m r s ( 3 ，9 ，”) 所含三元组的个数是 【竺= 1 2 f ! 盟 6 例2 5 一个m r s ( 3 ，9 ，2 7 ) 设岛，8 1 ，玩和玩是集合x 上k t s ( 9 ) 的四个平行类，其中b 3 = 历，易，岛 今对每个区组b 玩 局 构作- - 4 k t s ( 9 ) = ( b z 3 ，a b ) ，它的四个平行类为 4 日( o ) ，4 口( 1 ) ，4 b ( 2 ) 和4 b ( 3 ) ；而对每个区组b u 既，构作一个r t d ( 3 ，3 ) = ( bx 忍， 如，x 忍：霉b ) ，白) ，如的三个平行类记为白( 0 ) ，白( 1 ) 和( 2 ) 定义 ，= (u4 日) u (uc 丑) ) u e ixz 3 b 岛 e l b b o u 8 1 u 岛 则( x 历，刁是一个m r s ( 3 ，9 ) ，2 7 ) ，它含有1 0 5 个三元组和一个9 长区组事实上 不难验证， ，= ( u 只j ) u ( uq k ) ， 而每个最j = u 和仉= (u4 b ( ) ) u 毋历) 都是集合x z 3 的分拆 1 0 可分解三元系的大集和超大集 引理2 6f 4 3 1 如果存在m r s ( k , u ) ，且对每个k i f , 存在k t s ( k ) ，则存在k t s ( u ) 广义的f r a m ef c t ，自， m ) ) ( 见 6 1 1 ) 是一个( t ，) 一g d d ( m ”) = ( x ，毋，ub r ) ，其中 x 是一个口m 元集，g 是x 分拆为口个m 元集( 称为组) 的一个分拆。且 1 ) v g 口，( x g ，吼 研，砗) 是一个( t 一1 ，) - g d d ( m ”- * ) ； 2 ) 所有的舀，r r ，互不相交 经计算可知，f ( t ， m ) ) 含不v m 雨个( t l ，k ) 一g d d ( ”，- 1 ) ，即l r l = i 兰记r g = p r ：睇的组集合为吼 g ) ) ，则i r o i = 南 例2 7f ( 3 ，3 ，4 3 ) ：设a 是一个4 元集对口t a 磊，定义 b ( a k ) = ( 以，协，) ： 而玑。) = a o ) ，i 十j + t 三七r o o d 3 ) 显 2 ，每个8 ( ) 是集合似( 8 ) 忍上以“j x z 3 ：8 扯 口) 为组集合的r t d ( 3 ，3 ) 则( a 历，“。 z 3 ：口a ) ，u 8 ( 啦) ：n a ，k z 3 ) 是一个f ( 3 ，3 ，4 3 ) ) 这个 f ( 3 ，3 ，4 3 ) ) 含1 2 个r t d ( 3 ，3 ) 一个f ( 2 ，3 ， m ) ) 称为k i r k m a nf r a m e , 简记为k f ( 仃，) 称其中的每个( 1 ，3 ) 一g d d ( m ”1 ) 为部分平行类( 或带洞平行类) ，它恰是集合x o 的分拆，g 9 例2 8 f ( 6 4 ) ：首先。在集合z 4x z 2 上构作以 计x 历：i 磊 为组集合的k f ( 2 4 ) ， 其区组集为a = ua ，其