论文部分内容阅读
假设m;t均为整数,且满足0 < t · m, 一个(m; t)-分裂系(记作(m; t)-SS)是一个两元组(X; B), X是一个m元集合,B是X的子集构成的集合,其中的元素称为区组(blocks),对于每一个YμX ,jYj = t, 存在区组B2B使得jBYj=bt=2c或者j(XnB)Yj=bt=2c。
假设m; t1; t2 均为整数,且满足0< t1 + t2 · m,一个(m; t1; t2)-分隔系(记作(m; t1; t2)-SEPS) 是一个两元组(X; B),jXj = m , B是X的子集构成的集合,其中的元素称为区组(blocks),对每一个子集PμX; QμX ,jPj = t1; jQj = t2 ; PQ = á, 都存在区组B2B使得PμB; QB = á或者Q μ B; PB=á。
一个分裂系或者分隔系被称为均匀的,如果每一个区组含有相同的元素个数bm=2c。
本文首先讨论了分隔系的一些基本性质,并借助于分隔系这一有力的工具,给出了分裂系的若干构造方法,包括直接构造法和间接构造法。在直接构造方法中,给出了Coppersmith 定理的推广;在间接构造方法中,利用各种技巧,给出了包括递归和积构造等多种方法。最后利用概率方法,给出了分裂系存在的一个充分条件并对一般的t 给出了分裂系大小的一个上界,并且当m >> t 时,此上界优于[1]中给出的上界。本文主要关心t= 5 和t= 6这两种情况。