稠密图分解和凯莱图分解中若干组合设计问题研究

Dense graph decomposition and Cayley graph decomposition are two hot topics in the research of combinatorics and graph theory. Dense graph decomposition is related to the asymptotic existence of combinatorial configu- rations, while Cayley graph decomposition is concerned about the existence of specific combinatorial structures. We shall focus on design theory aspects related to dense graph and Cayley graph decompositions. Combining the techniques from design theory, random graph theory and algebraic graph theory would be effective to solve the problems we shall discuss in this project. The main interests in the project include: investigate Gustavsson conjecture on dense graph decomposition; discuss the completion of partial Latin squares; discuss Cayley graph decomposition admitting automorphism groups; establish new constructions for polygonal designs and two-dimentional balanced sampling plans; give their applications to network, information security and statistics. This project will be helpful to promote interplay among branches of combinatorcs and supply more ideas to deal with the problems on combinatorial design theory.

稠密图的分解和凯莱图的分解是组合与图论研究领域的热点课题，前者涉及组合构型的渐进存在性，后者涉及具体组合结构的存在性。本项目旨在利用组合设计的理论及研究方法，结合随机图论、代数图论等多个组合学分支学科的技术特点，讨论稠密图的分解和凯莱图的分解，解决与这些问题密切相关的组合设计问题，主要内容包括：研究关于稠密图分解的Gustavsson猜想，解决与Gustavsson猜想相关的组合设计问题，如部分拉丁方的完成问题等；研究具有特殊自同构群的凯莱图的分解问题，讨论多边形设计和二维平衡样本设计的构造方法，讨论其在网络、信息安全、统计等领域中的应用。本项目有助于推动组合学各分支学科间的交叉和渗透，为组合设计问题的研究提供多种可能的方法和手段。

本项目旨在利用组合设计的理论及研究方法，讨论稠密图的分解和凯莱图的分解，解决与这些问题密切相关的组合设计问题。本项目研究了稠密图 (K3+e)-分解的最小点度条件；基于对关于稠密图分解的Gustavsson定理的思考，刻画了几类最大填充所有可能的余图与最小覆盖所有可能的溢图；讨论了具有三种不同邻近策略的二维不含邻近单元的平衡样本设计的构造方法和存在性；研究了几类具有特殊自同构群的凯莱图的分解，并将结果用于构造最优（二维）光正交码、最优光正交签名码、最优常复合码、最优跳频序列和最优等差避免冲突码等。项目实施四年间，项目组成员努力与国内外同行合作交流，在《Finite Fields and Their Appl.》、《Des. Codes Crypto.》、《J. Combin. Designs》、《Discrete Math.》、《Science China Math.》、《IEEE Trans. Inform. Theory》、《Graphs and Combin.》等国内外重要学术期刊发表SCI检索论文11篇，中文核心期刊论文2篇，已接收即将见刊的SCI检索论文4篇，合计17篇。