论文标题
对抗图燃烧密度
Adversarial graph burning densities
论文作者
论文摘要
图形燃烧是一个离散的时间过程，它模拟了网络中影响的传播。顶点要么是燃烧的，要么是未燃烧的，在每一轮中，一个燃烧的顶点会导致其所有邻居在选择新的火源燃烧之前燃烧。我们介绍了此过程的一种变体，该过程结合了在嵌套的，不断增长的图表上玩的对抗游戏。两名玩家，纵火犯和建筑商转弯：建筑商向它们添加了一定数量的新的未燃烧的顶点和边缘，以创建一个较大的图形，然后每个邻近的燃烧顶点的顶点都会燃烧，最后纵火烧了新的火源。这个过程永远重复。据说，如果燃烧顶点的限制部分趋于1，而纵火犯则赢得胜利，而据说建筑商却赢得了这一比例的限制。 本文的核心问题是确定鉴于建筑商在$ n $上增加了$ f（n）$顶点，纵火犯或建筑商都具有成功的策略。如果$ f（n）$是渐近的多项式，我们给出了哪个玩家有胜利策略的阈值结果。
Graph burning is a discrete-time process that models the spread of influence in a network. Vertices are either burning or unburned, and in each round, a burning vertex causes all of its neighbours to become burning before a new fire source is chosen to become burning. We introduce a variation of this process that incorporates an adversarial game played on a nested, growing sequence of graphs. Two players, Arsonist and Builder, play in turns: Builder adds a certain number of new unburned vertices and edges incident to these to create a larger graph, then every vertex neighbouring a burning vertex becomes burning, and finally Arsonist `burns' a new fire source. This process repeats forever. Arsonist is said to win if the limiting fraction of burning vertices tends to 1, while Builder is said to win if this fraction is bounded away from 1. The central question of this paper is determining if, given that Builder adds $f(n)$ vertices at turn $n$, either Arsonist or Builder has a winning strategy. In the case that $f(n)$ is asymptotically polynomial, we give threshold results for which player has a winning strategy.
