Effective tools for the analysis of discrete structures

分析模式和预测复杂系统的计算成本的需求从未像今天这样强烈。在计算机科学中，数字信息是使用离散结构来建模的，如图(对互联网等网络中的连接进行建模)和正式单词(对DNA等字母序列进行建模)。因此，计算机科学和相关的组合学领域中的一个基本问题是从结构的形式定义中推导出结构的大规模行为。这通常是通过提供大小为n的对象的数量(例如，具有n个节点的图的数量)的“渐近”估计来实现的，当n变得任意大时，其误差变为零。人们还可以检查大尺寸物体中参数的行为(例如，用包含某种固定模式的次数来计算具有固定字母数的类DNA序列的数量)。值得注意的是，对于大类结构，参数的行为是由众所周知的概率极限定理决定的。这样的结果可以预测统计机械模型中的相变，将自然选择产生的DNA模式从随机噪声中分离出来，并对海量数据上的分类算法的平均行为进行分类。这项研究采用了现代和经典的理论数学技术来创建这种大规模分析的工具：目标是开发可以在软件中实现并易于被其他人应用的严格方法。计算渐近行为的关键思想是用它的母函数来编码一个描述某一族对象的数字序列，一个无穷和，它的项描述了这个序列。存在公知的理论来导出由列举具有各种属性的对象的生成函数所满足的方程，这些生成函数然后用作序列的隐式编码。计算工具可以用来自动化这一过程的大部分。为了在单变量中生成函数，现在已经很成熟的分析组合学领域展示了如何使用复数分析中的工具来确定渐近行为。对于多元生成函数--例如，在计算具有多个参数的对象的极限定理时需要--我们知道的要少得多。这项研究发展了快速增长的多变量分析组合学领域，它借鉴和扩展了从微分几何、拓扑学和计算机代数等不同数学领域的方法。我们利用深奥的数学技术来开发易于使用的软件，用于离散结构的分析，可供不同领域的其他研究人员使用。此外，通过扩展以前的方法，这项工作也推进了基本的数学理论。理论工作以有影响力的尖端应用为指导，其中包括量子计算、生物信息学和排队论。

The need to analyze patterns and predict the cost of computing with complex systems has never been greater than it is today. In computer science, digital information is modeled using discrete structures, such as graphs (which model connections in networks like the internet) and formal words (which model sequences of letters like DNA). A fundamental problem in computer science, and the related field of combinatorics, is thus the derivation of large-scale behaviour of structures from their formal definitions. This is often accomplished by providing an "asymptotic" estimate for the number of objects with size n (for instance, the number of graphs with n nodes) whose error goes to zero as n gets arbitrarily large. One can also examine the behaviour of parameters among objects of large size (for instance, counting the number of DNA-like sequences with a fixed number of letters by the number of times it contains some fixed pattern). Strikingly, for large classes of structures the behaviour of parameters is dictated by well-known limit theorems from probability. Such results can predict phase transitions in statistical mechanical models, separate DNA patterns which arise via natural selection from random noise, and classify the average behaviour of sorting algorithms on vast amounts of data. This research adapts theoretical mathematical techniques -- both modern and classical -- to create tools for this large-scale analysis: the goal is to develop rigorous methods that can be implemented in software and easily applied by others. The key idea to calculating asymptotic behaviour is to encode a sequence of numbers describing some family of objects by its generating function, an infinite sum whose terms describe the sequence. Well known theories exist to derive equations satisfied by the generating functions enumerating objects with various properties, which then serve as implicit encodings of the sequences. Computational tools can be used to automate much of this process. For generating functions in a single variable, the now well-established field of analytic combinatorics shows how to use tools from complex analysis to determine asymptotic behaviour. For multivariate generating functions -- needed, for instance, when calculating limit theorems for objects with multiple parameters -- much less is known. This research develops the rapidly growing field of analytic combinatorics in several variables, which draws on and extends methods from areas of mathematics as diverse as differential geometry, topology, and computer algebra. We exploit deep mathematical techniques to develop easy-to-use software for the analysis of discrete structures that can be put to use by other researchers across diverse fields. Furthermore, by extending previous methods this work also pushes forward the underlying mathematical theory. The theoretical work is guided by impactful and cutting-edge applications, which include quantum computing, bioinformatics, and queuing theory.