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

这个数学研究项目从计算和算法的角度研究图上的“芯片射击游戏”。 在过去的三十年里，基于在网络或图形中重新分配项目的芯片射击游戏已经出现在各种各样的数学和计算领域。 它们起源于动力系统中，是阿贝尔沙堆模型的一部分，这是第一个已知的系统显示出被称为自组织临界性的重要属性的例子。最近的观点认为，图形上的芯片射击游戏是研究代数曲线的离散组合工具。这导致了对图论和代数几何的数学领域之间的联系有了更深入的理解。 这个框架中的一个关键概念是网络的除法性，它衡量了在该网络上赢得某些筹码射击游戏的难度;这个数字已经与图论中的关键不变量联系起来，例如树宽。这个项目将从计算的角度加深对芯片发射游戏的理解，首先设计并实现有效的算法来研究这些游戏及其难度。一旦实施，这些工具将用于研究等不同领域的代数几何，图论和动力系统，以及在课堂上作为教学工具。除了这些数学应用之外，已知计算困难的芯片点火问题将作为计算方法和技术的良好基准。该项目涉及本科生的研究，为这些学生提供了在STEM的纯和应用领域的未来职业生涯的关键技能。该项目将考虑有限和度量图上的几个版本的gonality：除数gonality，一个图上的正秩因子的最小程度;几何gonality，定义在一棵树的调和态射;稳定的除数性，允许在计算除数性之前进行细化;以及更高的角度，要求具有规定秩的除数的最小度。虽然纯组合的性质，这些主题深深连接到这些领域的代数几何热带几何，布氏理论，和布里-诺特理论。本研究主要包含三个部分：（1）研究计算图的对称性的理论问题以及与计算复杂性相关的问题。 这包括研究在一般情况下和特殊类别的图中界定不同版本的角性的计算复杂性;设计计算角性的算法;以及研究具有重要计算后果的问题，例如找到角性的上界和下界。这里的关键工具将是对现有算法的修改，如达尔的燃烧算法。(2)实现用于研究图上的芯片发射游戏的计算工具。这将包括组合图和度量图的工具，这些工具也将免费提供给研究人员和教师。(3)应用这些工具来研究芯片发射游戏，图论和代数几何。 这些项目包括研究随机图的gonality，调查长期存在的图形gonality，执行相关的计算代数曲线，并调查嵌入方面的热带几何。 在某些情况下，计算本身将是至关重要的;在其他情况下，他们将只是引导研究方向在富有成效的方向。这个奖项反映了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.