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

这一建议涉及理论数学的基础研究，特别是在图论领域。有三个主要方面：图的小闭集、图的方向和图的交叉数。著名的Robertson和Seymour的图次定理断言所有图的集合在次运算下是很好的拟有序的。Nash-Williams证明了一个关于树的更强的结果，这意味着树的小闭集在包含下也是准有序的。本课题的主要目标是证明具有有界树宽的图的小闭集在包含下是很好的拟有序的。Tutte推测，每个4边连通图的边都有一个方向，使得对于每个顶点v，指向v的有向边的数量与指向v的有向边的数量（取3模）相等。Thomassen用8边连通代替4边连通证明了这一结论的推广。Lovasz等人改进了对6边连通图的推广，Lai证明了对4边连通平面图的推广是错误的。与Thomassen和Younger一起，我们证明了5边连通的平面图。一个主要的目标是证明Thomassen的泛化适用于所有的5边连通图；这就意味着Tutte的猜想是正确的。图G的交叉数cr(G)是平面上所有G图中G的成对交叉数最少的。有n个顶点的完全图K(n)的交叉数是未知的。关于cr（K(n)）的值有一个长期存在的猜想，但这只通过n=12（通过计算机）得到了验证。（一个简单的计数论证表明，最小的反例将有n个奇数。）我们最近发现了一个不用计算机的证明，证明cr（K(9)）是36。一个长期的目标是发展这些技术来确定K(n)的交叉数。这项研究的动机部分来自于现实世界中出现的基础问题，比如电路设计和网络可靠性，但更关注的是理论计算机科学家和数学家感兴趣的问题。它的主要目的是提高我们对图论及其与拓扑学关系的基本知识。

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.