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.

该数学研究项目从计算和算法的角度研究了图形上的“筹码游戏”。 在过去的三十年中，基于整个网络或图形的重新分布项目的芯片游戏已经出现在各种数学和计算领域中。 它们起源于动态系统，作为Abelian Sandpile模型的一部分，这是显示一个称为自组织关键性的重要属性的系统的第一个已知示例。最近的观点将图表上的芯片发射游戏视为研究代数曲线的离散组合工具。这导致了对图理论的数学字段与代数几何形状之间的联系有更深入的了解。 在此框架中，一个关键概念是网络的分区性质，它衡量了某些芯片发射游戏在该网络上赢得的困难。该数字已经连接到图理论的关键不变性，例如树宽。该项目将从计算角度，首先设计，然后实施有效的算法来研究这些游戏及其难度。一旦实施，这些工具将用于在诸如代数几何，图形论和动力学系统以及教学工具等不同领域的研究中进行研究。除了这些数学应用之外，已知在计算上很难的芯片射击问题还将成为计算方法和技术的良好基准。该项目涉及研究中的本科生，为这些学生提供了STEM的纯净和应用领域的未来职业的关键技能。该项目将在有限和度量图上考虑几种版本的Gonality：Divisorial Gonality，Divisorial Gonality，最低级别的排名级别分数；几何性高性能，根据树的谐波形态定义；稳定的分区gonality，可以在计算分区的性能之前进行改进；和更高的gonalities，要求具有规定等级的除数的最低程度。尽管本质上纯粹是组合的，但这些主题与热带几何形状，伯科维奇理论和布里尔·纳特理​​论等代数几何形状的这种领域深入联系。总体项目的三个主要组成部分：（1）研究计算图的理论方面及相关主题相关的计算复杂性。 这包括研究一般和特殊类别类别的不同版本的界限的计算复杂性；设计用于计算高态的算法；并研究具有重要计算后果的问题，例如在高态上找到上限和下限。这里的关键工具将修改DHAR燃烧算法等现有算法。 （2）实施用于研究图表上芯片游戏的计算工具。这将包括组合图和公制图的工具，这些工具也将为研究人员和教师免费提供。 （3）将这些工具应用于研究芯片发射游戏，图理论和代数几何形状。 这样的项目包括研究随机图的性质，研究图形高态的长期猜想，执行与代数曲线相关的计算以及研究热带几何形状的嵌入式方面。 在某些情况下，计算本身将至关重要。在其他情况下，他们将仅以富有成果的方向指导研究方向。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛影响的评论标准来评估值得支持的。

项目成果

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