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

项目名称： 稠密图分解和凯莱图分解中若干组合设计问题研究

项目编号： No.11471032

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 数理科学和化学

项目作者： 冯弢

作者单位： 北京交通大学

项目金额： 60万元

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

中文关键词： 稠密图；凯莱图；图分解；拉丁方；平衡样本设计

英文摘要： 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.

英文关键词： dense graph;Cayley graph;graph decomposition;Latin square;balanced sampling plans