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

这个数学研究项目从计算和算法的角度来研究图上的“烧芯片游戏”。在过去的三十年里，基于在网络或图形中重新分配物品的芯片烧毁游戏出现在各种各样的数学和计算领域。它们起源于动力系统，是阿贝尔沙堆模型的一部分，这是已知的第一个显示自组织临界性重要属性的系统例子。最近的一种观点认为，图上的芯片射击游戏是研究代数曲线的一种离散的组合工具。这使我们对图论的数学领域和代数几何之间的联系有了更深的理解。这个框架中的一个关键概念是网络的除性，它衡量了某些烧片游戏在该网络上获胜的难度；这个数字已经与图论中的关键不变量联系在一起，例如树宽。这个项目将从计算的角度加深对芯片射击游戏的理解，首先设计并实现高效的算法来研究这些游戏及其难度。一旦实施，这些工具将被用于诸如代数几何、图论和动力系统等不同领域的研究，以及作为教学工具在课堂上使用。除了这些数学应用，已知在计算上困难的芯片烧毁问题将作为计算方法和技术的良好基准。这个项目有本科生参与研究，为这些学生提供未来STEM纯领域和应用领域的关键技能。该项目将考虑有限图和度量图上的几个版本的阶性：除性，图上正秩除数的最小程度；几何广度，根据树的调和态射定义；稳定的除性，它允许在计算除数之前进行精化；以及更高的阶性，它要求具有指定秩除数的最小程度。虽然本质上是纯粹的组合，但这些主题与诸如热带几何、Berkovich理论和Brill-Noether理论等代数几何领域有很深的联系。该总体计划有三个主要组成部分：(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.