Pfaffian orientations, graph coloring and the theory of Riemann surfaces on graphs

这个建议的中心问题是普氏图的特征化。Pfaffian图是重要的，因为Pfaffian图的完美匹配枚举问题可以在多项式时间内解决，而一般图的相应问题是#P-complete。在对Pfaffian图的结构表征的其他方法中，PI建议继续他对一般匹配次要理论的研究，这是Robertson和Seymour著名的图次要理论的类似物。这样的理论将有许多潜在的理论和算法的应用，超出了普氏图的理论。PI还建议继续他对其他三种图论问题的研究。第一个与四色定理有关，这是一个一百多年来一直悬而未决的问题，是现代图论的核心。第二类问题涉及圆形着色，这是一个相对较新的概念，近年来得到了广泛的研究，对图着色理论既有实际动机又有理论应用。第三，提出了黎曼曲面理论结果的图论类似物的研究。PI与马修·贝克（Matthew Baker）合作，最近证明了图的黎曼-洛克定理。黎曼-洛克定理被广泛认为是黎曼曲面理论中最重要的结果。它的类似物的发现证明了黎曼曲面和图之间的有趣联系，并导致了图论之外潜在应用的进一步开放问题。这项工作属于图论领域。图论可以用来模拟不同领域的各种对象，从电话网络和互联网到分子结构和晶格。本提案所考虑的问题在物理、化学和计算机科学中都有应用，在周期性调度和计算机芯片设计等实际问题中也有潜在的应用。在提出的研究问题上取得成果将促进我们对这些应用的理解。

The central problem of this proposal is characterization of Pfaffian graphs. Pfaffian graphs are important as the problem of enumeration of perfect matchings can be solved in polynomial time in a Pfaffian graph, while the corresponding problem for general graphs is #P-complete. Among other approaches to structural characterization of Pfaffian graphs, the PI proposes to continue his work on a general matching minor theory, an analogue of celebrated graph minor theory of Robertson and Seymour. Such a theory would have many potential theoretical and algorithmic applications beyond the theory of Pfaffian graphs. The PI also proposes to continue his research on three other types of graph theoretical problems. The first one is connected to the Four Color Theorem, a problem that remained open for over a hundred years and lies at the heart of the modern graph theory. The second type of problems involves circular colorings, a relatively new concept that has been studied extensively in recent years and has both practical motivations and theoretical applications to the theory of graph coloring. Thirdly, the investigation of graph theoretical analogues of the results in the theory of Riemann surfaces is proposed. The PI, in collaboration with Matthew Baker, has recently been able to prove a Riemann-Roch theorem for graphs. The Riemann-Roch theorem is widely regarded as the most important result in the theory of Riemann surfaces. The discovery of its analogue demonstrated an interesting connection between Riemann surfaces and graphs and led to further open problems with potential applications outside graph theory.This work belongs to the area of graph theory. Graph theory can be used to model various objects in diverse fields, ranging from telephone networks and Internet to molecular structures and crystal lattices. The problems considered in this proposal have applications in physics, chemistry and computer science, as well as potential applications to practical problems of periodic scheduling and computer chip design. Achieving results on the proposed research problems would advance our understanding of these applications.