基于图与超图的匹配中的若干问题的研究

Matching theory and the theory of degree constrained factors in graph theory, which was first studied by Tutte, and then developed by Lovasz etc. who was awarded the Wolf Prize, is always one of the main research fields in graph theory. Recently, matchings in hypergraphs has attracted much attention of scholars including Professor R?dl, a member of both the US National Academy of Sciences and the European Academy of Sciences. R?dl emphatically introduced a degree condition for the existence of perfect matchings in hypergraphs in a survey on hypergraphs in 2010. The goal of this project is to investigate non-consecutive degree constrained factor problems in graph theory and some problems in matchings of hypergraphs. First, we will study on the structure theory of degree constrained factors of graphs. By applying H-factor structure theory we will try to tackle some open problems in the theory of degree constrained factors. Second, we will study on the matching and factor problems of hypergraphs. We will mainly focus on exploring the relation between various degree conditions of k-uniform hypergraphs and k-partite k-uniform hypergraphs and the existence of their matchings, as well as the relation between the existence of restricted perfect matchings of a k-uniform hypergraphand its mimimum degree. Meanwhile, some sufficient conditions for the existence of matchings and restricted perfect matchings of a hypergraph will be presented according to its minimum degree. The results of this research will enhance the understanding of the structure theory of non-consecutive degree constrained factors of graphs and matching problems in hypergraphs, and boost the domestic research on these topics.

图的匹配及图的度约束因子理论最早由Tutte展开研究，并被沃尔夫奖得主Lovasz等发展，一直是图论中的热门和重点研究方向之一。近年来，超图的匹配问题受到包括美国与欧洲双科院士R?dl教授等人的关注。Rodl教授在2010年关于超图综述中着重介绍了超图的完美匹配存在性的度条件。 本项目旨在研究图的不连续的度约束因子问题及超图的匹配中的一些问题。首先，项目拟研究图的度约束因子的结构理论，采用H-因子结构理论研究度约束因子理论中的一些公开问题；其次项目申请人拟进行超图的匹配及超图的因子问题的研究，主要研究k-超图及k-分k-超图的各种度条件与其匹配的存在性之间的关系及k-超图的限制完美匹配与其最小度之间的关系，拟依据超图的最小度给出匹配及限制匹配存在性的一些充分条件。 本项目的研究成果将有助于研究者更好的理解图的间隔至多为一的度约束因子的结构理论及超图的匹配问题，能增强国内在该方向上的研究。

图的匹配及图的度约束因子理论一直是图论中的热门和重点研究方向之一。特别地，图与超图的匹配问题最近受到包括美国与欧洲双科院士Rödl教授等国际著名组合数学学者的关注。Rödl教授在2010年关于超图综述中着重介绍了超图的完美匹配存在性的度条件。.项目组成员成员研究了图与超图的匹配及图的度约束因子的存在性问题。在本项目支持下，项目组成员解决了图与超图匹配及图的度约束因子领域的一些公开问题，并在超图的匹配研究领域获得方法上的突破，主要研究成果有：与佐治亚理工学院郁星星教授等合作解决了Rodl教授在其综述中所提关于k-分k-超图匹配与几乎完美匹配的存在性问题；与郁星星教授合作解决了世界数学家大会45分钟报告人Sudakov所提的彩虹匹配问题，并在以色列海法大学Ahroni的彩虹匹配猜想上获得一些研究进展；与北京理工大学王国亮副教授合作解决了日本图论专家Kano教授1988年所提的公开问题；与郁星星教授合作，在超图的匹配存在性研究方面获得新的方法上的突破，有望在该研究领域获得一系列研究成果。.通过本项目的实施，团队成员进入超图匹配这一国际上热门的研究领域，并解决了一些该领域的公开难题，研究成果具有国际影响力，增强国内在该领域的研究。