几类图分解问题的组合构型研究

The graph decomposition problem is a hot topic in the fields of graph theory and combinatorics. The project aims to investigate some special graph decomposition problems and the related combinatorial designs. The methods from design theory and the tools such as algebraic graph theory, finite fields and number theory would be applied to solve the problems. The main contents of the project include: discuss i-perfect cycle and Steiner cycle decompositions of the complete graph; discuss cycle decompositions of the multipartite graph and Hamiltonian cycle decompositions; investigate cycle decompositions of the complete graph minus a 1-factor; investigate the maximum packing designs for cycle decompositions of the related graphs; study the balanced sampling plans avoiding adjacent units admitting automorphism groups, such as packing designs of circular or linear balanced sampling plans, two dimensional semicyclic or resolvable balanced sampling plans, and asymptotic existence results of two dimensional balanced sampling plans avoiding adjacent units; give the applications of balanced sampling plans to graph theory, statistics and combinatorial coding theory.

图分解问题是图论与组合领域的一个热门研究问题。本项目拟利用组合设计的理论和方法，结合代数图论、有限域和数论等工具，研究几类特殊的图分解问题以及与之紧密联系的组合设计问题。具体研究内容有：讨论完全图的i-完美圈分解和斯坦纳圈分解问题；讨论多部图的圈分解和哈密尔顿圈分解问题；研究完全图减去1-因子的圈分解问题；研究相关图的圈分解的最大填充设计；研究在特殊自同构群作用下的不含邻近单元的平衡样本设计，包括循环的、线性的等条件下平衡样本设计的填充设计，半循环的、可分解的等条件下的二维平衡样本设计，以及二维不含邻近单元的平衡样本设计的渐近存在性；给出平衡样本设计在图论、统计、组合编码学等领域的应用。

本项目主要研究与几类特殊图分解密切联系的组合设计问题，同时给出相关的编码理论上的应用。项目的主要研究成果如下：探讨了强差族的存在性和构造性问题，给出新的2-设计的离散例子和渐进存在性结果，包括相对差族、frame差族、可分解平衡不完全区组设计；解决了与循环斯坦纳三元系相关的Novák猜想；推广了partitionable set的结果，建立其与惠斯特竞赛设计之间的联系；证明了区组大小为3的半循环带洞可分组设计存在的充要条件；讨论了有限交换群上的五行差阵，证明了广义二面体群上四行差阵的存在谱；给出了重量是3的最优光正交签名码的构造；建立了互相关系数为1的二维最优光正交码及相关的等差冲突避免码存在的无穷类；研究了区组大小为4的循环平衡样本设计的存在性；完全解决了三个kite系统的相交数问题。目前为止，本研究共完成学术论文18篇，其中已发表SCI检索论文14篇，在投稿中的论文4篇。