Combinatorial games

组合游戏

• 批准号: 1950980
• 金额: --
• 依托单位: University of Cambridge
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2017
• 资助国家: 英国
• 起止时间: 2017 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-1950980
• 关键词: Combinatorial; games

My most successful research so far has been my study, together with Rebekah Herrman, of the `Diffusion Game' on graphs, about which we have written the paper `Uniform Bounds for Non-negativity ofthe Diffusion Game'. The diffusion game is a process in which each vertex of a graph is assigned a numerical label, representing a number of chips. These labels are updated at discrete integer time steps according to the following rule: for every edge whose endpoints have differing numbers of chips, we (simultaneously) transfer one chip from the vertex with more chips to the vertex with fewer chips. This process had previously been introduced by Duffy, Lidbetter, Messinger and Nowakowski, and further studied by Long and Narayanan. In a paper posted to arXiv last year, Long and Narayanan posed the question of whether, for a fixed number of vertics, bounding the initial number of chips on each vertex would give a constant bound on the number of chips on a vertex at any subsequent time step. We answered this question completely, if we start with at least (n - 2) chips on each vertex, then the number of chips on each vertex will remain non- negative. Furthermore, this bound is tight. We also establish a related (partial) bound based on the maximum degree of the graph; we hope to make further progress on this question in the future. These results, and subsequent questions, are discussed in detail in our aforementioned paper.

迄今为止，我最成功的研究是与 Rebekah Herrman 一起研究图上的“扩散博弈”，我们就此撰写了论文“扩散博弈非负性的统一界限”。扩散博弈是一个为图的每个顶点分配一个数字标签的过程，代表多个筹码。这些标签根据以下规则以离散整数时间步长更新：对于端点具有不同数量芯片的每条边，我们（同时）将一个芯片从具有更多芯片的顶点转移到具有更少芯片的顶点。这个过程之前由 Duffy、Lidbetter、Messinger 和 Nowakowski 提出，并由 Long 和 Narayanan 进一步研究。在去年发布到 arXiv 的一篇论文中，Long 和 Narayanan 提出了这样的问题：对于固定数量的顶点，限制每个顶点上的初始芯片数量是否会在任何后续时间步骤中对顶点上的芯片数量给出恒定的限制。我们完全回答了这个问题，如果我们开始时每个顶点上至少有 (n - 2) 个芯片，那么每个顶点上的芯片数量将保持非负数。此外，这个界限是紧的。我们还根据图的最大度建立相关（部分）界限；我们希望今后在这个问题上取得进一步进展。这些结果以及随后的问题在我们前面提到的论文中进行了详细讨论。