Grant: Discovery Grants Program - Individual
McGill University
$20,000.00
Extremal and Structural Aspects of Graph Minor Theory
FY 2018-19
Summary
The goal of this proposal is systematic investigation of extremal and structural properties of minor-closed classes of graphs. Graph minor theory is a deep and rich area of graph theory, initially developed by Robertson and Seymour in a series of twenty three papers. It continues to be an active area of research with extensive algorithmic applications. Some of the methods developed as part of the theory have been successfully used in practical computations.*One of the central results in graph minor theory is the graph structure theorem of Robertson and Seymour, which gives an approximate structural description of graphs that do not contain a fixed graph as a minor. The PI proposes to continue his ongoing long term joint project with Robin Thomas, the goal of which is a refinement of many aspects of this theory. In particular, one of the goals of the project is to obtain tight bounds on connectivity which guarantees existence of certain minors and related configurations (linkages, topological minors, etc.) in large graphs. *The PI also proposes investigation of extremal aspects of graph minor theory. One of the main goal of the proposal in this direction is to show that the density of every minor-closed class of graphs is attained by graphs of bounded pathwidth. The second goal is to compute density of particular minor-closed classes and develop generic tools for this type of problems.*Finally, the PI proposes to investigate relaxations of Hadwiger's conjecture. Hadwiger's conjecture is a longstanding open problem, which greatly strengthens the four-color theorem. It is possibly the most famous open problem in graph theory. The PI has recently announced a proof, joint with Zdenek Dvorak, of one relaxation of the conjecture, improving on earlier results of Kawarabayshi and Mohar, Wood, and Liu and Oum. The PI proposes to extend this result in several directions, in particular, investigating intriguing connections with bootstrap percolation, a concept investigated in probabilistic combinatorics and theoretical physics.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2017-05010
Name nom
Norin, Sergey
Department département
Mathematics and Statistics
Organization id
61
Institution établissement
McGill University
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2018
Competition year année de concours
2017
Award amount
20000
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
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
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
5
Application title
Extremal and Structural Aspects of Graph Minor Theory
Keyword
NSERC
Application summary
The goal of this proposal is systematic investigation of extremal and structural properties of minor-closed classes of graphs. Graph minor theory is a deep and rich area of graph theory, initially developed by Robertson and Seymour in a series of twenty three papers. It continues to be an active area of research with extensive algorithmic applications. Some of the methods developed as part of the theory have been successfully used in practical computations.*One of the central results in graph minor theory is the graph structure theorem of Robertson and Seymour, which gives an approximate structural description of graphs that do not contain a fixed graph as a minor. The PI proposes to continue his ongoing long term joint project with Robin Thomas, the goal of which is a refinement of many aspects of this theory. In particular, one of the goals of the project is to obtain tight bounds on connectivity which guarantees existence of certain minors and related configurations (linkages, topological minors, etc.) in large graphs. *The PI also proposes investigation of extremal aspects of graph minor theory. One of the main goal of the proposal in this direction is to show that the density of every minor-closed class of graphs is attained by graphs of bounded pathwidth. The second goal is to compute density of particular minor-closed classes and develop generic tools for this type of problems.*Finally, the PI proposes to investigate relaxations of Hadwiger's conjecture. Hadwiger's conjecture is a longstanding open problem, which greatly strengthens the four-color theorem. It is possibly the most famous open problem in graph theory. The PI has recently announced a proof, joint with Zdenek Dvorak, of one relaxation of the conjecture, improving on earlier results of Kawarabayshi and Mohar, Wood, and Liu and Oum. The PI proposes to extend this result in several directions, in particular, investigating intriguing connections with bootstrap percolation, a concept investigated in probabilistic combinatorics and theoretical physics.