Singularity analysis and the large scale behaviour of combinatorial structures

点击翻译按钮获取中文摘要

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.