若干离散结构的存在性及其应用问题研究

摘要

组合设计理论主要研究各种离散结构的存在性和构造问题，其基本内容、思想和方法与代数、数论、图论和有限几何相互交叉渗透.应用学科如计算机科学、信息科学、统计学、生物信息学等中大量的离散结构问题为组合设计理论提供了广阔的平台和巨大的动力.本论文研究了与统计学、信息科学密切相关的混合正交阵、Frame-GBTD、强可分码等离散结构的存在性及其应用.
　　混合正交阵(MOA)作为正交阵的推广，在试验设计中起重要作用.He-dayat等人在专著《正交阵列理论及其应用》中给出了构作强度为2的MOA的“膨胀替代法”，并提问:对强度t≥3时，该方法是否依然有效？我们在第二章中解决了这个问题，给出了对任意强度t的“膨胀替代法”，并由此获得了一批新的MOA.
　　在第三章中，我们研究了标架广义平衡竞赛设计(Frame-GBTD)的渐近存在性.它因可用于构作最优的符号常重码和常重复合码而被广泛研究.由于Frame-GBTD结构复杂，即使对于k≤5时，已知存在性结果也很少.我们利用Lamken和Wilson的关于边染色完全有向图的分解定理，将Frame-GBTD的存在性问题转化为恰当的图分解问题，从而给出了对于一般的k和g的FGBTD(k，gn)的渐近存在性结果.
　　在第四章中，我们研究了单纯正交阵(SOA).利用组合构作方法，我们证明了当λ≥2时，SOAλ(3，5，v)的存在的必要条件也是充分的，除了确定的例外:v=6且λ=3;v=3且λ=8;v=6且λ=35，和一些可能的例外:v=6且λ∈{3,7,11,13,15,17,19,21,23,25,29,33}.
　　多媒体时代，版权保护尤为重要.多媒体指纹技术就是一种有效的保护多媒体文件版权的技术.作为抗合谋攻击码，如防诬陷码(FPC)和可分码(SC)被引进用于追踪确定攻击者.已经知道，FPC的追踪性能比SC好，可是码字个数（对应于用户个数）却没有SC多.最近Jiang等人引进的强可分码(SSC)具有和FPC一样好的追踪性能，却有比FPC更多的码字个数.目前为止，关于强可分码的结果还很少，仅限于一些长度为2和3的类.在第五章中，我们着重研究最优SSC的码字个数的下界问题.我们运用P.Erd(o)s，N.Alon等人提出的概率方法，证明了SSC的码字个数渐近地趋向SC的码字个数，即给出了SSC码字个数的一个下界.由于SSC的追踪性能比SC好，这就更有力地说明了SSC是比FPC和SC都更好的码.

目录

声明

摘要

第一章 绪论

1．1 相关研究背景

1．2 主要结果

第二章 混合水平正交阵——Hedayat-Sloane-Stufken问题的解

2．1 基本概念

2．2 方法的描述

2．3 一些新的MOA的类

第三章 Frame-GBTD——渐近存在性结果及其图论方法证明

3．1 研究背景及预备知识

3．2 渐近存在性的图论方法证明

3．3 定理3．9的一个应用

第四章 单纯正交阵的构造

4．1 背景及预备知识

4．2 单纯正交阵的构作方法

4．3 主要结果

第五章 强可分码——存在性结果及其概率方法证明

5．1 强可分码的背景

5．2 (2)-SSC的概率下界

5．3 (t)-SSC的概率下界

参考文献

攻读博士期间完成的论文

致谢