Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Simon Fraser University

$18,000.00

Structural Combinatorics

FY 2016-17

Summary
I pursue a broad research program in combinatorics which is themed by the search for structural understanding of exceptional phenomena. This summary is divided according to the major topics which I intend to study over the next 5 years. Combinatorial Number Theory One of the fundamental problems in this subject is to describe finite subsets A,B of a (multiplicative) group for which the product set AB has small size. The first deep contribution to this program (for G=Z) was due to Freiman, and subsequently refined by Ruzsa. Recent work by numerous authors have revealed the significance of this problem to the world of additive combinatorics and beyond. A new breakthrough by Breulliard, Green, and Tao gives a powerful rough structure theorem which applies in arbitrary groups. However, much work remains to be done to gain a more precise understanding. My work in this area concerns the extreme case when |AB| is very small (in this realm the subject is highly combinatorial). In the case when |AB| < |A| + |B|, I have recently completed a precise structure theorem describing the sets. Together with my Ph.D. student, Tom Boothby, we have begun to characterize those sets with |AB| = |A| + |B|, and going forward, I hope to pursue the structure of sets with |AB| < |A| + |B| + c for a fixed constant c. A rough structure theorem for this case would be extremely useful in (mathematical) applications. There many crossovers between graph theory and additive number theory, and I am especially interested in this connection. Together with Mohar, I have proved a rough structure theorem for small separations in vertex transitive graphs which has applications in both graph theory and combinatorial number theory. There are numerous directions to push forward here (ex. a generalization to digraphs) which I believe would make suitable projects for students. Another crossover problem is to give bounds on the average degree of a power of a regular graph. Together with McDonald and Scheide, I have recently proved a tight bound on this for powers which are 2 (mod 3). Extending these results from graphs to digraphs would be extremely valuable for both extremal graph theory and additive combinatorics. Graph Immersion Immersion is a natural containment operation in graphs which has received relatively little attention in comparison to graph minors. Robertson and Seymour have famously shown that graphs are well-quasi-ordered under immersion, but very little is understood about structural properties of this relation. Recently I have collaborated with various groups of colleagues to study immersion. Our most notable results include a theorem demonstrating that every simple graph of minimum degree 200t immerses the complete graph K_t and a rough structure theorem for graphs which do not immerse a given graph. There are numerous important directions for future research here. Indeed, I am working on such problems at present with two Masters students. Together with Mahdieh Malekian (and McDonald) we are working toward a precise characterization of the graphs which do not immerse K_5 or K_{3,3}, and together with Stefan Hannie (and Mohar and Archdeacon) we are studying immersion of 2-regular digraphs. Matroid Minors The matroid minors project of Geelen, Gerards, and Whittle has established a powerful theory of matroids which are representable over a fixed finite field. This work also has promoted the study of certain matroids which are quite close to graphs called frame matroids. As a first step toward understanding these matroids, my Ph.D. student Daryl Funk and Goddyn and I have proved a representation theorem for these matroids which we believe will be useful in understanding their structure, our eventual goal.
Program
Discovery Grants Program - Individual
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2014-06301
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
2016
Competition year année de concours
2014
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
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
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
3
Nb partie
5
Application title
Structural Combinatorics
Keyword
NSERC
Application summary
I pursue a broad research program in combinatorics which is themed by the search for structural understanding of exceptional phenomena. This summary is divided according to the major topics which I intend to study over the next 5 years. Combinatorial Number Theory One of the fundamental problems in this subject is to describe finite subsets A,B of a (multiplicative) group for which the product set AB has small size. The first deep contribution to this program (for G=Z) was due to Freiman, and subsequently refined by Ruzsa. Recent work by numerous authors have revealed the significance of this problem to the world of additive combinatorics and beyond. A new breakthrough by Breulliard, Green, and Tao gives a powerful rough structure theorem which applies in arbitrary groups. However, much work remains to be done to gain a more precise understanding. My work in this area concerns the extreme case when |AB| is very small (in this realm the subject is highly combinatorial). In the case when |AB| < |A| + |B|, I have recently completed a precise structure theorem describing the sets. Together with my Ph.D. student, Tom Boothby, we have begun to characterize those sets with |AB| = |A| + |B|, and going forward, I hope to pursue the structure of sets with |AB| < |A| + |B| + c for a fixed constant c. A rough structure theorem for this case would be extremely useful in (mathematical) applications. There many crossovers between graph theory and additive number theory, and I am especially interested in this connection. Together with Mohar, I have proved a rough structure theorem for small separations in vertex transitive graphs which has applications in both graph theory and combinatorial number theory. There are numerous directions to push forward here (ex. a generalization to digraphs) which I believe would make suitable projects for students. Another crossover problem is to give bounds on the average degree of a power of a regular graph. Together with McDonald and Scheide, I have recently proved a tight bound on this for powers which are 2 (mod 3). Extending these results from graphs to digraphs would be extremely valuable for both extremal graph theory and additive combinatorics. Graph Immersion Immersion is a natural containment operation in graphs which has received relatively little attention in comparison to graph minors. Robertson and Seymour have famously shown that graphs are well-quasi-ordered under immersion, but very little is understood about structural properties of this relation. Recently I have collaborated with various groups of colleagues to study immersion. Our most notable results include a theorem demonstrating that every simple graph of minimum degree 200t immerses the complete graph K_t and a rough structure theorem for graphs which do not immerse a given graph. There are numerous important directions for future research here. Indeed, I am working on such problems at present with two Masters students. Together with Mahdieh Malekian (and McDonald) we are working toward a precise characterization of the graphs which do not immerse K_5 or K_{3,3}, and together with Stefan Hannie (and Mohar and Archdeacon) we are studying immersion of 2-regular digraphs. Matroid Minors The matroid minors project of Geelen, Gerards, and Whittle has established a powerful theory of matroids which are representable over a fixed finite field. This work also has promoted the study of certain matroids which are quite close to graphs called frame matroids. As a first step toward understanding these matroids, my Ph.D. student Daryl Funk and Goddyn and I have proved a representation theorem for these matroids which we believe will be useful in understanding their structure, our eventual goal.