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

这一建议的中心问题是Pfaffian图的刻画。Pfaffian图很重要，因为完美匹配的计数问题在Pfaffian图中可以在多项式时间内解决，而对于一般图来说，相应的问题是#P-完全的。在对Pfaffian图的结构刻画的其他方法中，Pi建议继续他在一般匹配次论方面的工作，该理论类似于Robertson和Seymour的著名的图次要理论。这样的理论将有许多潜在的理论和算法应用，而不仅仅是法菲图理论。他还建议继续研究其他三种类型的图论问题。第一个问题与四色定理有关，这是一个悬而未决了一百多年的问题，是现代图论的核心。第二类问题涉及圆染色，这是近年来被广泛研究的一个相对较新的概念，对图染色理论具有实际动机和理论应用。第三，对黎曼曲面理论中的结果进行了图论类比研究。PI与Matthew Baker合作，最近已经能够证明关于图的Riemann-Roch定理。黎曼-罗赫定理被广泛认为是黎曼曲面理论中最重要的结果。它的类比的发现揭示了黎曼曲面与图之间的一种有趣的联系，并导致了图论以外的潜在应用的进一步公开问题。图论可以用来对不同领域的各种对象进行建模，从电话网络和互联网到分子结构和晶格。该方案中考虑的问题在物理、化学和计算机科学中都有应用，也可能在周期调度和计算机芯片设计等实际问题中应用。在提出的研究问题上取得成果将促进我们对这些应用的理解。

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.