Ideals of graphs, graph orientations, and crossing numbers of graphs

图的理想、图的方向和图的交叉数

• 批准号: RGPIN-2014-03750
• 负责人: Richter, Bruce
• 金额: $ 1.31万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=610628
• 关键词: Ideals; graphs; graph; orientations; crossing

This proposal concerns basic research in theoretical mathematics, particularly in the area of graph theory. There are three principal aspects: minor-closed sets of graphs, orientations of graphs, and crossing numbers of graphs. The famous Graph Minor Theorem of Robertson and Seymour asserts that the set of all graphs is well quasi-ordered under the minor operation. Nash-Williams proved a much stronger result about trees, which implies that minor-closed sets of trees are also well quasi-ordered under inclusion. A major goal of this project is to prove that minor-closed sets of graphs with bounded tree-width are well quasi-ordered under inclusion. Tutte conjectured that every 4-edge-connected graph has an orientation of its edges so that, for each vertex v, the number of directed edges pointing in to v is congruent (mod 3) to the number of directed edges pointing out from v. Thomassen proved a generalization of this with 4-edge-connected replaced by 8-edge-connected. Lovasz et al improved the generalization to 6-edge-connected graphs and Lai showed it false for 4-edge-connected planar graphs. With Thomassen and Younger, we proved it for 5-edge-connected planar graphs. A major goal is to prove that Thomassen's generalization holds for all 5-edge-connected graphs; this would imply Tutte's conjecture is true. The crossing number cr(G) of a graph G is the fewest number of pairwise crossings of G among all drawings of G in the plane. The crossing number of the complete graph K(n) with n vertices is not yet known. There is a long-standing conjecture for the value of cr(K(n)), but this has been verified (by computer) only through n=12. (A simple counting argument shows that the smallest counterexample will have n odd.) We have recently found a computer-free proof that cr(K(9)) is 36. A long-term goal is to develop these techniques to determine the crossing number of K(n). The research is motivated in part by foundational issues that arise in real-world topics, such as circuit design and reliability of networks, but is more concerned with issues of interest to theoretical computer scientists and mathematicians. Its principal purpose is to advance our fundamental knowledge of graph theory and its relationship to topology.

这一建议涉及理论数学的基础研究，特别是在图论领域。有三个主要方面：图的小闭集、图的方向和图的交叉数。