Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Simon Fraser University

$42,000.00

Structural Graph Theory and Additive Combinatorics

FY 2023-24

Summary
My primary research area is structural graph theory. This is a deep mathematical subject with important ties to real world problems. For instance, one of the foundational theorems of this subject is the Kuratowski-Wagner Theorem which characterizes exactly which graphs can be drawn in the plane without crossings. Not only is this a beautiful mathematical theorem in its own right, it is also a vital concept when creating circuit boards: The networks that can be constructed on one side of a circuit board are precisely those which have such a drawing. More generally, networks are ubiquitous objects in the modern world (the internet, social networks, road networks, etc.) and abstract theorems which give global information about their structure can be powerful tools. Structural graph theory has developed tremendously over the past half century, and some aspects of this theory are now quite well established and understood. Notably, there is a grand (albeit rough) generalization of the Kuratowski-Wagner theorem due to Robertson and Seymour which gives a global description of all graphs not containing a certain substructure called a forbidden minor. This deep theorem has profound consequences in graph theory, significant connections to other subjects in mathematics, as well as applications in the form of new graph algorithms. Although the structure of graphs with a forbidden minor is now well-established, there are many important avenues still to explore. The primary long-term goal of my research program is to establish powerful new structure theory to transform our understanding of graphs, directed graphs, and other combinatorial objects. One aim is to determine the structure of a graph not containing another type of substructure called a forbidden immersion. This is a natural analogue of the Robertson-Seymour theory that could have similarly broad based impact. Another aim is to improve our structural understanding of small product sets. This is a subject in additive combinatorics which is intimately related to graph theory, but also has important connections to many other parts of mathematics. My short-term objectives are to pursue structure theory in three settings. First, I hope to prove a global structure theorem for any k-edge-connected graph G not containing a fixed graph H of maximum degree k as an immersion. This is an important step in realizing the long-term goal of an effective structure theory for forbidden immersions. A second goal is to establish a strong structure theorem for pairs of sets A,B in a group for which |AB| < |A| + |B| + c for a fixed constant c. Such a theorem would be highly influential within additive combinatorics. Last but not least, I plan to study expansion in graphs by adapting some tools from combinatorial group theory. This is a first step toward a structural understanding of directed graphs with small growth.
Program
Discovery Grants Program - Individual
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2019-06459
Name nom
DeVos, Matthew
Department département
Mathematics - Mathematics
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2019
Award amount
42000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR 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
9999
Research subject group en
Not available
Research subject group fr
Not available
Research subject en
Non disponible
Research subject fr
Non disponible
Application title
Structural Graph Theory and Additive Combinatorics
Keyword
additive combinatorics; approximate subgroup; Cayley graph; digraph; graph structure; immersion; minor; rough structure; small doubling; surface embedding
Application summary
My primary research area is structural graph theory. This is a deep mathematical subject with important ties to real world problems. For instance, one of the foundational theorems of this subject is the Kuratowski-Wagner Theorem which characterizes exactly which graphs can be drawn in the plane without crossings. Not only is this a beautiful mathematical theorem in its own right, it is also a vital concept when creating circuit boards: The networks that can be constructed on one side of a circuit board are precisely those which have such a drawing. More generally, networks are ubiquitous objects in the modern world (the internet, social networks, road networks, etc.) and abstract theorems which give global information about their structure can be powerful tools. Structural graph theory has developed tremendously over the past half century, and some aspects of this theory are now quite well established and understood. Notably, there is a grand (albeit rough) generalization of the Kuratowski-Wagner theorem due to Robertson and Seymour which gives a global description of all graphs not containing a certain substructure called a forbidden minor. This deep theorem has profound consequences in graph theory, significant connections to other subjects in mathematics, as well as applications in the form of new graph algorithms. Although the structure of graphs with a forbidden minor is now well-established, there are many important avenues still to explore. The primary long-term goal of my research program is to establish powerful new structure theory to transform our understanding of graphs, directed graphs, and other combinatorial objects. One aim is to determine the structure of a graph not containing another type of substructure called a forbidden immersion. This is a natural analogue of the Robertson-Seymour theory that could have similarly broad based impact. Another aim is to improve our structural understanding of small product sets. This is a subject in additive combinatorics which is intimately related to graph theory, but also has important connections to many other parts of mathematics. My short-term objectives are to pursue structure theory in three settings. First, I hope to prove a global structure theorem for any k-edge-connected graph G not containing a fixed graph H of maximum degree k as an immersion. This is an important step in realizing the long-term goal of an effective structure theory for forbidden immersions. A second goal is to establish a strong structure theorem for pairs of sets A,B in a group for which |AB| < |A| + |B| + c for a fixed constant c. Such a theorem would be highly influential within additive combinatorics. Last but not least, I plan to study expansion in graphs by adapting some tools from combinatorial group theory. This is a first step toward a structural understanding of directed graphs with small growth.
Simon Fraser University - $42,000 Grant (2023-24) | Canada Spends