完美匹配的性质

Matching theory is one of the core subjects of graph theory and combinatorial optimization. The matching polyhedra theory is a perfect combination of integer programming and graph theory. In this project, the perfect matchings will be studied from two aspects: the polytope of perfect matchings and the structure of perfect matchings. The goal is to obtain innovative results and to increase the applications of the polyhedra theory in graph theory. Centring on Fan-Raspaud Conjecture and Norine-Thomas Conjecture, the following research contents will be investigated: (1) The linear inequalities system and its total dual integrality of special polyhedra. If the system of inequalities which describes Fan-Raspaud Conjecture has an integral solution, then the conjecture should be proved. (2) The structure properties of cubic bricks and the upper bound on the number of vertices of degree 3 in minimal bricks. (3) The recusive approch to perfect matching polytopes of cubic graphs: including the fractional points and the properties of facets of polytopes. (4) The characterizations of graphs with certain perfect matching polytopes: including those with flat, diameter one, simple or simplicial polytopes. These research work will enlarge the bases of recursion, and extend the research field of polyhedra.

匹配理论是图论与组合最优化的核心研究课题之一。匹配多面体是整数规划与图论的完美结合。本项目从多面体和结构性质两个方面探讨完美匹配的性质，目的是做出创新的成果并促进多面体理论在图论中的应用。主要围绕Fan-Raspaud猜想（2-连通三正则图中存在三个完美匹配其交集为空）和Norine-Thomas猜想（存在正数a使得在每个极小砖图中度为3的顶点数至少是a|V|）从以下方面展开研究：（1）特定多面体的线性不等式组表示及其整性。 如果描述Fan-Raspaud猜想的不等式组有整解猜想即得证。（2）三正则砖图的结构性质及极小砖图度为3的顶点数目的上界。（3）三正则图完美匹配多面体的递归性：包括多面体的分数点及各种刻面的性质等。（4）具有特殊完美匹配多面体的三正则图类的刻画：包括平坦的、直径为1的、简单的和单纯的多面体等。进而扩展递归基础，并开拓多面体理论的研究领域。

图论与组合最优化是两个交融渗透，互相促进发展的研究领域。匹配理论是图论与组合最优化的核心课题之一。而匹配多面体是整数规划与图论的完美结合。本项目研究Fan-Raspaud猜想（任一无割边的三正则图中都存在三个完美匹配其交集是空集）、与完美匹配多面体和圈结构相关的完美匹配问题。研究成果如下：受本项目资助共发表学术论文19篇，其中16篇论文发表于SCI期刊上。此外，关于该项目的研究内容接收待发表论文1篇，投稿在审论文2篇。本项目取得的代表性成果如下：（1）对完美匹配多面体组合直径为1的实心砖图（solid brick）给出了完全刻画。在这个结果的基础上进一步对Birkhoff-von Neumann图和完美匹配多面体组合直径为1的图的交集的给出了完全的刻画。论文被《SIAM Journal on Discrete Mathematics》接收待发表。这个成果对于我们进一步刻画完美匹配多面体组合直径为1的图和Birkhoff-von Neumann图这两类图具有重要意义。（2）对Fan-Raspaud猜想，含有有四个奇圈构成的2-因子的无桥三正则图，1-哈密尔顿图和2-哈密尔顿图，我们证明猜想成立。 此外，我们把猜想中的“存在三个完美匹配其交为空集”的性质放在更大的图类匹配覆盖图上研究，得到具有这种性质的匹配覆盖图的一个充分必要条件，利用这个条件刻画了一些图类。这开辟了关于完美匹配性质研究的一个新专题。（3）在研究过程中，我们注意到完美匹配交错圈与完美匹配的研究有着密切的关系。对圈强迫的二部图、三正则无爪图给出了刻画，对导出圈友好的三正则无爪图，对圈友好的平面无爪图、弦图给出了刻画