Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Simon Fraser University

$18,000.00

Structural combinatorics

FY 2010-11

Summary
I intend to pursue a broad research program in combinatorics, encompassing a variety of topics from arithmetic combinatorics to colourings of graphs. Though the subject matter is varied, there is a common theme running throughout: the search for structural explanations to exceptional behavior. Such structure theorems are among the most useful in combinatorics, since they provide us with very strong information when they apply. Perhaps my favorite research topic is the study of small growth/expansion in groups and graphs. Here the central problem is quite easy to state in its most basic form: if A,B are finite subsets of a (multiplicative) group G and |AB| is small relative to |A| and |B|, what can we say about the structure of A,B, and G? Two famous theorems give us powerful answers to this question in special cases. Frieman's Theorem (a founding theorem in arithmetic combinatorics) gives us a rough structure for subsets of integers A for which |A+A| < c|A|. Gromov's Theorem (a founding theorem in geometric group theory) shows that every finitely generated group of polynomial growth has a finite index subgroup which is nilpotent. A major problem in this area is that of unifying these two theorems. Although this goal appears quite far off, there are a variety of more tractable combinatorial problems to solve along the way. I also intend to pursue some structural problems in graph theory. One particularly interesting topic is that of perfect matchings in cubic graphs. Many famous theorems, such as The Four Colour Theorem, Edmond's Matching Polytope Theorem, and Lovasz' Matching Lattice Theorem, give us useful information about this topic. However, our understanding of the behavior of small numbers of perfect matchings is still quite limited, and I believe there is progress to be made here. In addition to this topic, I intend to investigate structural digraph theory, and some problems in graph colouring, and topological graph theory.
Program
Discovery Grants Program - Individual
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
371616-2009
Name nom
DeVos, Matthew
Department département
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
2010
Competition year année de concours
2009
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
337
Committee name en
Pure & Applied Maths - B
Committee name fr
Maths pures et appliquées - B
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
5
Application title
Structural combinatorics
Keyword
NSERC
Application summary
I intend to pursue a broad research program in combinatorics, encompassing a variety of topics from arithmetic combinatorics to colourings of graphs. Though the subject matter is varied, there is a common theme running throughout: the search for structural explanations to exceptional behavior. Such structure theorems are among the most useful in combinatorics, since they provide us with very strong information when they apply. Perhaps my favorite research topic is the study of small growth/expansion in groups and graphs. Here the central problem is quite easy to state in its most basic form: if A,B are finite subsets of a (multiplicative) group G and |AB| is small relative to |A| and |B|, what can we say about the structure of A,B, and G? Two famous theorems give us powerful answers to this question in special cases. Frieman's Theorem (a founding theorem in arithmetic combinatorics) gives us a rough structure for subsets of integers A for which |A+A| < c|A|. Gromov's Theorem (a founding theorem in geometric group theory) shows that every finitely generated group of polynomial growth has a finite index subgroup which is nilpotent. A major problem in this area is that of unifying these two theorems. Although this goal appears quite far off, there are a variety of more tractable combinatorial problems to solve along the way. I also intend to pursue some structural problems in graph theory. One particularly interesting topic is that of perfect matchings in cubic graphs. Many famous theorems, such as The Four Colour Theorem, Edmond's Matching Polytope Theorem, and Lovasz' Matching Lattice Theorem, give us useful information about this topic. However, our understanding of the behavior of small numbers of perfect matchings is still quite limited, and I believe there is progress to be made here. In addition to this topic, I intend to investigate structural digraph theory, and some problems in graph colouring, and topological graph theory.