论文部分内容阅读
一个(m,t)一分裂系统(简记(m,t)-SS)是一个集合系统(X,B),其中拾|X|m,它满足对任意的t(t≥2)元子集Y（∩）X都能找到一个区组B∈β,使得|B∩Y|=[t/2].本文中,(N;m,t)-SS表示一个含有N个区组的(m,t)一分裂系统,当m,t固定时,N(m,t)表示所有的(N;m,t)一分裂系统中N的最小值.在分裂系统中,称(N(m,t);m,t)-分裂系统是最优的分裂系统. Stinson和Coppersmith把分裂系统应用于低汉明权重离散对数问题的大步小步算法中,此应用中要求N的值越小越好.对于任意整数m,t都存在一个(m/[t/2]);m,t)-SS,因此研究分裂系统的主要工作是研究它的性质和构造,找出最优的分裂系统.2007年,Deng和Stinson研究了分裂系统的一些性质,给出了构造(m,3)-分裂系统的几种方法和N(m,t)≥［log2(m－t+1)]+1(m≥t+1). 本文的工作是应用分裂系统的关联矩阵和其它相关的组合结构研究(m,t)-分裂系统的构造,确定N(m,t)的范围,进一步找出部分最优的分裂系统.主要内容有以下两部分: 第一部分,我们首先通过直接构造(m,t)-分裂系统和N(m,t)的下界确定了N(t+2,t)=3和N(m,2)=[log2m].其次,通过构造([m/2];m,4)-SS得到了[log2(m－3)]+1≤N(m,4)≤[m/2],由(N;m,t,t)-分隔系统构造了(N－1/1/2(2t/2)+1;m,2t)-SS.最后,给出了利用完美hash族构造m,t)-分裂系统的方法,并用此方法构造了(3×4j;52j,3)-SS(j是正整数),(7[m/2];m2,4)-SS,(6[m/2];m2,4)-SS(m是素数方幂)等. 第二部分,针对于t=4的情况,我们通过研究分裂系统的关联矩阵的构造给出(m,4)-分裂系统的一些递归构造,包括间接构造和乘积构造.我们首先利用矩阵的叉积由(N1;m1,4)-SS和(N2;m2,4)-SS构造析取的(N1+N2+m1+m2;m2m1,4)-SS.当n≥7,n≡1,3(mod6),m=n(n－1)/6时,又结合无覆盖集族的性质由(N1;m,4)-SS构造了析取的(2(N1+n);m2,4)-SS.然后,应用矩阵分块和剩余类思想由(m1,4)-SS构造了(km1,4)-SS(k=3,4).当m≡1,3(mod6)时,用平衡不完全区组设计构造了正则的(m2－m/6;m－1/2,m,4)-SS.