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

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

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.