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

这项建议涉及理论数学的基础研究，特别是在图论领域。主要有三个方面：图的次闭集、图的方向和图的交叉数。著名的Robertson和Seymour的图小定理断言，所有图的集合在小运算下是良好的拟序的。Nash-Williams证明了关于树的一个更强的结果，这意味着次闭集在包含下也是很好的拟序的。Tutte猜想，每个4边连通图都有一个边的方向，使得对于每个顶点v，指向v的有向边的个数与v中指向v的有向边的个数是一致的(Mod 3)，Thomassen证明了这一点的推广，用8边连通代替了4边连通.Lovasz等人改进了对6-边连通图的推广，Lai证明了对4-边连通平面图的推广是错误的。对于5-边连通平面图，我们用Thomassen和Young证明了这一点。一个主要目的是证明托马森的推广对所有5边连通图都成立，这意味着Tutte猜想是正确的。图G的交叉数cr(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.