Supersimple+group+divisiblede+signs+with+blocksize+four

南京师范大学硕士学位论文Super-simplegroupdivisibledesignswithblocksizefour姓名：严飞申请学位级别：硕士专业：数学；运筹学与控制论指导教师：曹海涛2009-05-16摘要设K是正整数的集合，一个λ重可分组设计是一个满足以下条件的三元组(X,G,B)：X是一个有限点集；G中的元素(称为组)均是X的子集，并且所有组构成X的一个划分；B是由X的k元子集(称为区组)构成的集合，k∈K；对于任意两个属于不同组的点恰好在λ个区组中出现，而属于同一组的两个点不在任何区组中出现。

如果它的区组集B可以划分成一些平行类，其中每个平行类都是点集X的一个划分，则称这个设计为可分解的可分组设计。

没有重复区组的设计称为单纯设计。

若一个设计(V,B)的区组集B中的任意两个不同的区组B1,B2满足|B1∩B2|≤2，则称此设计为超单设计。

超单设计的概念是由Gronau和Mullin提出的。

超单设计本身是一个有趣的组合设计问题，而且它在编码理论等学科中有广泛的应用。

例如：超单的设计可以用于构造重叠码。

超单的可分组设计对其它超单设计的构造有很重要的作用。

本文主要研究区组大小为4，型为g u，重复度为2到6的超单可分组设计的存在性问题。

我们证明了它们存在的必要条件也是充分的，除了(λ,g,u)∈{(3,2,5),(4,3,5)}。

关键词:可分组设计；成对平衡设计；超单。

iiiAbstractLet K be a set of positive integers.A group divisible design(K,λ)-GDD is a triple(X,G,B)which X is afinite set of points,G is a partition of X into subsets called groups,B is a collection of subsets of X(called blocks)with sizes from K, such that every pair of points from distinct groups occurs in exactlyλblocks,and no pair of points belonging to a group occurs in any block.A design is called simple if it contains no repeated blocks.A design(V,B) is said to be super-simple if|B1∩B2|≤2for any two blocks B1,B2∈B and B1=B2.The concept of super-simple designs was introduced by Gronau and Mullin. The existence of super-simple designs is an interesting extremal problem by it-self,but there are also some useful applications.For example,such super-simple designs are used in perfect hash families and covering,in the construction of new designs and in the construction of superimposed codes.Super-simple group divisible designs are powerful for the construction of other types of super-simple designs.In this thesis,we mainly investigate the existence of a super-simple(4,λ)-GDD of type g u forλ∈[2,6].We shall show that the necessary conditions for the existence of a super-simple(4,λ)-GDD of type g u are also sufficient except for(λ,g,u)∈{(3,2,5),(4,3,5)}.Key words:group divisible design;pairwise balanced design;super-simpleii学位论文独创性声明本人郑重声明:1、坚持以“求实，创新”的科学精神从事研究工作。

2、本论文是我个人在导师指导下进行的研究工作和取得的研究成果。

3、本论文中除引文外，所有实验、数据和有关材料均是真实的。

4、本论文中除引文和致谢的内容外，不包含其他人或其它机构已经发表或撰写过的研究成果。

5、其他同志对本研究所做的贡献均已在论文中作了声明并表示了谢意。

作者签名：日期：学位论文使用授权声明本人完全了解南京师范大学有关保留、使用学位论文的规定，学校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进行检索；有权将学位论文的标题和摘要汇编出版。

保密的学位论文在解密后适用本规定。

作者签名：日期：Chapter1IntroductionIn this chapter,we shall give a brief introduction for some base definitions and known results.§1.1Base DefinitionsWe begin with the definition of a group divisible design.Definition1.1Let K be a set of positive integers.A group divisible design(K,λ)-GDD is a triple(X,G,B)which satisfies the following properties:1.X is afinite set of points,2.G is a partition of X into subsets called groups,3.B is a collection of subsets of X(called blocks)with sizes from K,such thatevery pair of points from distinct groups occurs in exactlyλblocks,4.no pair of points belonging to a group occurs in any block.When K={k},we write(K,λ)-GDD as(k,λ)-GDD.Further,we denote (K,1)-GDD as K-GDD and(k,1)-GDD as k-GDD.The type of the GDD(X,G,B)is the multiset of sizes|G|of the G∈G and we usually use the“exponential”notation for its description:type1i2j3k···de-notes i occurrences of groups of size1,j occurrences of groups of size2,and so on.A(K,λ)-GDD(X,G,B)is resolvable(denoted by RGDD)if the blocks of B can be partitioned into parallel classes,each parallel class being a partition of the point set X.A pairwise balanced design(v,K,λ)-PBD is a(K,λ)-GDD of type1v indeed.A balanced incomplete block design(v,k,λ)-BIBD is a(k,λ)-GDD of type1v.A transver-sal design TD(k,n,λ)is a(k,λ)-GDD of type n k.Whenλ=1,we simply write TD(k,n).It is idempotent if it contains a parallel class of blocks.It is well known that a TD(k,n)is equivalent to k−2mutually orthogonal Latin squares of order n and a resolvable TD(k,n)(denoted by RTD(k,n))is equivalent to a TD(k+1,n).A design is called simple if it contains no repeated blocks.1Definition1.2A design(V,B)is said to be super-simple if|B1B2|≤2for anytwo blocks B1,B2∈B and B1=B2.When|B|=3for any B∈B,a super-simple design is just a simple design. Whenλ=1,the designs are necessarily super-simple.The concept of super-simple designs was introduced by Gronau and Mullin in[15].The existence of super-simple designs is an interesting extremal problem by itself,but there are also some useful applications.For example,such super-simple designs are used in perfect hash families[21]and covering[4],in the con-struction of new designs[3]and in the construction of superimposed codes[19].Super-simple group divisible designs are powerful for the construction of other types of super-simple designs.In this thesis,we focus on the existence of a super-simple group divisible design with block size four.§1.2Some Known ResultsIn this section,we will introduce some known results about the above men-tioned designs.Lemma1.1([1,5])1.There exists a(v,{4,5,6},1)-PBD and a(v,{4,5,6,7,8},1)-PBD for all v≥13and v/∈{14,15,18,19,23}.2.There exists a(v,{5,6,7,8,9},1)-PBD for all v≥21and v/∈{22−24,27−29,32−34}.3.A(v,{4,5,6,8},1)-PBD exists for all v≥8and v/∈{9,10,11,12,14,15,18,19,23}.4.A(v,{4,7},1)-PBD exists for all v≡1(mod3)and v/∈{10,19}.5.A4-GDD of type m u exists if and only if u≥4,(u−1)m≡0(mod3)andu(u−1)m2≡0(mod12)except for(m,u)∈{(2,4),(6,4)}.6.An idempotent TD(5,n)exists for all n≥5and n/∈{6,10}.7.A TD(6,n)exists for all n≥5and n/∈{6,10,14,18,22}.8.An idempotent TD(6,n)exists for all n≥7and n/∈{10,14,18,22,26}.9.A TD(7,n)exists for all n≥7and n/∈{10,14,15,18,20,22,26,30,34,38,46,60}.There are some known results for the existence of super-simple designs,es-pecially for super-simple(v,k,λ)-BIBDs.When k=4or5the necessary condi-tions are known to be sufficient for2≤λ≤6or2≤λ≤5with few possible exceptions.We summarize these known results in the following Theorems.Theorem1.2([2,6,9–11,14,15,18])There exists a super-simple(v,4,λ)-BIBD with2≤λ≤6if and only if1.λ=2,v≡1(mod3)and v≥7;2.λ=3,v≡0,1(mod4)and v≥8;3.λ=4,v≡1(mod3)and v≥10;4.λ=5,v≡1,4(mod12)and v≥13;5.λ=6,v≥14.Theorem1.3([12–14,16])A super-simple(v,5,λ)-BIBD exists with2≤λ≤5if and only if1.λ=2,v≡1,5(mod10),v=5,15,except possibly when v∈{115,135};2.λ=3,v≡1(mod20)and v≥21,and except possibly when v≡5(mod20)and v≥25;3.λ=4,v≡0,1(mod5)and v≥15;4.λ=5,v≡1(mod4)and v≥17,except possibly when v=21.We also have the following known results about super-simple TD(4,λ;v) which can be found in([17])Theorem1.4A super-simple TD(4,λ;v)exists if and only ifλ≤v and(λ,v)is neither(1,2)nor(1,6).§1.3Main ResultsIn this thesis,we mainly investigate super-simple PBDs and super-simple GDDs.In Chapter3,we shall prove that the necessary conditions for a super-simple(v,{4,5},λ)-PBD withλ∈[2,4]are also sufficient.Theorem1.5There exists a super-simple(v,{4,5},λ)-PBD with2≤λ≤4if and only if1.λ=2,v≥7,and except when v∈{8,9,12,14};2.λ=3,v≡0,1(mod4)and v≥8;3.λ=4,v≥10,and except when v=11and possibly except when v=12.It is easy to see that the following are the necessary conditions for the exis-tence of a super-simple(k,λ)-GDD of type g u.Theorem1.6The necessary conditions for the existence of a super-simple(k,λ)-GDD of type g u are1.λ≤g(u−2);k−22.u≥k;3.λ(u−1)g≡0(mod k−1)and4.λu(u−1)g2≡0(mod k(k−1)).In Chapter4,we shall prove that the necessary conditions for the existence of a super-simple(4,λ)-GDD of type g u withλ∈[2,6]are also sufficient with two exceptions.Theorem1.7The necessary conditions for the existence of a super-simple(4,λ)-GDD of type g u with2≤λ≤6are also sufficient except for(λ,g,u)∈{(3,2,5), (4,3,5)}.Chapter 2Recursive ConstructionsFor our recursive constructions,we shall use the following standard recur-sive constructions,the proofs of which can be found in [10].Construction 2.1(Weighting )Let (X ,G ,B )be a super-simple GDD with index λ1,and let ω:X →Z + {0}be a weighting function on X ,where Z +is the set of positive integers.Suppose that for each block B ∈B ,there exists a super-simple (k,λ2)-GDD of type {ω(x ):x ∈B }.Then there exists a super-simple (k,λ1λ2)-GDD of type { x ∈G i ω(x ):G i ∈G}.Construction 2.2(Breaking up groups )If there exists a super-simple (K,λ)-GDD of type (sh 1)u 1···(sh t )u t and a super-simple (K,λ)-GDD of type s h i +ηfor each i ,1≤i ≤t ,then there exists a super-simple (K,λ)-GDD of type s t i =1h i u i +η,where η=0or 1.Similarly,we also have the following construction.Construction 2.3If there exists a super-simple (K,λ)-GDD of type h u 11···h u t t anda super-simple (h i +η,K,λ)-PBD for each i ,1≤i ≤t ,then there exists a super-simple (t i =1h i u i +η,K,λ)-PBD,where η=0or 1.To present the next construction,we need the notation of a (K,λ;v,ω)-IPBD.Definition 2.1An incomplete pairwise balanced design (K,λ;v,ω)-IPBD is a triple (V ,H ,B )which satisfies the following properties:1.V is a v -set of points,H is a ω-subset of V (called a hole )and B is a collection of subsets of V (called blocks )with block sizes from K ;2.|H B |≤1for all B ∈B ;3.Any two points of V appear either in H or in λblocks of B exactly.Now we give a recursive construction for super-simple PBDs by using in-complete super-simple PBDs.It’s obvious that a super-simple (K,λ;v,ω)-IPBD is a super-simple (v,K,λ)-PBD indeed when ω∈{0,1}.So,the following construc-tion can be considered as a generalization of Construction 2.3.5Ch2Recursive Constructions 6Construction 2.4(Filling in holes I )Suppose that there exists a super-simple (K,λ)-GDD of type h 1h 2···h t ,a super-simple (K,λ;h i +s,s )-IPBD for each i ,1≤i ≤t −1,and a super-simple (h t ,K,λ)-PBD,then there exists a super-simple (t i =1h i +s,K,λ)-PBD.Proof:Suppose (X ,G ,B )is a super-simple (K,λ)-GDD of type h 1h 2···h t .Let Y ={∞1,∞2,···,∞s }.For each G i ∈G ,1≤i ≤t −1,construct on the point set G i Y a super-simple (K,λ;h i +s,s )-IPBD and denotes its block set by B G i .For G t ∈G ,construct on the point set G t Y a super-simple (h t +s,K,λ)-PBDand denotes its block set by B G t .Let A =(t i =1B G i ) B .Then,it is not difficult to check that A is the desired block set of a super-simple (t i =1h i +s,K,λ)-PBD on the point set X ∪Y .In Chapter 4,we shall also need the following two “filling in holes”construc-tions.The first construction is similar to Construction 2.2,we just state it without proof.Construction 2.5(Filling in holes II )If there exists a super-simple (K,λ)-GDD of type (sh 1)u 1···(sh t )u t ,a super-simple (K,λ)-GDD of type s h i (sm )1for each i ,1≤i ≤t −1and a super-simple (K,λ)-GDD of type s h i +m ,then there exists asuper-simple (K,λ)-GDD of type s Σt i =1h i u i +m .For our second construction,we need the notation of an incomplete group divisible design.Definition 2.2An incomplete group divisible design (K,λ)-IGDD with type (g,s )u is a quadruple (X ,G ,H ,B )which satisfies the following properties:1.|X |=gu ,G ={G 1,G 2,···,G u }is a partition of X into u subsets of cardi-nality g ,H ={H 1,H 2,···,H u }(the G i are groups and the H i are holes )is a collection of subsets of X such that H i ⊆G i and |H i |=s ,i =1,2,···,u .2.Any pair of distinct points of X which occurs in a group does not occur in any block.Ch2Recursive Constructions73.If a pair of distinct points from X comes from distinct groups and each pointoccurs in the hole of its respective group,then that pair occurs in no block of B.Otherwise,it occurs in exactlyλblocks of B.Construction2.6(Filling in holes III)Suppose there exist1.a TD(k,m)with r parallel classes;2.a super-simple(k2,λ)-IGDD of type(t+n i,n i)k,n i≥0,1≤i≤r;3.a super-simple(k2,λ)-GDD of type t k when r<m;4.a super-simple(k2,λ)-GDD of type(Σri=1n i)k when r>1or a super-simple (k2,λ)-GDD of type(t+n1)k when r=1or a super-simple(k2,λ)-GDD oftype n k1when r=1.Then there exists a super-simple(k2,λ)-GDD of type(mt+Σri=1n i)k.Proof:We start with a TD(k,m)with r parallel classes P1,P2,···,P r.Give its every point weight t.If r>1,for each block B∈P i,1≤i≤r,place a super-simple(k2,λ)-IGDD of type(t+n i,n i)k.It should be mentioned that these points in the holes of IGDDs are disjoint if the two blocks B1and B2come from different parallel classes,and the holes are the same if B1and B2come from the same parallel class.For each of the other blocks not in the r parallel classes,place a super-simple(k2,λ)-GDD of type t k.Thus we have obtained a(k2,λ)-IGDD oftype(mt+Σri=1n i,Σri=1n i)k.Filling in the holes with a super-simple(k2,λ)-GDDof type(Σri=1n i)k,we get a super-simple(k2,λ)-GDD of type(mt+Σri=1n i)k.If r=1,it is obvious that P1contains m blocks,denote them by B1,B2,···, B m.For any block B∈P1,place a super-simple(k2,λ)-GDD of type t k.For each block B j∈P1,1≤j≤m−1,place a super-simple(k2,λ)-IGDD of type (t+n1,n1)k.Note that the holes are the same.For the block B m,place a super-simple(k2,λ)-IGDD of type(t+n1,n1)k if there exists a super-simple(k2,λ)-GDD of type n k1.otherwise,place a super-simple(k2,λ)-GDD of type(t+n1)k.Thus we have obtained a super-simple(k2,λ)-GDD of type(mt+n1)k as desired or a super-simple(k2,λ)-IGDD of type(mt+n1,n1)k which also leads to the required (k2,λ)-GDD of type(mt+n1)k byfilling in the holes with a super-simple(k2,λ)-GDD of type n k1.Chapter3Super-simple(v,{4,5},λ)-PBDIn this chapter,we dealt with the existence of super-simple(v,{4,5},λ)-PBD withλ∈[2,4].Let K be a set of positive integers and m denote the smallest integer in K. Defineα(k)=gcd{k−1:k∈K}andβ(k)=gcd{k(k−1):k∈K}.It is easy to see that the following are the necessary conditions for the existence of a super-simple(v,K,λ)-PBD.1.v≥(m−2)λ+2;2.λ(v−1)≡0(modα(K))and3.λv(v−1)≡0(modβ(K)).The necessary condition for the existence of a super-simple(v,{4,5},3)-PBD is the same as the necessary condition for the existence of a super-simple(v,4,3)-BIBD.Thus,the existence problem of a super-simple(v,{4,5},3)-PBD has been solved already.In this chapter we investigate the existence of super-simple(v,{4, 5},λ)-PBD withλ=2and4.§3.1λ=2In this section,we shall prove that the necessary conditions for the existence of a super-simple(v,{4,5},2)-PBD are also sufficient except for v∈{8,9,12,14}.Theorem3.1A super-simple(v,{4,5},2)-PBD exists if and only if v≥7except when v∈{8,9,12,14}.First,we shall use direct constructions to obtain super-simple(v,{4,5},2)-PBD for some small values of v.These designs have been obtained after computer-assisted searches.The way to check the super-simplicity is essentially the same as what was used in[3].Suppose that a design is obtained by developing m base blocks modulo v.Let S={b1,b2,b3},b1<b2<b3,be a3-subset contained in a base block.Instead of developing S modulo v we form the following three representatives of the orbit corresponding to S:{b1−b i,b2−b i,b3−b i},i=1,2,3.8It is mentioned in[3]that if these3-subsets are pairwise distinct,then the design is super-simple.Lemma3.2There exists a super-simple(15,{4,5},2)-PBD.Proof:Let the point set be Z15.Below are the required base blocks,the required de-sign is obtained by developing the base blocks{0,3,6,9,12},{0,1,4,5},{0,2,7,9} modulo15.Here,thefirst base block{0,3,6,9,12}has a short orbit of order3.Lemma3.3There exists a super-simple(v,{4,5},2)-PBD for any v∈M={17, 23,27,33,39,47}.Proof:For each v∈M,take the point set Z v.Instead of listing all the required blocks,we only list the base blocks and all the required blocks can be generated from them by(+1mod v).v=17{0,1,2,5,8}{0,2,7,11}v=23{0,1,2,5,11}{0,2,6,16}{0,3,8,15}v=27{0,1,2,5,11}{0,2,7,15,19}{0,3,14,21}v=33{0,1,2,4,11}{0,3,8,15,21}{0,4,14,20}{0,5,14,22}v=39{0,1,2,4,9}{0,3,13,19,28}{0,4,17,25}{0,5,17,24}{0,6,16,27}v=47{0,1,3,9,27}{0,1,4,6}{0,4,11,23}{0,5,17,33}{0,7,17,32}{0,8,18,34}{0,9,20,34}Lemma3.4There exists a super-simple(v,{4,5},2)-PBD for any v∈M={18, 26,32,36,38,42,48,56,66}.Proof:For each v∈M,take the point set Z v.All the required blocks can be generated from the following base blocks by(+2mod v).v=18{0,1,2,4,8}{0,1,3,9}{0,3,6,13}{0,5,7,11}{0,5,9,10}v=26{0,1,2,3,6}{0,2,5,9,15}{0,4,14,19}{0,6,17,19}{0,7,12,23}{0,8,16,25}{1,5,13,19}v=32{0,1,3,9,27}{0,1,2,4,8}{0,3,7,18}{0,5,12,22}{0,5,15,24}{0,6,17,18}{0,7,19,23}{0,9,19,21}{0,11,16,29}v=36{0,1,3,9,27}{0,6,15,19}{0,7,21,22}{0,5,7,10}{0,5,11,19}{0,1,13,17}{0,2,18,29}{0,2,25,35}{0,3,8,23}{0,4,10,24}{0,4,12,29}v=38{0,1,3,9,27}{0,1,4,12,36}{0,2,7,8}{0,4,9,18}{0,7,13,22}{0,10,21,31}{0,10,25,26}{0,11,18,33}{0,13,17,25}{0,17,19,35}{0,19,23,33}v=42{0,1,3,9,27}{0,11,21,33}{0,3,4,10}{0,5,7,10}{0,5,9,13}{0,6,14,26}{0,7,18,33}{0,8,25,35}{0,1,23,29}{0,2,19,31}{0,2,23,28}{0,4,19,22}{0,11,12,25}v=48{0,1,3,9,27}{0,15,25,37}{0,4,19,35}{0,5,7,10}{0,5,9,13}{0,6,13,18}{0,8,16,34}{0,11,20,36}{0,11,28,42}{0,1,4,33}{0,2,21,35}{0,2,25,26}{0,3,10,39}{0,17,37,47}{0,21,27,41}v=56{0,1,2,3,6}{0,2,5,7,11}{0,20,43,47}{0,7,21,41}{0,10,21,22}{0,12,25,28}{0,14,29,34}{0,14,32,47}{0,18,41,49}{0,19,29,48}{0,4,35,43}{0,6,32,45}{0,8,25,45}{0,9,30,46}{0,17,33,49}{1,7,25,35}{1,13,27,39}v=66{0,1,3,9,27}{0,20,45,55}{0,4,29,41}{0,3,29,49}{0,6,38,59}{0,4,43,65}{0,6,13,63}{0,5,43,58}{0,11,17,21}{0,5,8,18}{0,16,33,47}{0,18,41,51}{0,19,31,49}{0,1,33,65}{0,2,22,56}{0,2,40,47}{0,9,14,36}{0,11,27,42}{0,12,26,42}{0,15,19,57}{0,15,23,59}We also need the following known results about super-simple(v,{4,5},λ)-GDDs.Lemma3.5([16])There exists a super-simple(5,2)-GDD of type v5where v≡2(mod4).It is obvious that we can obtain a super-simple(v,{k−1,k},λ)-PBD by delet-ing one point from the point set of a super-simple(v,k,λ)-BIBD.So,we have the following lemma.Lemma3.6If there exists a super-simple(v,k,λ)-BIBD,then there exists a super-simple(v−1,{k−1,k},λ)-PBD.More generally,we can obtain a super-simple(v−s,{k−1,k},λ)-GDD by deleting s points from the last group of a super-simple(v,k,λ)-GDD.Lemma3.7If there exists a super-simple(v,k,λ)-GDD with type h1h2···h t,then there exists a super-simple(v−s,{k−1,k},λ)-GDD with type h1h2···h t−1(h t−s).Lemma3.8There exists a super-simple(v,{4,5},2)-PBD for any v≡0,4(mod10) and v/∈{4,14,114,134}.Proof:By Theorem1.3,there exists a super-simple(v,5,2)-BIBD for any v≡1,5 (mod10)and v/∈{5,15},except possibly when v∈{115,135}.Applying Lemma 3.6with k=5andλ=2,we can get a super-simple(v,{4,5},2)-PBD for any v≡0,4(mod10)and v/∈{4,14,114,134}.Lemma3.9There exists a super-simple(v,{4,5},2)-PBD for any v∈M={29,53, 59,78,83,102,107,114,119,132,138,143,156,162}∪{12×t+δ:t∈[5,13]\{6,9},δ=2,3}.Proof:For each v∈M,let v=4g+x.The two parameters g and x are listed in the following table.We start from a super-simple(5,2)-GDD of type g5which exists by Lemma3.5.Removing g−x points from the last group of the super-simple(5,2)-GDD of type g5,we get a super-simple({4,5},2)-GDD of type g4x1 by Lemma3.7.Applying Construction2.3withη=0,we get a super-simple (4g+x,{4,5},2)-PBD.Here,all these input super-simple(g,{4,5},2)-PBD and (x,{4,5},2)-PBD come from Theorems1.2,1.3and Lemmas3.2-3.4,3.8.v=4g+x g x v=4g+x g x v=4g+x g x297153131591376213106313117817108317158619108719119820189920191022118107231511423221192519122252212325231322820v=4g+x g x v=4g+x g x v=4g+x g x1342822135282313828261433119146312214731231563324158332615933271623330Lemma3.10There exists a super-simple(v,{4,5},2)-PBD for any v∈{72,77,89, 96,108,113,137,149}∪{12×t+δ:t∈{5,7,9,10,12},δ=8,9}.Proof:By Theorem1.4,there exists a super-simple(4,2)-GDD of type g4.Start-ing form this GDD and applying Construction2.3,we obtain a super-simple (4g+η,{4,5},2)-PBD,whereη=0or1.Here,the input designs(g+η,{4,5},2)-PBDs come from Theorems1.2,1.3and Lemmas3.3,3.4,3.8,3.9.We list all the parameters in the following table.v=4g+ηgηv=4g+ηgηv=4g+ηgη6817069171721807719189221922309323196240108270113281116290117291128320129321137341149371152380153381Lemma3.11There exists a super-simple(126,{4,5},2)-PBD.Proof:Start from a super-simple(5,2)-GDD of type255which exists by Lemma 3.5.Then,applying Construction2.3withη=1,we get a super-simple(126,{4,5}, 2)-PBD.Here,the input super-simple(26,{4,5},2)-PBD comes from Lemma3.4.Now,we shall prove Theorem3.1.By Theorem1.2,there exists a super-simple(v,{4,5},2)-PBD for any v≡1(mod3)and v≥7.Then we only need to prove that there exists a super-simple(v,{4,5},2)-PBD for any v≡0,2(mod3)and v≥8.For convenience,we use[a,b]1,23or[a,b]0,23to denote a set of positiveintegers v such that a≤v≤b and v≡1,2(mod3)or v≡0,2(mod3).Lemma3.12There exists a super-simple(v,{4,5},2)-PBD for any v≥11,v/∈{12,14}and v=48t+m,where m∈[0,18]0,23,t≥0.Proof:For t≤3,the existence of a super-simple(v,{4,5},2)-PBD has been solved by Theorem1.3and Lemmas3.2-3.4,3.9,3.10.For t≥4,we start from a super-simple(5,2)-GDD of type(12t−5)5.Remov-,points from the last group,we get a super-simple ing12t−5−x,x∈[20,38]1,23({4,5},2)-GDD of type(12t−5)4x1by Lemma3.7.Applying Construction2.3 withη=0,we get a super-simple(48t+m,{4,5},2)-PBD.Here,all these input super-simple(12t−5,{4,5},2)-PBD and(x,{4,5},2)-PBD come from Theorems 1.2,1.3and Lemmas3.3,3.4,3.8.Lemma3.13There exists a super-simple(v,{4,5},2)-PBD for any v=48t+m, ,t≥0.m∈[20,41]0,23Proof:For t=0,1,2,there exists a super-simple(v,{4,5},2)-PBD by Theorem1.3 and Lemmas3.3,3.4,3.8-3.11.For t≥3,we start from a super-simple(5,2)-GDD of type(12t+1)5.Re-,points from the last group,we get a super-moving12t+1−x,x∈[16,37]1,23simple({4,5},2)-GDD of type(12t+1)4x1.Applying Construction2.3withη= 0,we get a super-simple(v,{4,5},2)-PBD.Here,all these input super-simple (12t+1,{4,5},2)-PBD and(x,{4,5},2)-PBD come from Theorems1.2,1.3and Lemmas3.3,3.4,3.8,3.9.Lemma3.14There exists a super-simple(v,{4,5},2)-PBD for any v=48t+m, m∈[42,47]0,2,t≥0.3Proof:For t=0,1,2,there exists a super-simple(v,{4,5},2)-PBD by Theorem1.3 and Lemmas3.3,3.4,3.8-3.10.For t≥3,we start from a super-simple(5,2)-GDD of type(12t+4)5.Re-moving12t+4−x,x∈[26,31]1,2,points from the last group,we get a super-3simple({4,5},4)-GDD of type(12t+4)4x1.Applying Construction2.3withη= 0,we get a super-simple(v,{4,5},2)-PBD.Here,all these input super-simple (12t+4,{4,5},2)-PBD and(x,{4,5},2)-PBD come from Theorems1.2,1.3and Lemmas3.4,3.9.By some simple computations and a computer exhaustive search,there does not exist a super-simple(v,{4,5},2)-PBD for any v∈{8,9,12,14}.So,combining Theorem1.2and Lemmas3.12-3.14,we have proved Theorem3.1.§3.2λ=4In this section,we shall prove that the necessary conditions for the existence of a super-simple(v,{4,5},4)-PBD are also sufficient except for v=11and pos-sibly except for v=12.Theorem3.15A super-simple(v,{4,5},4)-PBD exists if and only if v≥10except for v=11and possibly except when v=12.First,we shall use direct constructions to obtain super-simple(v,{4,5},4)-PBD for some small values of v.Lemma3.16There exists a super-simple(v,{4,5},4)-PBD for any v∈M={17, 18,23,26,27,29,32,33,36,38,39,42,47,48,59,62,63,66,83}.Proof:For each v∈M,take the point set X=Z v.Instead of listing all the required blocks,we only list the base blocks and all the required blocks can be generated from them by(+1mod v).v=17{0,1,2,6,13}{0,1,3,9,15}{0,1,4,8}{0,2,7,10}v=18:{0,1,2,4,7}{0,1,5,10}{0,1,8,11}{0,2,6,14}{0,2,9,15}v=23{0,1,2,4,7}{0,1,5,9,10}{0,2,8,15}{0,2,11,14}{0,3,10,15}{0,4,11,17}v=26{0,1,2,4,7}{0,1,5,9,11}{0,1,8,15}{0,2,10,16}{0,3,11,16}{0,3,12,17}{0,4,11,17}v=27{0,1,2,4,7}{0,1,5,9,14}{0,1,8,16,18}{0,2,6,14,17}{0,3,14,20}{0,5,11,20}v=29{0,1,3,9,27}{0,1,2,6,13}{0,1,4,14,22}{0,2,10,14,19}{0,3,10,17,23}{0,4,13,18}v=32{0,1,3,9,27}{0,1,2,5,7}{0,1,8,17}{0,2,12,21}{0,3,12,22}{0,3,14,21}{0,4,14,20}{0,4,15,19}{0,5,13,20}v=33{0,1,3,9,27}{0,1,2,5,7}{0,1,8,13,22}{0,2,10,18,21}{0,3,13,20}{0,4,14,23}{0,4,15,20}{0,4,16,22}v=36{0,1,3,9,27}{0,1,2,5,7}{0,1,8,10,20}{0,3,8,21,24} {0,4,13,24}{0,4,14,25}{0,4,17,23}{0,5,16,22}{0,7,14,22}v=38{0,1,3,9,27}{0,1,2,5,7}{0,1,8,10,17}{0,3,10,23,26} {0,4,15,23,28}{0,4,16,25}{0,4,18,26}{0,5,18,24}{0,6,17,27}v=39{0,1,3,9,27}{0,1,2,5,7}{0,1,8,10,17}{0,3,6,16,25} {0,4,15,25}{0,4,16,24}{0,4,17,28}{0,5,18,28}{0,5,19,27}{0,6,20,27}v=42{0,1,3,9,27}{0,1,2,5,7}{0,1,8,10,17}{0,3,12,23,28} {0,3,14,18,30}{0,4,14,22,27}{0,4,17,23,29}{0,7,20,28}{0,10,20,31}v=47{0,1,3,9,27}{0,1,4,12,36}{0,10,21,31}{0,2,4,7} {0,3,7,12}{0,5,11,17}{0,7,15,28}{0,7,23,38}{0,8,25,30}{0,1,14,23}{0,1,18,28}{0,2,16,29}{0,4,19,29}{0,6,19,33}v=48{0,1,3,9,27}{0,10,25,26}{0,4,17,35}{0,2,6,9} {0,3,7,11}{0,5,10,16}{0,7,15,30}{0,9,19,36}{0,9,22,34}{0,10,24,26}{0,1,20,21}{0,3,14,35}{0,1,17,19}{0,5,19,25}{0,5,33,41}v=59{0,1,3,9,27}{0,1,4,12,36}{0,13,26,43}{0,5,22,45} {0,3,7,12}{0,5,11,17}{0,7,14,22}{0,8,17,27}{0,9,20,30}{0,10,20,38}{0,11,31,44}{0,12,25,44}{0,1,15,31}{0,1,22,24}{0,4,38,45}{0,2,4,30}{0,3,19,25}{0,5,23,39}v=62{0,1,3,9,27}{0,1,4,12,36}{0,13,26,44}{0,5,20,37} {0,3,7,12}{0,5,11,17}{0,7,14,22}{0,8,17,27}{0,9,20,30}{0,10,20,31}{0,12,27,49}{0,13,29,47}{0,1,2,40}{0,4,28,32}{0,2,16,39}{0,2,19,48}{0,3,19,40}{0,5,26,33}{0,6,29,48}v=63{0,1,3,9,27}{0,14,29,44}{0,8,24,40}{0,2,4,7} {0,3,7,12}{0,5,11,17}{0,7,14,22}{0,8,17,27}{0,9,20,30}{0,10,20,31}{0,12,25,41}{0,13,28,42}{0,13,32,50}{0,1,12,40}{0,3,22,43}{0,1,18,38}{0,1,25,29}{0,2,18,35}{0,4,26,40}{0,5,30,36}v=66{0,1,3,9,27}{0,15,32,48}{0,4,22,42}{0,2,4,7}{0,3,7,12}{0,5,11,17}{0,7,14,22}{0,8,17,27}{0,9,20,30}{0,10,20,31}{0,12,25,38}{0,13,27,47}{0,13,29,43}{0,14,30,47}{0,1,16,37}{0,3,38,44}{0,1,19,41}{0,1,24,32}{0,2,25,37}{0,4,28,43}{0,5,26,27}v=83{0,1,3,9,27}{0,1,4,12,36}{0,18,41,60}{0,6,29,54}{0,5,24,60}{0,3,33,37}{0,5,11,46}{0,8,17,27}{0,9,20,30}{0,10,20,31}{0,12,25,38}{0,13,27,40}{0,14,28,43}{0,15,30,46}{0,16,32,49}{0,16,34,58}{0,17,36,57}{0,18,40,62}{0,1,2,34}{0,4,33,61}{0,2,7,68}{0,2,9,47}{0,3,7,55}{0,5,30,44}{0,6,37,44}{0,8,20,71}To show that there exists a super-simple(107,{4,5},4)-PBD,we need the follow-ing super-simple({4,5},4;23,2)-IPBD.Lemma3.17There exists a super-simple({4,5},4;23,2)-IPBD.Proof:Let the point set X=Z21∪{∞1,∞2}.All the required blocks will be gen-erated from the base blocks{0,3,9,13,∞1},{0,1,2,4,7},{0,1,5,9}{0,3,10,15,∞2}, {0,1,8,10},{0,2,10,16}by+1mod21.Lemma3.18There exists a super-simple(107,{4,5},4)-PBD.Proof:Starting from a super-simple(5,2)-GDD of type75which exists by Lemma 3.5.Applying Constructing2.1with a super-simple(5,2)-GDD of type35from Lemma3.5,we obtain a super-simple(5,4)-GDD of type215.Then applying Con-struction2.5with a super-simple(21,{4,5},4)-PBD coming from Theorem1.3anda super-simple({4,5},4;23,2)-IPBD coming from Lemma3.17,we obtain a super-simple(107,{4,5},4)-PBD.Lemma3.19There exists a super-simple(v,{4,5},4)-PBD for any v≡0,4(mod10) and v≥14.Proof:By Theorem1.3,there exists a super-simple(v,5,4)-BIBD for any v≡1,5 (mod10)and v≥15.Applying Lemma3.6with k=5andλ=4,we can get a super-simple(v,{4,5},4)-PBD for any v≡0,4(mod10)and v≥14.。