Existence Of Incomplete Canonical Kirkman Packing Designs

The embedding problem is one of the fundamental problems in combinatorial design theory.The existence of incomplete canonical Kirkman packing design with holes play an important role on the embedding of canonical Kirkman packing design.Let positive integers u,v?4(mod 6).An incomplete canonical Kirkman packing design of order u with a hole of size v,denoted by ICKPD(u,v),is a triple(X,Y,C)where X is a point set of u elements,Y(called a hole)is a v-subset of X,and C is a collection of subsets(blocks)of X with size 3 or 4 such that:(i)|B?Y|?1 for each B?C;(ii)any two distinct elements of X occur together in at most one block;(iii)C admits a partition into(u-v)/2 parallel classes on X,each of which contains one block of size 4 and(v-4)/3 triples,and a further(v-4)/2 holey parallel classes of triples on X\Y;(iv)each element of X\Y is contained in exactly two blocks of size 4.First we directly construct some nonuniform 4-GDD with groups of three dif-ferent sizes and some incomplete Kirkman packing designs with small holes.Then applying“Weighting Construction”and“Filling in Holes Construction”,we almost completely determine the spectrum for ICKPD(u,v)s and obtain the fol-lowing main results:Theorem A:Necessary conditions for existence of an ICKPD(u,v)are u?v?4(mod 6)and u?3v+4.These conditions are sufficient with a definite exception(u,v)=(16,4)and except possibly when v?4(mod 12),v>76 and u?{3v+4,3v+10}.Theorem B:If m,n are positive integers with m?n?2m,then there exists a 4-GDD of type(3m)~4(3n)~1(6m)~1.Theorem C:(1)There exists a 4-GDD of type 12~t15~1(6t)~1for t?4 and t/?{7,9,10,13,14,15,17,18,19,22,23};(2)There exists a 4-GDD of type 12~t18~1(6t)~1for t?4 and t/?{17,18,19,22,23};(3)There exists a 4-GDD of type 12~t21~1(6t)~1for t?4 and t/?{7,8,...,12,14,15,17,18,19,22,23}.The structure of this dissertation is organized as follows:The first chapter introduces the basic concepts of Kirkman packing designs and incomplete Kirkman packing designs,as well as the latest results for existence of these designs.In the second chapter,the concepts of group divisible design and Kirkman frame are introduced,and some basic recursive construction methods for group divisible designs are also given.Using mixed difference method and computer search to construct some nonuniform 4-GDDs with groups of three different sizes.At the same time,the existence results of 4-GDDs are updated.By applying the result 4-GDDs,we establish some new Kirkman frames,which play a key role in the fourth chapter to prove the existence of incomplete canonical Kirkman packing designs with a maximum hole.In Chapter 3,we first apply direct construction to construct some key ICKPD(u,v)s with small v,and then use recursive construction to establish the spectrum of ICKPD(u,v)s with 4?v?76.The fourth chapter makes full use of new 4-GDDs and Kirkman frames con-structed in Chapter 2 to show that the existence of several classes of incomplete canonical Kirkman packing designs with a maximum hole,which lay the foun-dation for the establishment of the main results of this dissertation in the fifth chapter.Chapter 5 is devoted to determining the spectrum for ICKPDs by recursion and induction.Chapter 6 gives a brief conclusion of this dissertation and puts forward the questions of further research.