1、中国科学:数学2023年第53卷第2期:217232SCIENTIA SINICA Mathematica论文英文引用格式:Stinson D R,Wei R.On maximum parallel classes in packing designs(in Chinese).Sci Sin Math,2023,53:217232,doi:10.1360/SSM-2022-0037c 2022中国科学 杂志社填充设计的最大部分平行类献给朱烈教授80华诞Douglas R.Stinson1,卫瑞中21.David R.Cheriton School of Computer Science,Uni
2、versity of Waterloo,Waterloo,ON N2L 3G1,Canada;2.Department of Computer Science,Lakehead University,Thunder Bay,ON L3V 0B9,CanadaE-mail:dstinsonuwaterloo.ca,rweilakeheadu.ca收稿日期:2022-03-08;接受日期:2022-04-25;网络出版日期:2022-05-26;*通信作者加拿大自然科学和工程研究委员会(Natural Sciences and Engineering Research Council,NSERC)
3、(批准号:RGPIN-03882 和RGPIN-05610)资助项目摘要设整数(,v,k)是最大部分平行类大小为的任意(v,k)-填充设计中所包含的最大区组数目.对于k=3,该问题由Stinson(2021)引入并研究.本文主要研究k=4的情形,获得(,v,4)的上下界.本文给出最大部分平行类大小为的(v,4)-填充设计的具体构造.对于小的值,所构造的填充设计的区组数非常靠近上界(,v,4).本文的一些方法可以推广到k 4的情形.关键词最大部分平行类填充设计最优设计组合设计MSC(2020)主题分类05B401引言设v和k是正整数,且2 6 k 6 v 1.一个(v,k)-填充设计是一个对子S
4、=(X,B),其中X是一个v元集,B是X的一些k元子集构成的集合(称k元子集为区组).使得X中每个点对至多出现在一个区组中.填充数D(v,k)是所有(v,k)-填充设计中最大的区组数.对于k=4,下述结论成立.定理1.18D(v,4)=v4v13 ,其中=1,当v 7,10(mod 12)且v=10,19,1,当v=9或v=17,2,当v=8,10或v=11,3,当v=19,0,其他情形.Stinson 等:填充设计的最大部分平行类若X的每个点对恰出现在一个区组中,则该填充设计称为平衡不完全区组设计(balanced incom-plete block design,BIBD),记作(v,k,
5、1)-BIBD.填充设计S的一个平行类是指一些不相交的区组构成的集合,并划分X.填充设计S的一个部分平行类是指B中一些不相交的区组构成的集合.部分平行类所含的区组数称为该部分平行类的大小.一个大小为的部分平行类称为最大的,如果填充设计S中不存在大小为+1的部分平行类.(,v,k)定义为所有最大部分平行类大小为的(v,k)-填充设计中的最大区组数.Stinson7研究了(,v,3),并给出了一些最大部分平行类大小为的(v,3)-填充设计的直接构造.一些(,v,3)的上界也在文献7中被证明.本文将(,v,3)的结果推广到k=4的情形.第2节给出两种最大部分平行类大小为的(v,k)-填充设计构造方法
6、.第3节给出3个(,v,4)的上界.第4节确定一些(,v,4)的精确值.第5节讨论本文中一些结果推广到k 4的情形.2构造Stinson7利用Room方构造最大部分平行类大小取值较小时的(v,3)-填充设计.该方法的一个自然推广是利用Kirkman方构造(v,4)-填充设计.一个Kirkman方,记作KSk(n),是一个元素取自于n元集V上的tt的阵列R,其中t=n1k1,满足下列条件:(1)集合V中的每个点都包含在阵列R的每一行和每一列的一个单元格中;(2)R中的每个单元格或者是空集,或者是集合V的一个k元子集;(3)R中非空单元格中区组构成的集合是一个(n,k,1)-BIBD.众所周知,K
7、S2(n)是一个Room方.对于k=3,文献3,5证明了如下结论.定理2.1设n为一个正整数,n 3(mod 6),n=9,15.则存在一个KS3(n),可能的例外是n 21,141,153,165,177,189,231,249,261,285,351,357.假设R是一个KS3(n),则可以构造一个最大部分平行类大小为的(n+,4)-填充设计,其中 6n3,具体构造如下.首先,从R中挑选出行,使所挑选的每一行的第一个单元格都非空(共有n3个这样的行).将这些行记为r1,.,r.对ri中的每一个非空单元格都添加上一个新点si,形成一个4长区组.这样获得的n3个4长区组形成一个(n+,4)-填
8、充设计.由R的第一列中的单元格产生的区组形成一个大小为的部分平行类.因为填充设计的每个区组包含某个si,所以这样的部分平行类是最大的.因此,我们有下述结论.定理2.2设n为一个正整数,n 3(mod 6),且n 9,15,21,141,153,165,177,189,231,249,261,285,351,357.则存在一个区组数为n3、最大部分平行类大小为的(n+,4)-填充设计.我们可以稍微改进这个结果.如果将s1,.,s上的任意一个4-填充设计添加进去,那么最大部分平行类大小仍为,因为每个区组总是至少包含一个si.定理2.3设n是一个正整数,n 3(mod 6),且n 9,15,21,1
9、41,153,165,177,189,231,249,261,285,351,357.则存在一个区组数为n3+D(,4)的(n+,4)-填充设计,其最大部分平行类大小为.218中国科学:数学第 53 卷第 2 期在定理2.2和2.3中构造的(v,4)-填充设计须满足v 3(mod 6).下面给出一种变形来放松这种限制.一个横截设计,记作TD(k,n),是一个三元组(V,G,B),其中V是一个kn元集合,G将集合V划分成k个大小为n的组,B是集合V的k元子集构成的集合,B中的元素称作区组,使得V中任意点对或者出现在同一个区组中,或者出现在同一组中,但不能同时发生.存在k2个两两正交的n阶拉丁方(
10、MOLS)等价于存在一个TD(k,n).有关两两正交拉丁方的内容,参见文献1.n阶拉丁方L的一个截态是由来自不同行、不同列的n个单元格构成的集合,这n个单元格包含n个不同的元素.k个相互正交的n阶拉丁方的公共截态是n个单元格构成的集合,它是k个拉丁方中每一个的截态.定理2.4假设两个正交的n阶拉丁方有一个公共截态,且1 6 6 n.则存在一个区组数为n+D(,4)、最大部分平行类大小为的(3n+,4)-填充设计.证明从两个正交的n阶拉丁方出发,首先构造相对应的TD(4,n).然后删除横截设计的第4组中n个点,并且删除所有包含这些点的区组.剩下的n个区组形成一个(3n+,4)-填充设计.最后,在
11、第4组中未被删除的个点上构造一个大小为D(,4)的填充设计,这样就得到一个区组数为n+D(,4)的(3n+,4)-填充设计.与截态相对应的未被删掉的区组形成一个大小为的部分平行类.因为每个区组至少包含这个TD的第4组中个未被删除的点,所以任何部分平行类最大者的大小为.一个n阶自正交拉丁方(self orthogonal Latin square,SOLS)(记作SOLS(n)是一个与其转置正交的拉丁方.容易看出,SOLS(n)的主对角线是这两个正交拉丁方的公共截态.定理2.54对于所有正整数n=2,3,6,存在一个n阶自正交拉丁方.由定理2.4和2.5可得以下结论.定理2.6若n 4,n=6,
12、则对于1 6 6 n,存在一个区组数为n+D(,4)、最大部分平行类大小为的(3n+,4)-填充设计.注2.1定理2.3和2.6给出类似的结论.对于适当的v,它们都给出区组数约为(v )3+(1)12的填充设计.定理2.6产生最大部分平行类大小为的(v,4)-填充设计,其中v 0(mod 3).现在描述一些变形.假设用定理2.6去构造一个区组数为n+D(,4)、最大部分平行类大小为的(3n+,4)-填充设计.然后删掉一个不包含在大小为的部分平行类的任何区组中的一个点x(这里要求 6 n 1),同时删掉包含x的个区组.则可以得到以下结果.定理2.7若n 4,n=6,则对于1 6 6 n 1,存在
13、一个区组数为(n 1)+D(,4)、最大部分平行类大小为的(3n 1+,4)-填充设计.在定理2.7中,本文构造了一个具有大小为的部分平行类的(v,4)-填充设计,其中v 2(mod 3).现在处理最后一种情形:v 1(mod 3).同样,用定理2.6去构造一个区组数为n+D(,4)、最大部分平行类大小为的(3n+,4)-填充设计.我们进行以下修改:(1)将在最后一组的个点上构造的D(,4)个区组全部删除;(2)将在最后一组的个点和一个新点上构造的4-填充设计的D(+1,4)个区组添加进去.219Stinson 等:填充设计的最大部分平行类定理2.8若n 4,n=6,则对于1 6 6 n,存在
14、一个区组数为n+D(+1,4)、最大部分平行类大小为的(3n+1+,4)-填充设计.3上界本节证明(,v,4)的3个上界(即最大部分平行类大小为的(v,4)-填充设计的最大区组数).首先设定一些记号.设S=(X,B)是一个区组数为b的(v,4)-填充设计,其最大部分平行类大小为,故v 4.设P=B1,.,B是个不相交区组构成的集合,并令P=i=1Bi.令T=XP.则有|P|=4和|T|=v 4.对于x P且0 6 i 6 3,令Tix表示包含点x且恰好包含T中i个点的不属于P的区组构成的集合.定义tix=|Tix|.3.1第一个界第一个界使用文献7中所述方法.可以观察到,对于任意两个点x,y
15、Bi P,区组B T3x和区组B T3y不可能不相交.否则,可以删掉Bi并且在部分平行类中添加两个区组B和B,则可获得一个大小为+1的新部分平行类.由上述观察直接可以得到下述引理.引理3.1设Bi=w,x,y,z P且t3w maxt3x,t3y,t3z.则下列两个条件之一成立:(1)t3w6 3;(2)t3w 4且t3x=t3y=t3z=0.证明假设t3w 4且B T3x T3y T3z.则存在一个区组B T3w,使得B B=.这与上面的观察相矛盾.因此,若t3w 4,则有t3x=t3y=t3z=0.因为P包含个区组,所以有如下的界.定理3.1(,v,4)6(8 7)+max12,v 43)
16、.证明因为P是最大的,所以T中不包含区组.由引理3.1可得,至多有 max12,v 43个区组只包含集合P中一个点,且包含T中3个点.集合P中不包含在P的任何区组中的点对数目为(42)6=8(1).因此,至多有8(1)个不属于P的区组,每个至少包含P中两个点.因此,填充设计中区组总数至多为8(1)+max12,v 43+.证毕.220中国科学:数学第 53 卷第 2 期推论3.1对于v 4+36,有(,v,4)6v3+2023 7.证明不等式v43 12成立当且仅当不等式v 4+36成立.因此,当v 4+36时,由定理3.1可得(,v,4)6(8 7)+v 43)=v3+2023 7.证毕.3.2第二个界现在用一个更加精确的计数来证明一个较好的界.接下来的两个引理都很简单.引理3.2对于任意x P,下面两个不等式等价:3t3x+2t2x+t1x6 v 4,(3.1)t2x+2t1x+3t0 x6 4(1).(3.2)引理3.3填充设计的区组数b可由下述公式计算获得:b=+xPt3x+12xPt2x+13xPt1x+14xPt0 x.(3.3)对于任意x P,定义cx=t3x+t2x2+