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

图上的普法夫方向、图着色和黎曼曲面理论

• 批准号: 0803214
• 负责人: Sergey Norin
• 金额: $ 10.33万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0803214&HistoricalAwards=false
• 关键词: Pfaffian; orientations; graph; coloring; theory

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.

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