Grant: Discovery Grants Program - Individual
University of Waterloo
$43,000.00
Algorithms and structure in graphs and matroids
FY 2018-19
Summary
This research proposal falls into the context of optimization, combinatorics, and theoretical computer science. We will investigate common generalizations to flows and graphs colouring. We will study the structure of certain minor closed classes of graphs and binary matroids with the aim of finding efficient recognition algorithms. The following is a summary of the projects in the proposal.*Problem A. A quintessential minimax relation is the Max-Flow Min-Cut theorem that 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. Furthermore, there exist efficient algorithms to find a maximum flow. We are interested in generalizing these results to multi-commodity flows and to flows in binary matroids. Two tantalizing conjectures by Seymour on the existence of fractional and integer flows are motivating our work.*Problem B. Wagner proved that graphs without K5 minors can be constructed by pasting planar graphs and one special graph along edges and triangles. A graph G contains K5 as an odd-minor if K5 can be obtained from G by first deleting a subset of the edges and then contracting all the edges on a single cut. We wish to understand the structure of graphs that do not contain K5 as an odd minor. These graphs play a pivotal role in the study of multi-flows in graphs. These graphs can be 4-coloured, a generalization of the 4-color theorem, and feature in several important conjectures on colouring and homomorphisms.*Problem C. Geelen, Gerards, and Whittle proved that any minor closed class of binary matroids can be characterized by a finite set S of excluded minors. Unfortunately, these results only indicate that the set S is finite and provide little guidance on how to obtain it. In an excluded minor characterization we look for an explicit description of S. Finding such characterizations has been a very fruitful area of research in both matroid and graph theory. Our goal is to find excluded minor characterizations and recognition algorithms for both even-cycle and even-cut matroids.*The problems that are outlined in this proposal are widely viewed as important and resolving those would have profound implications. On the other hand some of these conjectures have been open for nearly four decades and are very challenging. We are however, in an enviable position now, as we have developed over the past few years, machinery that should greatly facilitate our projects. Indeed, we are very optimistic that we will be able to settle some long-standing conjectures during the period of this research proposal.*
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2015-04061
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
2018
Competition year année de concours
2015
Award amount
43000
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
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
2956
Research subject group en
Applied mathematics
Research subject group fr
Mathématiques appliquées
Research subject en
Optimisation and optimal control theory
Research subject fr
Optimisation et théories de commande optimale
Partie
4
Nb partie
5
Application title
Algorithms and structure in graphs and matroids
Keyword
NSERC
Application summary
This research proposal falls into the context of optimization, combinatorics, and theoretical computer science. We will investigate common generalizations to flows and graphs colouring. We will study the structure of certain minor closed classes of graphs and binary matroids with the aim of finding efficient recognition algorithms. The following is a summary of the projects in the proposal.*Problem A. A quintessential minimax relation is the Max-Flow Min-Cut theorem that 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. Furthermore, there exist efficient algorithms to find a maximum flow. We are interested in generalizing these results to multi-commodity flows and to flows in binary matroids. Two tantalizing conjectures by Seymour on the existence of fractional and integer flows are motivating our work.*Problem B. Wagner proved that graphs without K5 minors can be constructed by pasting planar graphs and one special graph along edges and triangles. A graph G contains K5 as an odd-minor if K5 can be obtained from G by first deleting a subset of the edges and then contracting all the edges on a single cut. We wish to understand the structure of graphs that do not contain K5 as an odd minor. These graphs play a pivotal role in the study of multi-flows in graphs. These graphs can be 4-coloured, a generalization of the 4-color theorem, and feature in several important conjectures on colouring and homomorphisms.*Problem C. Geelen, Gerards, and Whittle proved that any minor closed class of binary matroids can be characterized by a finite set S of excluded minors. Unfortunately, these results only indicate that the set S is finite and provide little guidance on how to obtain it. In an excluded minor characterization we look for an explicit description of S. Finding such characterizations has been a very fruitful area of research in both matroid and graph theory. Our goal is to find excluded minor characterizations and recognition algorithms for both even-cycle and even-cut matroids.*The problems that are outlined in this proposal are widely viewed as important and resolving those would have profound implications. On the other hand some of these conjectures have been open for nearly four decades and are very challenging. We are however, in an enviable position now, as we have developed over the past few years, machinery that should greatly facilitate our projects. Indeed, we are very optimistic that we will be able to settle some long-standing conjectures during the period of this research proposal.*