Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Simon Fraser University

$26,000.00

Singularity analysis and the large scale behaviour of combinatorial structures

EF 2020-21

Résumé
Many problems from the natural sciences and computing theory are modelled using discrete combinatorial objects, such as trees, sequences, and random walks. Interesting applications require an understanding of the properties of these objects when they are extremely large. The models aid in predicting the run-time of algorithms, properties of genomes, and phase transitions in chemical processes. Naive strategies are quickly overwhelmed by the sheer size of the objects. Formal power series (known as generating functions in this context) have proved to be an efficient and effective way to study enumerative questions, offer insights into distributions of important parameters, and other large scale behavioural questions notably when tools like exhaustive generation are no longer feasible. The proposed research program develops theory and applications for an important class of generating functions in order to answer enumerative questions, and to develop algorithms to randomly generate objects. This kind of information is key to evaluate the choice of a combinatorial model in a given application. Efficient uniform random generation gives a glimpse of what a typical object of large size looks like. Asymptotic enumeration formulas are simple enough to test against. This program develops new methods and techniques by focussing on lattice walks and grammars. Lattice walks are a basic, yet customizable object: one controls the allowable steps and the region of interest. Grammars are a formalism for describing objects. This is an ideal context from which to study generating functions. The key novelty of this program is the analysis of multivariable series by extracting relevant subsidies. This is done through a study of integrals, with special properties. Computer algebra, algebraic geometry and complex analysis all intervene to unravel structure and provide insight. When a combinatorial class can be written using a grammar, there exist efficient strategies for random generation. We investigate this in the case of some graph classes. When no grammar (provably) exists, they are still useful: It suffices to find a combinatorial class that is generated by a grammar, that contains the desired class and not much else. In this case rejection algorithms are provably efficient. This research is important to anyone that studies combinatorial models-- from natural sciences to pure mathematics. New strategies to understand the large scale behaviour of combinatorial classes has the potential to advance any field manipulating big data.
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-2017-04157
Name nom
Mishna, Marni
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
2020
Competition year année de concours
2017
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 grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
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
Installment
inst:4-5
Partie
2
Nb partie
5
Application title
Singularity analysis and the large scale behaviour of combinatorial structures
Keyword
NSERC
Application summary
Many problems from the natural sciences and computing theory are modelled using discrete combinatorial objects, such as trees, sequences, and random walks. Interesting applications require an understanding of the properties of these objects when they are extremely large. The models aid in predicting the run-time of algorithms, properties of genomes, and phase transitions in chemical processes. Naive strategies are quickly overwhelmed by the sheer size of the objects. Formal power series (known as generating functions in this context) have proved to be an efficient and effective way to study enumerative questions, offer insights into distributions of important parameters, and other large scale behavioural questions notably when tools like exhaustive generation are no longer feasible. The proposed research program develops theory and applications for an important class of generating functions in order to answer enumerative questions, and to develop algorithms to randomly generate objects. This kind of information is key to evaluate the choice of a combinatorial model in a given application. Efficient uniform random generation gives a glimpse of what a typical object of large size looks like. Asymptotic enumeration formulas are simple enough to test against. This program develops new methods and techniques by focussing on lattice walks and grammars. Lattice walks are a basic, yet customizable object: one controls the allowable steps and the region of interest. Grammars are a formalism for describing objects. This is an ideal context from which to study generating functions. The key novelty of this program is the analysis of multivariable series by extracting relevant subsidies. This is done through a study of integrals, with special properties. Computer algebra, algebraic geometry and complex analysis all intervene to unravel structure and provide insight. When a combinatorial class can be written using a grammar, there exist efficient strategies for random generation. We investigate this in the case of some graph classes. When no grammar (provably) exists, they are still useful: It suffices to find a combinatorial class that is generated by a grammar, that contains the desired class and not much else. In this case rejection algorithms are provably efficient. This research is important to anyone that studies combinatorial models-- from natural sciences to pure mathematics. New strategies to understand the large scale behaviour of combinatorial classes has the potential to advance any field manipulating big data.