Singularity analysis and the large scale behaviour of combinatorial structures

奇点分析和组合结构的大规模行为

• 批准号: RGPIN-2017-04157
• 负责人: Mishna, Marni
• 金额: $ 1.89万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=758550
• 关键词: Singularity; analysis; large; scale; behaviour

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.

自然科学和计算理论中的许多问题都是使用离散组合对象建模的，例如树、序列和随机游走。 有趣的应用程序需要了解这些对象的属性时，他们是非常大的。这些模型有助于预测算法的运行时间、基因组的性质以及化学过程中的相变。 简单的策略很快就会被对象的庞大规模所淹没。形式幂级数（在本文中称为生成函数）已被证明是研究枚举问题的有效方法，提供了对重要参数分布的见解，以及其他大规模行为问题，特别是当穷举生成等工具不再可行时。拟议的研究计划开发理论和应用的一类重要的生成函数，以回答枚举问题，并开发算法，随机生成对象。这类信息是在给定应用中评估组合模型选择的关键。高效的均匀随机生成可以让我们看到一个典型的大尺寸物体的样子。渐近枚举公式很简单，可以用来检验。这个程序开发新的方法和技术，专注于网格行走和语法。晶格行走是一个基本的，但可定制的对象：一个控制允许的步骤和感兴趣的区域。文法是描述对象的形式体系。这是研究生成函数的理想背景。该方案的主要新奇在于通过提取相关补贴来分析多变量序列。 这是通过研究具有特殊性质的积分来完成的。计算机代数，代数几何和复杂的分析都介入解开结构，并提供洞察力。当一个组合类可以用一个文法来写时，就存在有效的随机生成策略。我们在一些图类的情况下研究这一点。当没有语法（可证明的）存在时，它们仍然是有用的：找到一个由语法生成的组合类就足够了，它包含所需的类，而不包含其他的。在这种情况下，拒绝算法是有效的。这项研究对任何研究组合模型的人都很重要-从自然科学到纯数学。理解组合类的大规模行为的新策略有可能推动任何操纵大数据的领域。