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

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

• 批准号: 0701033
• 负责人: Sergey Norin
• 金额: $ 10.33万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2007-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0701033&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.

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