Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Victoria

$26,000.00

Novel methods in combinatorics

EF 2022-23

Résumé
My research lies in the field of combinatorics, although several of my research directions are intrinsically linked to questions in number theory, probability and geometry. The overarching theme of my proposed research program concerns new methods. It involves both pioneering new methods that have the potential to revolutionise our understanding in certain areas, developing novel techniques that I (along with co-authors) have discovered and utilising existing powerful methods in areas where their strength has not yet been fully exploited. In the past I have substantially impacted the field in many distinct areas, and I intend to continue in this vein. To this end, my program contains several themes. Random Matrices: The study of random matrices lies at the intersection of combinatorial geometry, probability and number theory. Understanding the properties and parameters of random matrices has many applications to other areas of mathematics such as graph theory, stochastic growth models and tiling problems, but also to engineering (in particular in the design and analysis of wireless networks). I intend to develop techniques towards solving two of the major open problems in this area, then to apply these techniques to related problems. Graph colouring: It is very desirable to have an intelligible certificate that a graph is not k-colourable. With some colleagues, I recently developed a framework in which we could find simple algebraic certificates for non k-colourability, and for which existence can be proved by elementary arguments. This research direction involves developing our theory and applying it to prove a wide range of results in the area of graph colouring. We have successfully achieved our first goals and reproved several known results using our methods. Processes on graphs: The family of processes that I am interested in can be thought of as models of the spread of disease through a network. A typical such process begins with an initial set of `infected' nodes (the others are `healthy'), and at each time step, a healthy node can become infected according to a set of update rules. The questions I intend to study broadly fall into two categories: extremal and probabilistic. Extremal questions are often of the form, `What is the minimum number of vertices that need to be initially infected for the process to spread to infect everything?' The probabilistic questions concern the study of parameters of a process where the initially infected set is chosen randomly. Extremal graph theory: With Scott, I determined the maximum possible number of induced cycles in a graph with n vertices. I believe that our methods can be generalised and applied to related problems. One such problem is an extremal question on transversals in hypergraphs. This is interesting because results about minimal transversals of hypergraphs can be translated to give results about particular minimal models in CNF theories, which have applications in logic programming.
Programme
Discovery Grants Program - Individual
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2021-02511
Name nom
Morrison, Natasha
Department département
Mathematics and Statistics - Mathematics and Statistics
Organization id
7
Institution établissement
University of Victoria
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2022
Competition year année de concours
2021
Award amount
26000
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
2900
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Pure mathematics
Research subject fr
Mathématiques pures
Installment
inst:2
Partie
1
Nb partie
5
Application title
Novel methods in combinatorics
Application summary
My research lies in the field of combinatorics, although several of my research directions are intrinsically linked to questions in number theory, probability and geometry. The overarching theme of my proposed research program concerns new methods. It involves both pioneering new methods that have the potential to revolutionise our understanding in certain areas, developing novel techniques that I (along with co-authors) have discovered and utilising existing powerful methods in areas where their strength has not yet been fully exploited. In the past I have substantially impacted the field in many distinct areas, and I intend to continue in this vein. To this end, my program contains several themes. Random Matrices: The study of random matrices lies at the intersection of combinatorial geometry, probability and number theory. Understanding the properties and parameters of random matrices has many applications to other areas of mathematics such as graph theory, stochastic growth models and tiling problems, but also to engineering (in particular in the design and analysis of wireless networks). I intend to develop techniques towards solving two of the major open problems in this area, then to apply these techniques to related problems. Graph colouring: It is very desirable to have an intelligible certificate that a graph is not k-colourable. With some colleagues, I recently developed a framework in which we could find simple algebraic certificates for non k-colourability, and for which existence can be proved by elementary arguments. This research direction involves developing our theory and applying it to prove a wide range of results in the area of graph colouring. We have successfully achieved our first goals and reproved several known results using our methods. Processes on graphs: The family of processes that I am interested in can be thought of as models of the spread of disease through a network. A typical such process begins with an initial set of `infected' nodes (the others are `healthy'), and at each time step, a healthy node can become infected according to a set of update rules. The questions I intend to study broadly fall into two categories: extremal and probabilistic. Extremal questions are often of the form, `What is the minimum number of vertices that need to be initially infected for the process to spread to infect everything?' The probabilistic questions concern the study of parameters of a process where the initially infected set is chosen randomly. Extremal graph theory: With Scott, I determined the maximum possible number of induced cycles in a graph with n vertices. I believe that our methods can be generalised and applied to related problems. One such problem is an extremal question on transversals in hypergraphs. This is interesting because results about minimal transversals of hypergraphs can be translated to give results about particular minimal models in CNF theories, which have applications in logic programming.