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

点击翻译按钮获取中文摘要

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.