RUI: Algorithms and Complexity in Chip-Firing Games and Graph Gonality

这个数学研究项目从计算和算法的角度研究图上的“芯片射击游戏”。 芯片射击游戏基于在整个网络或图表中重新分配项目，在过去三十年中出现在各种数学和计算领域。 它们起源于动力系统，作为阿贝尔沙堆模型的一部分，这是第一个已知的显示自组织临界性重要属性的系统示例。最近的观点将图上的芯片发射游戏视为研究代数曲线的离散组合工具。这使得人们对图论和代数几何数学领域之间的联系有了更深入的理解。 该框架中的一个关键概念是网络的除数性，它衡量某些筹码游戏在该网络上获胜的难度；这个数字已经与图论中的关键不变量（例如树宽）联系起来。该项目将从计算角度加深对芯片射击游戏的理解，首先设计并实现有效的算法来研究这些游戏及其难度。一旦实施，这些工具将用于代数几何、图论和动力系统等不同领域的研究，以及作为课堂教学工具。除了这些数学应用之外，已知计算困难的芯片发射问题也将成为计算方法和技术的良好基准。该项目涉及本科生参与研究，为这些学生提供未来在 STEM 的纯领域和应用领域职业的关键技能。该项目将考虑有限图和度量图上的几种版本的函数性：除数函数性，图上正秩除数的最小度；几何 Goality，根据树的调和态射定义；稳定的除数函数性，允许在计算除数函数性之前进行细化；以及更高的目标，要求具有规定等级的除数的最小次数。虽然本质上是纯粹的组合，但这些主题与热带几何、伯科维奇理论和布里尔-诺特理论等代数几何领域有着深刻的联系。该总体项目包含三个主要组成部分：（1）研究计算图连通性的理论方面以及与计算复杂性相关的主题。 这包括研究一般性的和特殊类别的图的不同版本的函数性的边界计算复杂性；设计计算目标的算法；研究具有重要计算结果的问题，例如寻找函数的上限和下限。这里的关键工具将是对 Dhar 燃烧算法等现有算法的修改。 (2) 实现用于研究图上的筹码游戏的计算工具。这将包括用于组合图和度量图的工具，这些工具也将免费提供给研究人员和教师。 (3) 应用这些工具来研究芯片射击游戏、图论和代数几何。 此类项目包括研究随机图的多角性、研究关于图多角性的长期猜想、执行与代数曲线相关的计算以及研究热带几何的嵌入式方面。 在某些情况下，计算本身至关重要；在其他情况下，他们只是将研究方向引导到富有成效的方向。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

This mathematics research project studies "chip-firing games" on graphs from a computational and algorithmic perspective. Chip-firing games, which are based on redistributing items throughout a network or graph, have appeared in a wide variety of mathematical and computational areas over the past three decades. They originated in dynamical systems as part of the abelian sandpile model, the first known example of a system to display an important property known as self-organized criticality. A more recent perspective has treated chip-firing games on graphs as a discrete, combinatorial tool for studying algebraic curves. This has led to a deeper understanding of the connections between the mathematical fields of graph theory and algebraic geometry. A key concept in this framework is the divisorial gonality of a network, which measures how difficult certain chip-firing games are to win on that network; this number has already been connected to key invariants from graph theory, such as treewidth. This project will deepen understanding of chip-firing games from a computational perspective, first designing and then implementing efficient algorithms for studying these games and their difficulty. Once implemented, these tools will be used for research in such disparate fields as algebraic geometry, graph theory, and dynamical systems, as well as in classrooms as pedagogical tools. In addition to these mathematical applications, the chip-firing problems that are known to be computationally difficult will serve as a good benchmark for computational methods and techniques. This project involves undergraduate students in the research, providing those students with key skills for future careers in both pure and applied areas of STEM.The project will consider several versions of gonality, on both finite and metric graphs: divisorial gonality, the minimum degree of a positive rank divisor on a graph; geometric gonality, defined in terms of harmonic morphisms to a tree; stable divisorial gonality, which allows for refinements before computing the divisorial gonality; and higher gonalities, which ask for the minimum degree of a divisor with prescribed rank. Although purely combinatorial in nature, these topics connect deeply to such areas of algebraic geometry as tropical geometry, Berkovich theory, and Brill-Noether theory. There are three main components of the overarching project: (1) To study the theoretical aspects of computing graph gonality and related topics vis-a-vis computational complexity. This includes studying the computational complexity of bounding the different versions of gonality, both in general and for special classes of graphs; designing algorithms for computing gonalities; and studying questions with important computational consequences, like finding upper and lower bounds on gonalities. Key tools here will be modifications of such existing algorithms as Dhar's burning algorithm. (2) To implement computational tools for studying chip-firing games on graphs. This will include tools for both combinatorial and metric graphs, which will also be made freely available to both researchers and teachers. (3) To apply these tools to study chip-firing games, graph theory, and algebraic geometry. Such projects include studying gonality of random graphs, investigating long-standing conjectures on graph gonalities, performing computations relevant to algebraic curves, and investigating embedded aspects of tropical geometry. In some cases, the computations themselves will be of paramount importance; in other cases, they will simply guide the direction of research in fruitful directions.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.