多部竞赛图和正则有向图中的顶点不交圈

Cycles in graph theory have received extensive attention and the existence of vertex-disjoint cycles is one of its important branches. Bermond and Thomassen conjectured in 1981 that every digraph with minimum outdegree at least 2k-1 contains at least k vertex-disjoint directed cycles, where k is a positive integer. This is one of the 100 famous conjectures selected by Bondy and Murty in their well-known book 《Graph Theory》. This project will focus on the above conjecture and study the existence of vertex-disjoint directed cycles with and without length constraints in digraphs. The following topics are included: (1) the verification of Bermond-Thomassen conjecture in multipartite tournaments and regular digraphs; (2) the existence of vertex-disjoint cycles of prescribed lengths in multipartite tournaments; (3) the existence of vertex-disjoint cycles of distinct lengths in regular digraphs. The structural analysis, probabilistic method, Chernoff bound, Lovász Lecal Lemma and Regularity Lemma will be used for considering the problems mentioned above. These research work is expected to provide effective ideas for solving the above conjecture and obtaining the conditions for the existence of vertex-disjoint cycles with different length constraints in digraphs.

圈问题在图论研究中受到广泛关注，顶点不交圈的存在性是其中一个重要分支。1981年，Bermond 和 Thomassen 猜想最小出度不小于 2k-1 的有向图包含 k 个顶点不交圈，其中 k 是正整数。这个猜想被收录在 Bondy 和 Murty 经典专著《Graph Theory》中所列的100个著名猜想集中。本项目围绕该猜想研究有向图中任意长度顶点不交圈和限定长度顶点不交圈的存在条件。主要研究内容如下：一、验证多部竞赛图和正则有向中猜想的成立性；二、刻画多部竞赛图中给定长度顶点不交圈的存在条件；三、刻画正则有向图中不同长度顶点不交圈的存在条件。对本项目的研究将以 Chernoff 不等式、Lovász 局部引理和正则性引理为工具，综合应用结构分析方法和概率方法，上述工作期望为解决 Bermond-Thomassen 猜想和刻画出有向图中限定长度顶点不交圈的存在条件提供有效的研究思路。

圈问题和划分问题是图论研究中的热点问题。1981年，Bermond 和 Thomassen 猜想最小出度不小于 2k-1 的有向图包含 k 个顶点不交圈，这个猜想被收录在 Bondy 和 Murty 经典专著《Graph Theory》中所列的100个著名猜想集中。2006年，世界数学家大会1小时报告人、以色列科学院院士 Alon 在 [Combinatorics, Probability and Computing 15 (2006) 933–937] 中猜想存在有限的函数 f(k) 使得最小出度不小于 f(k) 的有向图可以划分为两个导出子图，每个导出子图的最小出度不小于k。本项目围绕上述两个猜想研究有向图中顶点不交圈问题和出度划分问题。主要研究结果如下：一、给出了 Bermond-Thomassen 猜想在 k=3 情况下成立的证明；二、解决了欧洲图论学者 Bang-Jensen, Bessy 和 Thomasse 于2014年在图论领域权威 SCI 源期刊 [Journal of Grpah Theory 75 (2014) 284-302] 中提出的关于顶点不交圈数目的一个公开猜想；三、证明了 Alon 猜想在竞赛图、多部竞赛图、正则有向图等图类中成立。对上述内容的研究综合应用了结构分析方法、概率方法、Lovász 局部引理等，上述工作为最终解决 Bermond-Thomassen 猜想和 Alon 猜想提供了有效的研究思路。