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.