Reference number : GC-2017-Q1-01782, amendment number : , agreement type : G, recipient legal name : Mishna, Marni (Simon Fraser University), recipient country : CA, recipient province : nan, recipient city : British Columbia|Colombie-Britannique, recipient postal code : nan, program name english : Discovery Grants Program - Individual, program name french : Programme de subventions à la découverte - individuelles, program purpose english : 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., program purpose french : 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., agreement title english : Singularity analysis and the large scale behaviour of combinatorial structures, agreement title french : Singularity analysis and the large scale behaviour of combinatorial structures, agreement number : RGPIN, agreement value : 130000.0, agreement start date : 2017-05-10, agreement end date : nan, description english : nan, description french : nan, expected results english : nan, expected results french : nan, additional information english : Grant or Award spanning more than one fiscal year. (2017-2018 to 2022-2023), additional information french : Subvention ou bourse octroyée s'appliquant à plus d'un exercice financier. (2017-2018 à 2022-2023), owner organization : nserc-crsng, owner organization title : Natural Sciences and Engineering Research Council of Canada | Conseil de recherches en sciences naturelles et en génie du Canada