（应用数学专业论文）拟kirkman三元系嵌入问题的研究.pdf

上海交通大学博士学位论文 拟k i r k m a n 三元系嵌入问题的研究 摘要 f 嵌入问题是组合设计理论中的基本问题。自1 9 7 3 年d o y e n 与w i l s o n 关于 s t e r n e r 三元系嵌入问题的著名论文以来，国内外许多学者在这方面已经做了大 本文将系统研究一类重要的可分解设计一拟k i r k m a n 三元系的嵌入问题，先 1 ) g 构成的一个划分，且对任意g g ，有i g j e m ， 2 ) 对任意b b ，有例k ， 3 ) 对任意b b ，g g 有陋n g i 1 ， 4 ) x 中任意一对属于不同组的元素都包含在唯一的一个区组中， 则称( ，g ，b ) 为一个可分组设计，记为g d ( k ， ，m ；o ，当k = k ) ，且m = m ) 时， 通常将g d ( 弘) ，沏) ；v ) 记作g d ( k ，m ；v ) 并称为均匀可分组设计。 设( 爿，g ，b ) 为一个g d ( k ，肘；v ) 。p c b 。如果x 中每一点都恰好包含在p 的 分为平行类，则称该g d 设计为可分解的并记为r g d ( k ，m ；y ) 。称r g d ( 3 ，3 ；v ) 为 k i r k m a n 三元系并记作k t s ( v ) ，称r g d ( 3 ，2 ；v ) 为拟k i r 胁t a n 三元系并记作 上海交通大学博士学位论文 设( x ，g ，a ) 为一个r g d ( k ，m ；v ) 且( y ，h ，b ) 是一个r g d ( k ，m ；u ) 。如果满 足x c y ，g c h ，且a 中的每一个平行类都是b 中某个平行类的一部分，则 称( x ，g ，a ) 嵌入于( y ，h ，b ) ，或( y ，h ，b ) 包含( x ，g ，a ) 为子设计。关于k ： 3 ) 的r g d 的嵌入问题，有两种情形特别重要，其一即是k i r k m a n 三元系的嵌入问 题，这一问题已由r r e e s 与d r s t i n s o n 所解决：其二即拟k i r k m a n 三元系的 嵌入问题，该问题的研究处于起步阶段。可以说，这两种情形嵌入问题的解决是 研究一般情形下k = 3 ) 的r g d 设计的嵌入问题的基础。 关于拟k i r k m a n 三元系的嵌入问题，原先仅有如下结果：v ；”z0 ( m o d 6 1 且 “4 v ，v 2 1 0 2 时，存在某个n k t s ( u ) 包含一个n k t s ( v ) 为子设计。而这一问题 ，一 的必要条件为v “e 0 ( m o d 6 ) ，u 3 v ，且v 1 8 。7 。 本文分为八章。第一章介绍了有关概念及相应的嵌入问题的背景及研究结 果。 第二章介绍研究可分解设计特别是拟k i r k m a n 三元系的嵌入问题的一般性 构造原则与构造方法。 在第三章中我们构造了相关的g d 设计及鼢，概d n f r a m e ，为我们具体研究 拟k i r k m a n 三元系嵌入问题提供了有力的工具。 厂 胙为研究拟k i r k m a n 三元系嵌入问题的第一步，我们在第四章中完全解决了 带一个大小为6 或1 2 的洞的拟k i r k m a n 三元系即i n k t s ( u ，6 ) 与1 n k t s ( u ，1 2 ) 的存 在性问题。 第五章我们利用第二章所述的构造方法并结合一系列直接构造完全解决了 v 7 2 时，n k t s ( v ) 的嵌入问题，并对v 7 8 时的情形进行了讨论。 第六章我们讨论了拟k i r k m a n 三元系的最大嵌入问题，除1 4 个可能的例外， 我们完全解决了这一问题。 在第七章中我们综合运用各种递归构造方法并给出进一步的直接构造证明 了本文主要结论f 小 定理除最多4 0 个可能的例外，任一n k t s ( v ) 可嵌入于某个n k t s ( u ) 的充分必要 圭塑銮望查堂堕主兰壁垒兰 条件为v = “；0 ( m o d 6 ) ，“3 v ，v 1 8 。r 一厂一 关键词：可分解设计，- e l q z q # i 尹嵌入，t g k i r k m a n 三元系? k i r k m a n 妒d m e 7 i l l 圭塑銮望奎堂堕主兰堡垒壅 e m b e d d i n gp r o b l e m f o rn e a r l yk i rkma n t r i p l es y s t e m s a b s t r a c t t h ee m b e d d i n gp r o b l e mi so n eo ft h ef u n d a m e n t a la n di m p o r t a n tp r o b l e m si n d e s i g nt h e o r y m a n yb e a u t i f u lr e s u l t sh a v eb e e ng o ts i n c e1 9 7 3 ，w h e nd o y e na n d w i l s o ns o l v e dt h ee m b e d d i n g p r o b l e m f o rs t e i n e r t r i p l es y s t e m s i nt h i s p a p e r , w es t u d y t h e e m b e d d i n gp r o b l e m f o ra s p e c i a l r e s o l v a b l e d e s i g n - - t h ee m b e d d i n gp r o b l e m f o rn e a r l yk i r k m a n t r i p l es y s t e m s l e tvb ea p o s i t i v ei n t e g e r , ka n dm b et w os e t so f p o s i t i v ei n t e g e r s ag r o u p d i v i s i b l ed e s i g ng d ( k ，m ；v ) i sa l lo r d e r e dt r i p l e ( x ，g ，b ) w h e r exi sas e tw i t h c a r d i n a l i t yv gi sa s e to f s u b s e t s ( c a l l e dg r o u p s ) o f xs u c ht h a tg p a r t i t i o n sx a n di g i mf o re a c hg g ，a n dbi sas e to f s u b s e t s ( c a l l e db l o c k s ) o f xs u c ht h a t b i k f o re a c hb b w i t ht h ep r o p e r t yt h a te a c h p a i ro f d i s t i n c te l e m e n t so fxi sc o n t m n e d e i t h e ri nau n i q u eg r o u po ri nau n i q u eb l o c k ，b u tn o tb o t h t h en u m b e rvi sc a l l e dt h e o r d e ro ft h eg r o u pd i v i s i b l ed e s i g n 、 h e nk = k ) a n d m = m ) ，w es a yt h a tt h eg r o u p d i v i s i b l ed e s i g ni su n i f o r ma n dd e n o t e d g d o ( ，m ；v ) l e t ( x ，g ，b ) b eag d ( k ，m ；v ) a n dp 亡b i f pp a r t i t i o n sx ，t h e nw es a yt h a tp i sa p a r a l l e lc l a s s i f a l lt h eb l o c k si nbc a r l b ed i v i d e di n t op a r a l l e lc l a s s e s ，t h e nw ec a l l ( x ，g ，b ) ar e s o l v a b l eg r o u pd i v i s i b l ed e s i g n a n dd e n o t e dr g d ( k ，m ；v ) w ec a l l r g d ( 3 ，3 ；v ) ak i r k m a nt r i p l es y s t e ma n dd e n o t e dk t s ( v ) w ec a l lr g d ( 3 ，2 ；v ) a n e a r l yk i r k m a nt r i p l es y s t e ma n d d e n o t e d n k t s ( v ) n o wl e t ( y h ，a ) b ea nr g d k ，m ；u 】a n d ( x ，g b ) b ea nr g d k ，m ；v i fyc x ， a c b a n d e a c h p a r a l l e lc l a s s o f a i sa p a r t o f s o m e p a r a l l e lc l a s so f b ，t h e n ( 1 l h ，a ) i s s a i dt oe m b e d d e di n ( x ，g b ) ，o r ( y h ，a ) i sas u b d e s i g no f ( x ，g b ) w h e nk = 3 ，w e g e tt w os p e c i a l a n di m p o r t a n tc a s e s ，t h a ti s ，t h ee m b e d d i n gp r o b l e mf o rk i r k m a n t r i p l es y s t e m sa n dt h ee m b e d d i n gp r o b l e mf o rn e a r l yk i r k m a nt r i p l es y s t e m s a st o i v 上海交通大学博士学位论文 t h ef o r m e ro n e ，i th a sb e e nc o m p l e t e l ys o l v e db yr e e sa n ds t i n s o n b u to n l yl i m i t e d r e s u l th a sb e e ng o tf o rt h el a t e rc a s e i tc a nw e l lb es a i dt h a tt h e s et w os p e c i a lc a s e s a r ct h eb a s ef o ru st o s t u d yt h eg e n e r a l c a s eo ft h ee m b e d d i n gp r o b l e mf o r r g d ( 3 ，m ；”， f o rt h ee m b e d d i n gp r o b l e mo fn e a r l yk i r k m a nt r i p l e s y s t e m ，t h eo n l yr e s u l t k n o w nw a s ：t h e s ee x i s t sa l l n k t s ( u ) c o n t a i n i n g a l l n k t s ( v 、w h e n uiv 5 0 ( m o d 6 ) ，u 4 va n dv 1 0 2 b u tt h en e c e s s a r yc o n d i t i o nf o rt h i sp r o b l e mi s ：u 三v 三 0 ( m o d 6 ) u 3 va n d v 1 8 t h i sp a p e rc o n s i s t so f s e v e nc h a p t e r s i nc h a p t e ro n e , w e b r i e f l yi n t r o d u c es o m e t y p e so fd e s i g n sa n d r e l a t e de m b e d d i n g p r o b l e m sa n d r e s u l t s i n c h a p t e rt w o ，w ep r e s e n t s o m e g e n e r a lc o n s t r u c t i o n m e t h o d sf o r n e a r l y k i r k m a n t r i p l es y s t e m sw i t hs u b s y s t e m s i nc h a p t e rt h r e e ，w ec o n s t r u c ts o m e t y p e so f g d d sa n dk i r k m a n f r a m e s ，w h i c h i su s e di nt h el a t e rc h a p t e r sf o rt h ec o n s t r u c t i o no f n e a r l yk i r k m a n t r i p l es y s t e m sw i t h s u b s y s t e m s a so u rf i r s t s t e p ，w ec o m p l e t e l ys o l v et h ee x i s t e n c ep r o b l e mo fn e a r l yk i r k m a n t r i p l es y s t e m sw i t h ah o l eo f s i z e6o r1 2i nc h a p t e rf o u r i nc h a p t e rf i v e ，w ec o m p l e t e l ys o l v et h ee x i s t e n c e p r o b l e mo fi n k t s ( u ，v ) ，w h e n vs7 2 w ea l s od i s c u s st h e p r o b l e mw h e n v _ - 27 8 i nc h a p t e rs i x ，w ed i s c u s st h em a x i m u m e m b e d d i n g sf o rn e a r l yk i r k m a nt r i p l e 。 s y s t e m s ，w i t ha tm o s t1 4p o s s i b l ee x c e p t i o n s ，w ec o m p l e t e l ys o l v et h i sp r o b l e m i nc h a p t e rs e v e n ，w e g e to u rp r i m a r yr e s u l tb yi n d u c t i v ea n dd i r e c tc o n s t r u c t i o n s ： t h e o r e m ：w i t ha tm o s t4 0p o s s i b l ee x c e p t i o n s ，t h e r ee x i s t sa nn k t s ( u ) c o n t a i n i n g a nn k t s ( v ) i f a n d o n l yi f u 三v 三o ( m o d 6 ) ，u 3 va n dv 1 8 k e y w o r d s ：r e s o l v a b l ed e s i g n ，g r o u pd i v i s i b l ed e s i g n e m b e d d i n g , n e a r l yk i r k m a n t r i p l es y s t e m ，k i r k m a n f r a m e v 上海交通大学博士学位论文 第一章引论 1 1 嵌入问题及相关概念介绍 组合设计是离散数学的个重要分支，它在统计学，计算机科学，信息论等 学科有着广泛应用。组合设计理论研究设计的存在性，设计的同构分类及计数， 可分解性及嵌入等问题。本文主要研究一类特殊的可分解设计的嵌入问题一拟 k i r k m a n 三元系的嵌入问题。下面先介绍一些相关概念。 设v 是给定的正整数，k 与m 为给定的正整数集合。设( x ，g b ) 为有序三元 组，其中x 为一个v 元集，g 构成x 的一个划分。b 的元素称为区组，g 的元素 称为组。若下述条件满足： 1 ) 对任意b b ，有五， 2 ) 对任意g g ，有蚓e m ， 3 ) 对任意b b ，g g 有p n g i l ， 4 ) x 中任意一对属于不同组的元素都包含在唯一的一个区组中， 则称( 膏，g ，b ) 为一个可分组设计，记为g d ( k ，m ；v ) 。 当k = 女) ，m = 伽) 时，记( ，仰 ；v ) 为g d ( k ，m ；v ) ，并称其为均匀可分组 设计。对一个g d ( k ，r e ；v ) ，如果有v = i o n ，则称该均匀可分组设计为横截设计，记 为t d ( k ，m ) 。t d ( k ，m ) 的存在性等价于k 一2 个互相正交的肼阶拉丁方的存在性。 对一个g d ( k ，m ；v ) ，易知包含任一给定点的区组数为r = ( v m ) ( k 一1 ) ，区 组总数b = v ( v m ) k ( k 一1 ) ，又由于共有v m 个组且任一区组中不能包含两个同 组的点，故有v = 0 ( m o d m ) 且v k m 。当k = 3 与4 时，均匀g d 设计的存在性问题 已完全解决。 l 圭塑奎望查堂苎主堂焦丝兰一 定理1 1 2 9 当k = 3 时，g d ( 3 ，r e ；v ) 存在的充分必要条件为 ( v m ) ；0 ( m o d 2 ) v ( v 一用) ；0 ( r o o d 6 ) v 0 ( m o d m ) ，v 3 m 定理1 2 6 当k = 4 时，g d ( 4 , m ；v ) 存在的充分必要条件为 ( v m ) ；0 ( r o o d 3 ) v ( v m ) = o ( m o d l 2 ) v 0 ( m o d m ) v 4 m 对一个g d ( k ，m ；v ) ，如果有m = 1 ) ，则称该设计为成对平衡设计( p b d ) 。 当k = m 时的成对平衡设计即为s t e i n e r 设计并记为s ( 2 ，i ；v ) 或b ( k ，l ；v ) 。 不难验证，如果一个s ( 2 ，；v ) 存在，则包含任一给定点的区组个数 r = ( v t ) ( k 1 ) ，区组总数b = v ( v d k ( k 一1 ) 。 组合设计的存在性问题是组合设计理论中第一个基本问题。对于女5 的情 形，h a n a n i 于1 9 7 5 年发表的重要论文给出了s ( 2 ，女；v ) 存在性问题的完整解答， 即有如下定理： 定理1 3 2 9 设v - k 为正整数。对任意k ，k 5 ，s ( 2 ，女；v ) 存在的充分必要条件 为 v 一1 ；0 ( m o d k 一1 ) ，v ( v 1 ) ；0 ( m o d k ( k 一1 ) ) 对于一般情形下计s t e i n e r 系的存在性问题，w i l s o n 于1 9 7 5 年证明了下述重 要的“渐近存在性定理”： 上海交通大学博士学位论文 定理i 4 7 7 给定正整数女，存在常数y 。= v 。( 七) ，使当v v 。时，s ( 2 ，屯v ) 存在的 必要条件v 一1 ；o ( m o d k 一1 ) ，v ( v 一1 ) zo ( m o d k ( k 一1 ) ) 也是充分的。 设( x ，g ，b ) 为一个g d ( k ，m ；o 。p c b 。如果x 中每一点都恰好包含在p 的 一个区组中，则称p 为该g d 设计的一个平行类。如果该g d 设计的所有区组能划 分为平行类，则称该g d 设计为可分解的并记为r g d ( k ，m ；o 。当k = t ) ，m = f 1 ) 时，我们称该g d 设计为可分解的s t e i n e r 系，又称k i r k m a n 系，记为船( t ，1 ；0 。 显然，如果存在一个肿( ，l ；v ) ，则除了须满足前述s t e i n e r 系存在的必要条件外， 还需要满足条件v ；o ( m o d k ) 。 通常称助f 3 ，l ；o 为v 阶的k i r k m a n 三元系，记作k t s ( v ) 。k t s ( v ) 的存在性问题， 也即历史上著名的k i r k m a n 女生问题，经过一百多年的研究，得到完满解决，有 如下著名定理。 - 定理1 5 ( 3 4 】 4 2 】) ( r a y - c h a u d h u r i w i l s o n - l u 定理) k t s ( v ) 存在的充分必要条件 是 v i 3 ( r o o d 们 关于k = 4 , 5 时的衄( 女，1 ；0 的存在性问题，我们有如下结果。 定理1 6 【2 7 】彻( 4 ，l ；v ) 存在的充分必要条件是 vi 4 ( r o o d l 2 ) 定理1 7 1 1 1 2 1 1 1 9 1 1 3 9 1 除去5 个可能的例外，p , b ( 5 ，1 ；v ) 存在的充分必要条件是 v i 5 ( r o o d 2 0 ) 我们称r g d ( 3 ，2 ；v ) 为v 阶的拟k i r k m a n 三元系，记为n k t s ( v ) 。对n k t s ( v ) 的 存在性问题，有如下结果。 定理1 8 ( 4 7 3 3 4 7 ) n k t s ( v ) 存在的充分必要条件为 上海交通大学博士学位论文 v o ( m o d 6 ) v 1 8 下面我们介绍相应的嵌入问题。 设( ，g ，4 ) 为一个g d ( k ，m ；v ) 且( y ，h ，b ) 为个g d ( k ，m ；“) 。如果满足c y g c 日，那么我们说，g ，爿) 嵌入于( y ，h ，b ) ，或( 】，h ，b ) 包含( z ，g ，爿) 为子设计。 作为g d 设计的特殊情形，我们得到s t e i n e r 系的嵌入的概念。 设( x ，爿) 和( r ，b ) 为两个s t e i n e r 系，如果有x c y 且a c b ，那么我们说设计 ( j ，一) 嵌入到设计( j ，b ) 中，或者说( y ，b ) 包含( j ，爿) 为子设计。如果存在一个 s ( 2 ，；“) 包含s ( 2 ，；v ) 为子设计，我们任取一个点x c x y ，因为x 必须和y 中任 意点相遇一次，且子设计中点对只能在子设计的区组中相遇，因此我们不难得到 u ( 女一o v + 1 这一必要条件。综合s t e i n e r 设计自身的存在性条件，我们得到个 s ( 2 ，女；v ) 包含于某个s ( 2 ，t ；“) 的必要条件如下： 1 1 , 一1 iv 一1 ；0 ( m o d k 一1 、 u ( u 一1 ) ；v ( v 一1 ) ；0 ( m o d k ( k 1 ) )( 1 ) “( 一1 ) + 1 嵌入问题本身是组合设计理论中一个基本问题。国内外许多学者在这方面已 经做了大量工作，并且得到了不少漂亮的结果。另外，嵌入思想为构作具有某些 特定性质的设计提供了一个有力的方法，因此它在研究不可约设计的存在性，设 计的支撑数及相交数等问题起着重要作用。 d o y e n 和w i l s o n 于1 9 7 3 年解决了s t e i n e r 三元系的嵌入问题，他们的工作是 研究嵌入问题的开创性工作。 定理1 9 1 8 】一个s ( 2 ，3 ；v ) 包含于某个s ( 2 ，3 ；“) 的充分必要条件为 u ，v ；1 或3 ( m o d 6 ) ，“2 v 十1 s t e r n 和l e n z 6 1 对定理1 9 给出了一个非常简洁巧妙的证明。 b r o u w e r 和l e n z 最先开始了t = 4 的情形的研究，我国学者朱烈及魏瑞中对 4 这一问题做出了重要贡献。经过多名学者多年的共同努力，这一问题也得到了完 满的解决： 定理1 1 0 ( 【6 9 【7 0 【5 0 】) 一个s ( 2 一；v ) 包含于某个s ( 2 ，4 ；“) 的充分必要条件为 “，v 1 或4 ( m o d l 2 ) ，“3 v + 1 下面给出几类可分解条件设计的嵌入问题的定义。 设( x ，爿) 和( y ，口) 为两个可分解的s t e i n e r 系，如果有x c y 且a c b 并且对 ( ，爿) 的任一平行类p i ，必有( y ，b ) 的平行类厅，使p i p j ，则称( 爿，4 ) 嵌入于 ( y ，b ) 。k = 3 时，也即k i r k m a n 三元系的嵌入问题，经过r e e s 和s t i n s o n 近两年 的研究，已完全解决： 定理1 1 l ( 4 8 4 9 】 5 1 6 4 ) 一个k 弼( v ) 包含于某个k t s ( u ) 为子设计的充分必要条 件为： v i u = 3 ( m o d 6 ) u 3 v 蔡天文最早开始艘( 4 ，1 ；v ) 的嵌入问题的研究并得到如下结果： 定理1 1 2 ( 8 ) 当“= v ；4 ( m o d l 2 ) 且“5 v 一1 6 0 ，v 3 0 6 时，任意一个胎( 4 ，1 ；v ) 都可 嵌入于某个r b ( 4 , 1 ；u ) 。 设( ，g ，爿) 为一个r g d ( k ，m ；v ) 且( y ，h ，b ) 是一个r g d ( k ，肘；“) 。如果满足 x c y ，g c h 且a 中的每一个平行类都是b 中某个平行类的一部分，那么我们 说( ，g ，爿) 嵌入于( y ，日，曰) ，或( y ，h ，b ) 包含( ，g ，爿) 为子设计。关于k = 3 的r g d 设计的嵌入问题，有两类非常重要的情况，一类是已经解决了的m = 1 ) 的情形即 k i r k m a n 三元系的嵌入问题，另一类是m = 2 ) 的情形即拟k i r k m a n 三元系的嵌入 问题，该问题开始于沈灏及唐胜的研究 6 8 。可以说，这两种特殊情况嵌入问题 的研究是研究一般情况下k = 3 ) 的r g d 设计的嵌入问题的基础。 上海交通大学博士学位论文 显然，如果存在一个n k t s ( v ) 包含于某个n k t s ( u ) ，则须满足 v ；“；o ( m o d 6 ) ，v 1 8 ，另外，由于子设计中的任意两点只能在子设计的区组中相 遇，再加上平行条件，我们不难得出“3 v 这一必要条件。 关于拟k i r k m a n 三元系的嵌入问题，仅有如下结果。 定理1 1 3 ( 6 7 ) 设v s “o ( m o d 6 ) ，且“4 v ，v 1 0 2 ，则任一n k t s ( v ) 都可以嵌 入于某个n k r s ( ) 。 本文将进一步研究拟k i r l o n a n 三元系的嵌入问题。 1 2 本文主要内容 为了研究拟k i r k m a n 三元系的嵌入问题，我们在第二章介绍研究可分解设计 特别是拟k i r k m a n 三元系的嵌入问题的一般性构造原则与构造方法。然后，在第 三章中通过构造相关的g d 设计，我们得到了对本文研究特别有用的一系列 k i r k m a nf r a m e ，这为我们具体研究拟k i r k m a n 三元系嵌入问题提供了有力的工 具。在接下来的三章中，我们应用递归方法和直接构造证明了下述诸定理： 定理1 1 4 存在1 n k t s ( v ， ) ，h 6 ，1 2 】，当且仅当v = - o ( m o d 6 ) ，v - 3 h 。 定理1 1 5 a ) 设“= v z 0 ( m o d 6 ) ，v 7 8 且“- 3 5 v ，则任一n k t s ( v ) 都可以嵌入于某个 n k t s ( u ) 。 b ) 对v = 1 8 ，2 4 ，3 0 ，3 6 ，4 2 ，4 8 ，5 4 ，6 0 ，6 6 7 2 ，任一n k t s ( v ) 都可以嵌入于某个n k t s ( “) 的充 分必要条件为“；0 ( m o d 6 ) “3 v 。 定理1 6 除去1 6 个可能的例外，对任意给定的v ；o ( m 0 0 6 ) ，v 1 8 ，存在一个 n k t s ( u ) ，u 3 v ，3 v 十6 ，3 v + 1 2 ) ，包含一个n k t s ( v ) 为子设计。 在上述基础上，我们在第七章中得到了本文的主要结果： 上海交通大学博士学位论文 定理1 7 除最多4 0 个可能的例外，任一n k t s ( v ) 可嵌入于某个n k t s ( u ) 的充分 必要条件为v “；o ( m o d 6 1 ，u 3 v ，v 1 8 。 上海交通大学博士学位论文 第二章拟k i r k m a n 三元系嵌入问题的基本构造方法 2 1 引言 本章我们主要讨论带子设计的拟k i r k m a n 三元系的基本构造方法。为便于阅 读，我们对其中的几个主要构造方法给出证明。 2 2 基本构造方法 在本文中，我们将大量使用带各种大小的洞的拟k i r k m a n 三元系。我们称这 些拟k i r k m a n 三元系为不完全拟k i r k m a n 三元系，记为i n k t s 。如果我们有一个 n k t s ( v ) 包含一个n k t s ( w ) 为子设计，那么我们可以去掉子设计，留下一个洞， 我们记得到的不完全拟k i r k m a n 三元系为i n k t s ( v ，w ) 。当然，如果我们有一个 i n k t s ( v ，v ；w ；o ( m o d 6 ) ，那么我们可以用一个n k t s ( w ) 填充该不完全设计的 洞，得到一个n k t s ( v ) ，且它包含一个n k t s ( w ) 为子设计。下面，假设我们有 个n k t s ( v ) ，它包含一个n k t s ( m ) 和一个n k t s ( w 2 ) 为子设计，并且这两个子设计 又相交于一个n k t s ( w 3 ) 。如果我们去掉这些子设计，那么我们得到一个带多个洞 的不完全设计，记作( v ；w l ，w 2 ；w o 一一i n k t s 。 下面我们先给出几个重要概念。首先介绍带洞的g d 设计( 记为i g d d ) 。设 - ( x ，y ，g ，b ) 是一个有序四元组，z 为点集合，y c z ( 我们称y 为洞) ，g 构成z 的一个划分。b 的元素称为区组，g 的元素称为组。若对z 中任意一对点x , y ， 下列条件满足： 1 ) 当 x ，y c y 或亿y ) c g ，g g 时，x 与y 不同时包含于b 的任一区组中： 2 ) 当 x ，y 芷y 且 x ，y ) 旺g ，g g 时，x 与y 恰好同时包含于b 的唯一的 个区组中。 则我们称该四元组为一个i g d d 。 设( ，y ，g ，b ) 为一个，g d d ，如果对任意b b ，都有俐k ，则我们记该脚d 上海交通大学博士学位论文 为k i g d d 。定义i g d d 的型为 q g i l g n l ，d ：g c g 。显然，如果y = ，贝i j i g d d 为前面所定义的g d d 。 另一个重要概念是s t i n s o n 在文献 6 3 】中提出的f r a m e 以及后来推广的不完全 f r a m e 的概念。下面我们给出具体定义。 设( x ，g ，b ) 是一个k g d d ，p c b ，若p 构成烈g 的一个划分，g g ，则 称p 为以g 为洞的带洞平行类。若区组集合b 中的所有区组都能划分为以某个组 为洞的带洞平行类，则称此k g d d 为一个k f r a m e 。我们把 3 卜f r a m e 称为 k i r k m a n f r a m e 。f r a m e ( z ，g ，b ) 的型定义为( i o i ：g c g ) 。 下面的重要引理为我们应用f r a m e 构作设计及研究嵌入问题奠定了良好的基 础。 引理2 1 1 9 设( x ，g ，b ) 为一个忙) - f r a m e ，g 为任意一个组，则恰有蚓( 七一1 ) 个以g 为洞的带洞平行类。 另外一个值得注意的事实是一个型为 f 一t 2 ，“) 的 q f r a m e 等价于一个型 为 ( 幻t ( k 一1 ) ，t l ( k 一1 ) ) ，( k t 2 ( k 1 ) ，t 2 1 ( k 一1 ) ) ，( 幻一( 一1 ) ，厶( k 一1 ) ) ) 的 忙+ l - i g d d 。 均匀k i r k m a nf r a m e 的存在性问题已经完全解决，我们有如下定理： 定理2 2 ( 6 3 ) 存在型为t “的k i r k m a nf r a m e 的充分必要条件为： t i o ( m o d 2 ) ； t ( u 1 ) ；o ( m o d 3 ) ； u 4 一个不完全k p a n e 是一个k i g d d ( ，y ，g ，b ) ，其中区组集合b 能被划 分为带洞的平行类。每一个平行类或是x g 的一个划分，或是x ( g u y ) 的一 个划分，g g 。对每个洞g ，有l g n 】，i 2 个带洞平行类，这些带洞平行类的每 一个都构成x ( g u y ) 的一个划分，还有l g 1 ，l ，2 个带洞平行类，这些带洞平行 类的每个都构成x g 的一个划分。 9 k i r k m a n 。触m e 在解决尉砌4 n 三元系的嵌入问题中起了重要作用。同样， 它在本文中也起到一个显著作用。如果我们填充圈哟”口”p a m e 的洞，我们就得 到以下一个非常重要的构造带子设计的拟k i r l o n a n 三元系的方法。 定理2 3 ( 填洞构造) 6 7 设口0 。设存在一个类型为 f - ，f 2 ， 的k i r k m a n f l a m e ；如果存在一个n k t s ( t f + 口) 包含一个子设计k 粥( 口) ，1 i n ；则存在 一 个n k t s ( t + 口) ，= t i ，包含一个子设计m 嚣 + 口) ，1 i ”。 证明：添加a 个理想点到所给的k i r k m a nf r a m e 。在一个k i r l e m a nf r a m e 中，对任 意t i t ，共有n 2 个以t i 为洞的平行类：在一个n k t s ( t i + 口) 中，共有 t r 2 + ( a 一2 ) 2 个平行类，我们将其分为两部分，一部分为，2 个平行类，用以填 充k i r k m a nf r a m e 中t j 2 个以为洞的平行类，第二部分为一2 ) 2 个平行类，对 所有t i t 依次进行，将每次产生的第二部分的一2 ) 2 个平行类合并即得所需 的最终平行类，注意每个n k t s ( t f + a ) 都包含一个子设计n k t s ( a ) ，1 s i n ，故 最后( 1 2 2 ) 2 个平行类中只包含n k t s ( a ) 中的区组一次。证毕。 用一i n k t s 填充不完全k i r k m a np a m e ，我们就得到以下的广义填洞构造方 法。 定理2 4 ( 广义填洞构造) 设b 口20 。假设以下设计存在： 1 ) 一个型为 ( f l ，“i ) ，( f 2 ，“2 ) ，( 厶，“。) ) 的不完全k i r k m a nf r a m e ； 2 ) 对任意l i n ，有( f l + 6 ；“，+ 口，b ；a ) 一一1 n k t s ； 3 ) 一个i n k t s ( “+ 6 ，“一+ a ) 。 则存在一个艇阿( f + 6 ，“+ 口) ，其中f = t i ，“= “r 要利用上述的填洞构造方法，我们必须先构造出各类k i r k m a nf r a m e 或不完 全k i r k m a nf r a m e 。构造k i r k m a nf r a m e 或不完全k i r k m a np a m e 的一个非常有效的 方法是通过g d d 或i g d d 构造。因此我们必须先构造出各类g d d 或i g d d 。构 1 0 上海交通大学博士学位论文 造g d d 的一个基本方法是如下的w i l s o n 的g d d 基本构造方法 7 4 3 。 定理2 5 ( g d d 基本构造方法) 设( ，g ，b ) 是一个g d d 。s ：x 斗z + t a 0 ) 是 一个函数。对任意b b ，假设存在一个类型 s ( x ) ：x b ) 的一个k g d d ，那 么存在类型为 s ( x ) ：g g 的足一g d d 。 e g 证明：我们如下构作一个所需的k g d d ( v ，g ，b ) 。 v = u ，。岱( x ) ，其中s ( x ) = x 1 z ：，x s 。) 。g = u ，。岱( x ) ：g g 。由条件 知，对任意b b ，存在一个k g d d ( u ，。s s ( x ) ， s ( x ) ：x b ，b ( b ) ) ，我 们取b = ub 。b ( b ) 。下面我们仅需验证a ) v 中任意一对属于不同组的点包含 在b 中一个区组；b ) v 中任意一对属于同组的点不包含在b 中任何一个区组中。 考虑任意点对 五，弦) ，如果，属于g 中不同的组，那么显然z ，y 属于g 中不同 组。对包含 x ，y ) 点对的区组b ，有一个b 中的区组包含 * ，) 。如果* ，属于 g 中同一个组，那么或者x ，y 属于g 中同一个组，或者m = m ，i ，。对这两种情 况，显然没有包含 ，力) 的区组。证毕。 作为推广，我们可以得到，g d d 基本构造方法，见文献 5 0 】。 定理2 6 ( i g d d 基本构造方法) 设( x ，y ，g ，b ) 是一个i g d d 。f ，s 是j z + u o ) 的函数，且满足对每个工x ，有t ( x ) ss ( x ) 。对任意b b ，假设有类型 ( s ( x ) ，t ( x ) ) ：x b 的一个k i g d d ，再假设有类型为 。，s ( x ) ， e c n v t ( x ) ：g g 。则存在类型为 。s ( x ) ，。t ( x ) ：g g 的k i g d d 。 构造出各类g d d 或i g d d 后，我们有如下的构造k i r k m a n 。触m p 和不完全 k i r k m a n 加m e 的方法 4 8 】 6 3 】。 定理2 7 ( k i r k m a n f r a m e 基本构造方法) 设( ，g ，b ) 是一个g d d 。s ：寸z + u 0 ) 是一个函数。如果对任意b b ，有型为爷( 曲：x 研的k i r k m a n f r a m e 。那 么存在型为 s ( x ) ：g g l 幂jk i r k r n a n 加m p 。 上海交通大学博士学位论文 证明：此定理的证明与定理2 6 类似，由于k i r k m a nf r a m e 是一类特殊的g d d ， 所以我们只需验证得到的g d 设计的区组能划分为带洞的平行类。设 s ( z ) = m x ：，x s 。 ，v = u ，。x s ( x ) ，g = u ，。毋( x ) ：g g 。由条件知，对任意 b b ，存在一个k i r k m a n f r a m e ( u 、；。s ( x ) ， s ( x ) ：x b ，b ( 1 3 ) )