(m;5) 和（m;6）-分裂系的构造方法

论文摘要

假设m, t均为整数,且满足0 < t≤m,一个（m,t）-分裂系（记作（m,t）-SS）是一个两元组（X,B）, X是一个m元集合, B是X的子集构成的集合,其中的元素称为区组（blocks）,对于每一个Y ? X ,|Y | = t,存在区组B∈B使得|B∩Y | = t/2或者|（XB）∩Y | = t/2。假设m, t1, t2均为整数,且满足0 < t1 + t2≤m,一个（m,t1,t2）-分隔系（记作（m,t1,t2）-SEPS）是一个两元组（X,B）, |X| = m , B是X的子集构成的集合,其中的元素称为区组（blocks）,对每一个子集P ? X, Q ? X ,|P| = t1, |Q| = t2 , P∩Q =φ,都存在区组B∈B使得P ? B, Q∩B =φ或者Q ? B, P∩B =φ。一个分裂系或者分隔系被称为均匀的,如果每一个区组含有相同的元素个数m/2。本文首先讨论了分隔系的一些基本性质,并借助于分隔系这一有力的工具,给出了分裂系的若干构造方法,包括直接构造法和间接构造法。在直接构造方法中,我们给出了Coppersmith定理的推广;在间接构造方法中,我们利用各种技巧,给出了包括递归和积构造等多种方法。最后利用概率方法,给出了分裂系存在的一个充分条件并对一般的t给出了分裂系大小的一个上界,并且当m >> t时,此上界优于[1]中给出的上界。本文主要关心t = 5和t = 6这两种情况。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 基本介绍
• 1.1.1 分裂系
• 1.1.2 离散对数和分裂系
• 1.1.3 Abelian群上的编解码和分裂系
• 1.1.4 有向连通图和分裂系
• 1.2 本文的主要工作
• 第二章 分隔系的基本性质
• 2.1 定义
• 2.2 分隔系的基本性质
• 第三章 直接构造法
• 3.1 直接构造法
• 3.2 直接构造法示例
• 第四章 间接构造法
• 4.1 递归构造法
• 4.2 积构造法
• 第五章 分裂系的大小
• 5.1 关于下界
• 5.2 关于上界
• 参考文献
• 致谢