Graph Structure, Coloring, Flows and Algorithms

本提案的中心主题是图结构理论及其在着色、流和算法中的应用。更具体地说，主要研究者研究与图的小包含及其相关的图的结构，如有向小关系和匹配小关系，并使用这些结果来解决流和着色问题，以及表征“普法图”的问题。Pfaffian图之所以引起人们的兴趣，是因为它们允许对完美匹配进行有效的计算，而且它们丰富的理论与其他领域有关。这项研究需要开发图结构理论的新工具。特别地，PI提出了对最初由罗伯逊和西摩提出的“社会”概念的深入研究。该理论的应用范围从理论（流猜想，双循环猜想）到更多的算法（曲面上的图和属于适当小闭族的图的着色）。证明四色定理的一个重要方法是“可约性”技术。虽然它对证明是必不可少的，但几乎没有相关的理论。PI试图为四色定理、五流猜想和循环双盖猜想发展这样一个理论。一个成功的可约性理论（如果它存在的话）将有望导致四色定理的无计算机证明，以及五流和循环双盖猜想的证明。这项工作属于图论领域，与理论计算机科学和数学规划（运筹学）密切相关。图是一个抽象的数学概念，用于网络建模，如电话网络、交通网络或互联网。这类网络的研究中出现了各种各样的问题，本提案涉及的是结构性问题。为什么有些网络具有某些特定的理想属性，而另一些则没有？一个令人满意的答案可以有很多应用，从对底层结构的更好理解，到有效算法的设计，再到实际计算。例如，PI早先回答的一个这样的问题解决了1913年Georgia Polya提出的一个问题，它还解决了另一个困扰理论计算机科学家四分之一个世纪的问题，并在经济学中有应用。

The central theme of this proposal is graph structure theory and its applications to coloring, flows and algorithms. More specifically, the principal investigator studies the structure of graphs pertaining to the graph minor inclusion and its relatives, such as the directed minor and matching minor relations, and uses those results to attack flow and coloring problems, as well as the problem of characterizing ``Pfaffian graphs". Pfaffian graphs are of interest because they allow efficient computation of perfect matchings, and their rich theory is related to other areas. This research requires the development of new tools in graph structure theory.In particular, the PI proposes an in-depth study of the notion of ``society", originally introduced by Robertson and Seymour.Applications of the theory range from theoretical (the flow conjectures, the double cycle conjecture) to more algorithmic (coloring graphs on surfaces and graphs belonging to a proper minor-closed family).An important method employed in the proof of the Four-Color Theorem is the technique of ``reducibility". While it is essential for the proof, there is almost no associated theory. The PI attempts to develop such a theory for the Four-Color Theorem, for the 5-Flow Conjecture and for the Cycle Double Cover Conjecture. A successful theory of reducibility (if it exists) will hopefully lead to a computer-free proof of the Four-Color Theorem and to proofs of the 5-Flow and Cycle Double Cover Conjectures.This work falls within the area of graph theory, and is closely related to theoretical computer science and mathematical programming (operations research). A graph is an abstract mathematical notion used to model networks, such as telephone networks, transportation networks or the Internet. Various problems arise in the study of such networks, and this proposal is concerned with problems of structural nature. Why do some networks possess certain specific desirable properties, and others do not? A satisfactory answer can have many applications, ranging from better understanding of the undelying structure, to the design of efficient algorithms, to practical computations. For instance, one such question answered earlier by the PI settles a question of Georgia Polya from 1913, it also solves a different problem that baffled theoretical computer scientists for quarter of a century, and has applications in economics.