三个组合问题的研究

In this project, we shall mainly investigate semiframes, packing designs and combinatorial group testing. These combinatorial structures not only have important position in the theoretical research, but also have strong application backgrounds in the fields of communication, computer and so on. Semiframe can be used to obtain constant weight codes, it is the general form of two classical combinatorial designs (resolvable group divisible design and frame). The study of semiframes will promote their unity. Resolvable packing designs can be applied to construct threshold schemes in cryptography. The idea of combinatorial group testing plays an important role in the fields of blood test, digital fingerprint, Molecular biology and so on. On the base of the existing research work, the project shall continue to investigate the existences of semiframes with block sizes 3 and 4, cycle frames with uniform group size and some large sets of packing designs. We also study the constructions and algorithms of group testing and digital fingerprint, then try to apply these ideas to other fields. These combinatorial structures are very important topics with great difficulty in combinatorial mathematics, and attract a lot of attention of combinatorial mathematicians from all over the world. Through the implementation of this project, we hope not only to enrich the theory of combinatorics, but also promote the development on this field and strengthen the connection with other related subjects such as information.

本项目的研究对象主要为准支架、填充设计和组合分组测试，它们不仅在理论研究中有重要的地位，而且在通信和计算机等领域中有很强的应用背景。以等重量码为背景的准支架是两类经典组合设计（可分解的可分组设计和支架）的一般推广形式，其研究可以促进它们的有机统一。可分解的填充设计可以用来构造密码学中的门限方案。组合分组测试的思想方法在血液检验、数字指纹、分子生物等领域都有重要应用。在已有工作基础上，本项目将系统研究区组大小为3和4的准支架的存在性问题；组大小一致的圈支架的存在性问题；部分可分解填充设计的存在性问题；还将研究分组测试和数字指纹之间的组合构造和算法，尝试将分组测试的思想方法应用于其他领域。以上这些问题是组合数学中的重点研究对象，受到国内外学者的普遍关注，需要方法和技术上的突破。通过本项目的实施，不仅能丰富组合数学自身的理论成果，也可促进组合数学和信息等其他学科之间的交叉。

本项目主要研究组合设计理论中带可分解性质设计的存在性问题以及在编码和密码中有重要应用的离散组合结构的存在性问题。这些问题大都是组合及相关领域专业杂志上的公开问题。我们在这些公开问题的研究中取得了一些突破，主要成果如下。在经典设计的存在性方面，完全解决了圈长为任意整数的圈支架的存在性问题（1987年JCT（A）上的公开问题）。解决了圈长为任意奇数的几乎可分解圈设计的存在性问题（2010年Combinatorica上的公开问题），同时也解决了一些圈长为偶数的情形。将几乎可分解设计运用于著名的Hamilton-Waterloo问题的研究，对圈长为{3,4},{3,5},{3,7}的情形，完全解决了HWP解的存在性；对圈长都为奇数的情形, 大大推进了HWP解的存在性研究；几乎解决了圈长含8的Hamilton-Waterloo问题的解的存在性问题。完全解决了区组大小为3的准支架设计的存在性问题（2013年JCD上的公开问题），统一了区组大小为3的可分解GDD和Frame的存在性结果。完全解决了组型一致的爪支架的存在性问题。彻底解决了子图为爪的最大填充和最小覆盖的存在性问题。完全解决了任意相遇数的组型一致的3-GDD大集的存在性问题，并得到相应simple 3-GDD的存在性问题。完全解决了对称带洞拉丁方大集的存在性问题。在以编码和密码为应用背景的离散组合结构的研究方面，关于二元二值自相关序列问题，当周期模4余1时，部分解决了Schmidt 的猜想（2017年DCC上的公开问题）；当周期模4余2时，解决了前人遗留的3个例外；同时得到一些二元二值自相关序列的不存在性结果。在以光正交码为背景的循环设计的研究中，完全解决了n维奇数阶循环填充设计的存在性问题；得到了若干变重量光正交码的存在性结果。关于GSEDF问题，证明了不存在3个子集的GSEDF；给出了一些SEDF的不存在结果；用组合方法给出了GSEDF的第一个递归构造并由此得到一些存在性结果。对小参数的情形，给出了一些最优的可分Hash族；对一般情形，改进了一些最优的可分Hash族的上下界。对在网络缓存中有重要应用的PDA的研究中，利用组合方法给出了PDA的一些构造，并给出界的猜想。