Grant: Discovery Grants Program - Individual
University of Waterloo
$17,000.00
Structural problems and minimax relations in graphs and matroids
FY 2013-14
Summary
In this research proposal I plan to investigate the structure of certain minor closed classes of graphs and binary matroids. The particular classes considered arise naturally in the context of combinatorial optimization. The motivation is fourfold: to provide the building blocks for understanding more complex classes of objects; to find common generalizations to flow and coloring results in graphs; to design efficient algorithms to recognize these classes of graphs and matroids; and to show that certain NP-complete problems become polynomial when restricted to these classes of objects. In particular I will investigate the following problems:1) Tutte characterized which matroids arise from graphs. His work had important theoretical implications; it led for instance, to Seymour's decomposition theorem for regular matroids. We want to generalize this result by characterizing two classes of matroids that arise from signed graphs.2) A quintessential minimax relation is the Max-Flow Min-Cut theorem, which states that the largest amount of flow that can be sent between a pair of vertices in a graph is equal to the capacity of the smallest bottleneck separating these vertices. A famous 1977 conjecture by Seymour predicts that the same minimax relation holds for binary matroids that do not either of three special obstructions.3) Graphs that do not contain the complete graph as odd-minors play a pivotal role in the study of multi-commodity flows and graph coloring. A decomposition theorem for this class of graphs remains elusive, however. We wish to attack this problem by reducing it to a special case of the first problem.Each of these problems is widely regarded as important and challenging. An original feature of this proposal is that it highlights a common strategy to attack all three problems.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
238811-2012
Name nom
Guenin, Bertrand
Department département
Combinatorics and 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
2013
Competition year année de concours
2012
Award amount
17000
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
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
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
2
Nb partie
3
Application title
Structural problems and minimax relations in graphs and matroids
Keyword
NSERC
Application summary
In this research proposal I plan to investigate the structure of certain minor closed classes of graphs and binary matroids. The particular classes considered arise naturally in the context of combinatorial optimization. The motivation is fourfold: to provide the building blocks for understanding more complex classes of objects; to find common generalizations to flow and coloring results in graphs; to design efficient algorithms to recognize these classes of graphs and matroids; and to show that certain NP-complete problems become polynomial when restricted to these classes of objects. In particular I will investigate the following problems:1) Tutte characterized which matroids arise from graphs. His work had important theoretical implications; it led for instance, to Seymour's decomposition theorem for regular matroids. We want to generalize this result by characterizing two classes of matroids that arise from signed graphs.2) A quintessential minimax relation is the Max-Flow Min-Cut theorem, which states that the largest amount of flow that can be sent between a pair of vertices in a graph is equal to the capacity of the smallest bottleneck separating these vertices. A famous 1977 conjecture by Seymour predicts that the same minimax relation holds for binary matroids that do not either of three special obstructions.3) Graphs that do not contain the complete graph as odd-minors play a pivotal role in the study of multi-commodity flows and graph coloring. A decomposition theorem for this class of graphs remains elusive, however. We wish to attack this problem by reducing it to a special case of the first problem.Each of these problems is widely regarded as important and challenging. An original feature of this proposal is that it highlights a common strategy to attack all three problems.