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

RUI：芯片射击游戏的算法和复杂性以及图形控制性

• 批准号: 2011743
• 负责人: Ralph Morrison
• 金额: $ 9.94万
• 依托单位: Williams College
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-08-01 至 2023-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2011743&HistoricalAwards=false
• 关键词: RUI; Algorithms; Complexity; Chip; Firing

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.

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

项目成果

Uniform scrambles on graphs

• 发表时间: 2021-08
• 期刊: Australas. J Comb.
• 作者: Lisa Cenek;L. Ferguson;Eyobel Gebre;Cassandra Marcussen;Jason Meintjes;Ralph Morrison;Liz Ostermeyer;Shefali Ramakrishna

Graphs of scramble number two

第二次打乱图

• DOI: 10.1016/j.disc.2023.113539
• 发表时间: 2023
• 期刊: Discrete Mathematics
• 影响因子: 0.8
• 作者: Eagleton, Robin;Morrison, Ralph
• 通讯作者: Morrison, Ralph

Multiplicity-free gonality on graphs

图上的无多​​重性正交性

• DOI: 10.5614/ejgta.2023.11.2.2
• 发表时间: 2023
• 期刊: Electronic Journal of Graph Theory and Applications
• 影响因子: 0.7
• 作者: Dean, Frances;Everett, Max;Morrison, Ralph
• 通讯作者: Morrison, Ralph

On the scramble number of graphs

关于图的置乱数

• DOI: 10.1016/j.dam.2021.12.009
• 发表时间: 2022
• 期刊: Discrete Applied Mathematics
• 影响因子: 1.1
• 作者: Echavarria, Marino;Everett, Max;Huang, Robin;Jacoby, Liza;Morrison, Ralph;Weber, Ben
• 通讯作者: Weber, Ben