Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$18,000.00

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

FY 2014-15

Summary
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.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2014-03750
Name nom
Richter, Bruce
Department département
Combinatorics & Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2014
Competition year année de concours
2014
Award amount
18000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Partie
1
Nb partie
5
Application title
Ideals of graphs, graph orientations, and crossing numbers of graphs
Keyword
NSERC
Application summary
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.