# Adversarial graph burning densities

Karen Gunderson<EMAIL_ADDRESS>,  William Kellough
<EMAIL_ADDRESS>,  JD Nir<EMAIL_ADDRESS>and  Hritik Punj
<EMAIL_ADDRESS>
###### Abstract.

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.

###### 2020 Mathematics Subject Classification:

Primary: 05C57; Secondary: 05C42, 05C63

The first author gratefully acknowledges funding from NSERC, the second author
was supported in part from the University of Manitoba Faculty of Science
Undergraduate Research Award program, and the fourth author was supported by
the University of Manitoba Undergraduate Research Award program.

##  1\. Introduction

Graph burning is a discrete-time process that models the spread of influence
in a network. Vertices are in one of two states: either _burning_ or
_unburned_. In each round, a burning vertex causes all of its neighbours to
become burning and a new _fire source_ is chosen: a previously unburned vertex
whose state is changed to burning. The updates repeat until all vertices are
burning. The _burning number_ of a graph $G$, denoted $b(G)$, is the minimum
number of rounds required to burn all of the vertices of $G$.

Graph burning first appeared in print in a paper of Alon [1], motivated by a
question of Brandenburg and Scott at Intel, and was formulated as a
transmission problem involving a set of processors. It was then independently
studied by Bonato, Janssen, and Roshanbin [6, 7, 19] who gave bounds and
characterized the burning number for various graph classes. They showed in [7]
that the burning number of every connected graph is equal to the burning
number of one of its spanning trees and conjectured that if $G$ is a connected
graph on $n$ vertices, then $b(G)\leq\lceil n^{1/2}\rceil$. If true, this
would be the best possible upper bound as the path with $n$ vertices, $P_{n}$,
satisfies $b(P_{n})=\lceil n^{1/2}\rceil$. Currently, the tightest known bound
was given by Bastide, Bonamy, Bonato, Charbit, Kamali, Pierron, and Rabie [2]
who showed that $b(G)\leq\lceil\sqrt{4n/3}\rceil+1$. Norin and Turcotte
recently showed [18] that $b(G)\leq(1+o(1))\sqrt{n}$ and so the conjecture
holds asymptotically. Here, we require only the following bound from [3]:

(1) $b(G)\leq\sqrt{2n}.$

Burning density, introduced by Bonato, Gunderson, and Shaw [5], considers the
burning process when the graph itself is growing over time. Consider a
sequence of graphs:

$G_{1}\subseteq G_{2}\subseteq G_{3}\subseteq\cdots$

such that if $i<j$, the subgraph of $G_{j}$ induced by the vertices $V(G_{i})$
is $G_{i}$. That is, the ‘old graph’ does not change, but at each step ‘new
vertices’ arrive with some edges either between new vertices or between new
vertices and old vertices. The burning process in this setting evolves as: the
graph grows, the fire spreads, and we select an additional fire source.

At step $n$ of the process, let $V_{n}$ be the set of vertices and let $B_{n}$
be the set of burning vertices. In this context, there may never be a step
when every vertex is burning, but one can consider the proportion of burning
vertices. Given the sequences of graphs $\mathbf{G}=(G_{i})_{i\geq 1}$ and
fire sources $\mathbf{v}=(v_{i})_{i\geq 1}$, define the _lower burning
density_
$\underline{\delta}(\mathbf{G},\mathbf{v})=\liminf_{n\to\infty}\frac{|B_{n}|}{|V_{n}|}$,
the _upper burning density_
$\overline{\delta}(\mathbf{G},\mathbf{v})=\limsup_{n\to\infty}\frac{|B_{n}|}{|V_{n}|}$,
and the _burning density_
$\delta(\mathbf{G},\mathbf{v})=\lim_{n\to\infty}\frac{|B_{n}|}{|V_{n}|}$, if
it exists. As we will demonstrate, it is possible to construct examples where
the fraction of burning vertices fluctuates infinitely often and the burning
density does not exist.

In traditional graph burning there is a choice of where to place the fires,
but the process is otherwise deterministic. In this paper, we modify the setup
for burning densities to define an adversarial ‘game’. In this game there are
two players, Builder and Arsonist, who play as follows: Given a function
$f(n)$, known to both players, at time step $n$,

  * •

Builder adds $f(n)$ vertices to $G_{n-1}$ and edges incident to these new
vertices to create a connected graph $G_{n}$,

  * •

the fire spreads, and

  * •

Arsonist selects an additional fire source $v_{n}$.

Note that the definition of burning density does not require $G_{n}$ to be
connected, but we impose this restriction in order to prevent Builder from
playing the trivial strategy of adding $f(n)$ independent vertices. In this
game (that goes on forever), Arsonist wins if the burning density is
$\delta(\mathbf{G},\mathbf{v})=1$ and Builder wins if
$\overline{\delta}(\mathbf{G},\mathbf{v})<1$. That is, Arsonist wins if they
can eventually burn all but a negligible fraction of the vertices and Builder
wins if they can eventually guarantee that for all time steps going forward, a
constant fraction of the vertices are unburned. If
$\overline{\delta}(\mathbf{G},\mathbf{v})=1$ but
$\underline{\delta}(\mathbf{G},\mathbf{v})<1$, which is to say if the burning
density does not exist but the proportion of burning vertices approaches $1$
infinitely often, we say that neither player wins and the game ends in a draw.
Assume that both Builder and Arsonist play ‘perfectly’: among all possible
choices, they always choose the best.

One may equivalently view this game as measuring the worst-case burning
density of a graph burning process in which the graphs are known to be
connected and the orders of the graphs to be burned are known, but the
specific choice of $G_{n}$ is only revealed on turn $n$.

The game we have described is an adversarial zero-sum game with perfect
information. This means at most one player can win and both players know of
all options available to each player at every step in the game. Such games
have a long history in the literature, tracing back to von Neumann and
Morgenstern [17]. Gale and Stewart [11] introduced the idea of infinite games
in which a winner is selected only after countably many turns. Infinite games
are used in mathematical logic and have been used in computer science to study
computation processes [12]. Other examples of games on graphs that have (or
may potentially have) infinitely many rounds include a Maker-Breaker game for
infinite connected components of the origin in a subgraph of the infinite grid
[9], a Ramsey-game where a win for one of the players involves an infinite
graph [13], a variation of Cops and Robbers on an infinite graph [14], and
energy-parity games [8].

The central question of this paper is determining whether, given that Builder
adds $f(n)$ vertices at turn $n$, Arsonist or Builder has a winning strategy.
Our main result proves there is a threshold at which functions which grow
polynomially switch from being Arsonist-win to Builder-win.

######  Theorem 1.

Let $\alpha>0$ and $f:\mathbb{Z}^{+}\to\mathbb{Z}^{+}$ satisfy
$f(n)=\theta(n^{\alpha})$. Then in the adversarial burning game in which
Builder adds $f(n)$ vertices on turn $n$, Arsonist has a winning strategy if
$\alpha<1$ and Builder has a winning strategy if $\alpha\geq 1$.

Indeed, Theorem 1 is a direct consequence of a broader classification theorem
which considers functions that may fluctuate between growth rates.

######  Theorem 2.

Let $f:\mathbb{Z}^{+}\to\mathbb{Z}^{+}$ and consider the adversarial graph
burning game in which Builder adds $f(n)$ vertices on turn $n$. Then:

  * •

Arsonist has a winning strategy if there exists $\alpha<1$ such that
$f(n)=O(n^{\alpha})$ and $\omega(n^{2\alpha-1})$, and

  * •

Builder has a winning strategy if either $f(n)=\theta(n)$ or if there exists
$c>2$ so that for all $n\geq n_{0}$, $f(n)\geq cn$.

Note that if $f(n)=\theta(n^{\alpha})$ for $\alpha>1$, then, for sufficiently
large $n$, $f(n)>2.1n$, say, and so Theorem 1 follows from Theorem 2.
Additionally, Theorem 2 also covers superpolynomial functions.

In [7], it was shown that determining extremal values of burning numbers for
connected graphs can always be reduced to the restricted problem on trees.
Similarly, we show that, in terms of understanding which player has a winning
strategy, it suffices to assume that Builder always builds trees.

Given a function $f(n)$, define a _legal construction_ for Builder to be a
sequence of graphs $(G_{1},G_{2},\dots)$ such that for each
$n\in\mathbb{Z}^{+}$, $G_{n}$ is a connected graph with $\sum_{k=1}^{n}f(k)$
vertices, $G_{n}\subseteq G_{n+1}$, and the subgraph of $G_{n+1}$ induced by
$V(G_{n})$ is $G_{n}$.

######  Theorem 3.

Let $f(n)$ be given. For every legal construction
$\mathbf{G}=(G_{1},G_{2},\dots)$ for Builder and for all choices of fire
sources, $\mathbf{v}$, every legal construction
$\mathbf{T}=(T_{1},T_{2},\dots)$ such that $T_{n}$ is a spanning tree of
$G_{n}$, for all $n\in\mathbb{Z}^{+}$, satisfies
$\underline{\delta}(\mathbf{T},\mathbf{v})\leq\underline{\delta}(\mathbf{G},\mathbf{v})$
and
$\overline{\delta}(\mathbf{T},\mathbf{v})\leq\overline{\delta}(\mathbf{G},\mathbf{v})$.

In particular, if Arsonist has a strategy that succeeds given any sequence of
trees Builder selects, they have a winning strategy for all legal
constructions. Similarly, if Builder has a winning strategy, they also have a
winning strategy using a legal construction consisting of a sequence of trees.

We prove Theorem 3 in Section 2 and Theorem 2 in Section 3 before closing with
a few unresolved questions regarding the adversarial burning game.

###  1.1. Acknowledgements

The authors offer thanks to Ruiyang Chen who gave useful feedback on some
preliminary discussions of the problems considered in this paper as well as
the anonymous referee who offered several useful refinements to the results
and examples in this paper.

##  2\. Restricting Builder to trees

In this section we prove Theorem 3.

###### Proof.

For a legal construction $\mathbf{G}=(G_{1},G_{2},\dots)$, let
$\mathbf{T}=(T_{1},T_{2},\dots)$ be any sequence of graphs such that
$T_{n}\subseteq T_{n+1}$, the subgraph of $T_{n+1}$ induced by $V(T_{n})$ is
$T_{n}$, and $T_{n}$ is a spanning tree of $G_{n}$ for all
$n\in\mathbb{Z}^{+}$. Let $\mathbf{v}=(v_{1},v_{2},\dots)$ be any sequence of
fire sources for Arsonist in $\mathbf{G}$. Suppose Arsonist burns the same
sequence of vertices $\mathbf{v}$ when Builder uses the legal construction
$\mathbf{T}$.

Since $T_{n}$ contains a subset of the edges of $G_{n}$ for every
$n\in\mathbb{Z}^{+}$, the number of burning vertices in $T_{n}$ is at most the
number of burning vertices in $G_{n}$. Furthermore, $T_{n}$ and $G_{n}$ have
the same number of vertices for all $n\in\mathbb{Z}^{+}$. Thus
$\underline{\delta}(\mathbf{T},\mathbf{v})\leq\underline{\delta}(\mathbf{G},\mathbf{v})$
and
$\overline{\delta}(\mathbf{T},\mathbf{v})\leq\overline{\delta}(\mathbf{G},\mathbf{v})$.

∎

Based on Theorem 3, we assume hereafter that Builder’s sequence of graphs is a
growing sequence of trees.

##  3\. Polynomial thresholds

In this section we prove Theorem 2 by describing winning strategies in each
scenario. We start by proving that Arsonist has a winning strategy when the
number of vertices Builder is given is bounded by two sublinear polynomials.

######  Proposition 4.

Let $\alpha<1$ and let $f:\mathbb{Z}^{+}\to\mathbb{Z}^{+}$ be a function with
$f(n)=O(n^{\alpha})$ and $f(n)=\omega(n^{2\alpha-1})$. Then Arsonist has a
winning strategy in the adversarial burning game when Builder receives $f(n)$
new vertices at step $n$.

###### Proof.

Let $c>0$ be such that $f(n)\leq cn^{\alpha}$ for all $n$ sufficiently large.
Let $\mathbf{G}=(G_{1},G_{2},\dots)$ be the sequence of graphs Builder
constructs and for every $i$, let $V_{i}=V(G_{i})$.

Fix $N_{1}\in\mathbb{Z}^{+}$ large, and allow Arsonist to choose vertices to
burn arbitrarily in the first $N_{1}$ steps of the game. Recursively define a
sequence of integers $(N_{k})_{k\geq 1}$ as follows. For every $k\geq 1$
define $A_{k}=b(G_{N_{k}})$, the burning number of $G_{N_{k}}$, and
$N_{k+1}=N_{k}+A_{k}$. Arsonist’s strategy will be to burn the graph
$G_{N_{k}}$ in $A_{k}$ steps (which we bound by Equation (1)) between time
$N_{k}$ and time $N_{k+1}$, ignoring any vertices that had been burning before
time $N_{k}$. Thus we have $|B_{N_{k}}|\geq|V_{N_{k-1}}|$ for all $k\geq 2$ as
the number of vertices burning at time $N_{k}$ is at least the number of
vertices in $G_{N_{k-1}}$.

We first estimate the number of new vertices added between time $N_{k-1}$ and
$N_{k}$: $\sum_{n=N_{k-1}+1}^{N_{k}}f(n)$. For this, we use the inequality

(2) $(1+x)^{1+\alpha}\leq 1+2(1+\alpha)x,$

which holds for $x<1$ when $\alpha<1$.

$\displaystyle\sum_{n=N_{k-1}+1}^{N_{k}}f(n)$ $\displaystyle\leq
c\sum_{n=N_{k-1}+1}^{N_{k}}n^{\alpha}$ $\displaystyle\leq
c\int_{N_{k-1}}^{N_{k}+1}x^{\alpha}dx$
$\displaystyle=\frac{c}{\alpha+1}\left((N_{k}+1)^{\alpha+1}-(N_{k-1})^{\alpha+1}\right)$
$\displaystyle=\frac{c}{\alpha+1}\left((N_{k-1}+A_{k-1}+1)^{\alpha+1}-(N_{k-1})^{\alpha+1}\right)$
$\displaystyle=\frac{c}{\alpha+1}(N_{k-1})^{\alpha+1}\left(\left(1+\frac{A_{k-1}}{N_{k-1}}+\frac{1}{N_{k-1}}\right)^{\alpha+1}-1\right)$
$\displaystyle\leq\frac{c}{\alpha+1}(N_{k-1})^{\alpha+1}\left(\left(1+\frac{2A_{k-1}}{N_{k-1}}\right)^{\alpha+1}-1\right)$
$\displaystyle\leq\frac{c}{\alpha+1}(N_{k-1})^{\alpha+1}\left(1+\frac{4(\alpha+1)A_{k-1}}{N_{k-1}}-1\right)$
(by Equation (2)) $\displaystyle=4c(N_{k-1})^{\alpha}A_{k-1}$
$\displaystyle\leq 4c(N_{k-1})^{\alpha}\cdot\sqrt{2|V_{N_{k-1}}|}$ (by
Equation (1))

To estimate the total number of vertices, we consider two cases depending on
whether $\alpha\geq 1/2$ or $\alpha<1/2$. First, assume that $\alpha\geq 1/2$
so that $2\alpha-1\geq 0$.

We first claim that

(3) $|V_{N_{k}}|=\omega((N_{k})^{2\alpha}).$

Fix $M>0$ and choose $N$ large enough such that $f(n)\geq 4\alpha M\cdot
n^{2\alpha-1}$ for all $n\geq N$. Then for $k$ large enough that $N_{k}\geq
N$,

$\displaystyle|V_{N_{k}}|$ $\displaystyle=\sum_{n=1}^{N_{k}}f(n)$
$\displaystyle\geq\sum_{n=N+1}^{N_{k}}4\alpha Mn^{2\alpha-1}$
$\displaystyle\geq 4\alpha M\int_{N}^{N_{k}}x^{2\alpha-1}dx$
$\displaystyle\geq 2M\left(\left(N_{k}\right)^{2\alpha}-N^{2\alpha})\right)$
$\displaystyle\geq M\left(N_{k}\right)^{2\alpha}$

for $N_{k}\geq(2)^{1/2\alpha}N$. As $M$ was arbitrary, we have shown
$|V_{N_{k}}|=\omega((N_{k})^{2\alpha})$.

To estimate the fraction of burning vertices in the graph $G_{N_{k}}$, note
that

$|V_{N_{k}}|=|V_{N_{k-1}}|+\sum_{n=N_{k-1}+1}^{N_{k}}f(n).$

Therefore, using Equation (3),

$\frac{\sum_{n=N_{k-1}+1}^{N_{k}}f(n)}{|V_{N_{k-1}}|}\leq\frac{4\sqrt{2}c(N_{k-1})^{\alpha}}{\sqrt{|V_{N_{k-1}}|}}=4\sqrt{2}c\frac{(N_{k-1})^{\alpha}}{\omega((N_{k-1})^{\alpha})}=o(1).$

Returning to the case where $\alpha<1/2$, note that the condition on the lower
bound for the function $f$ reduces to $f(n)>0$. Then, using the bound
$|V_{N_{k-1}}|\geq N_{k-1}$ gives,

$\frac{\sum_{n=N_{k-1}+1}^{N_{k}}f(n)}{|V_{N_{k-1}}|}\leq\frac{4\sqrt{2}c(N_{k-1})^{\alpha}}{\sqrt{|V_{N_{k-1}}|}}\leq
4\sqrt{2}c\frac{(N_{k-1})^{\alpha}}{N_{k-1}^{1/2}}=o(1).$

Thus in either case,

$\displaystyle\liminf_{k\to\infty}\frac{|V_{N_{k-1}}|}{|V_{N_{k}}|}$
$\displaystyle=\liminf_{k\to\infty}\frac{|V_{N_{k-1}}|}{|V_{N_{k-1}}|+\sum_{n=N_{k-1}+1}^{N_{k}}f(n)}$
$\displaystyle=\liminf_{k\to\infty}\frac{|V_{N_{k-1}}|}{(1+o(1))|V_{N_{k-1}}|}$
$\displaystyle=1$

For any $n\geq N_{1}$, choose $k$ largest such that $n\geq N_{k}$. Then
$|B_{n}|\geq|B_{N_{k}}|\geq|V_{N_{k-1}}|$ and $|V_{n}|\leq|V_{N_{k+1}}|$, so
we have

$\displaystyle\underline{\delta}(\mathbf{G},\mathbf{v})$
$\displaystyle=\liminf_{n\to\infty}\frac{|B_{n}|}{|V_{n}|}$
$\displaystyle\geq\liminf_{k\to\infty}\frac{|V_{N_{k-1}}|}{|V_{N_{k+1}}|}$
$\displaystyle=\left(\liminf_{k\to\infty}\frac{|V_{N_{k-1}}|}{|V_{N_{k}}|}\right)\left(\liminf_{k\to\infty}\frac{|V_{N_{k}}|}{|V_{N_{k+1}}|}\right)$
$\displaystyle=1,$

where we note that the limit infimum is bounded above by $1$ and therefore
exists, which permits splitting the limit across the product
$\frac{|V_{N_{k-1}}|}{|V_{N_{k}}|}\cdot\frac{|V_{N_{k}}|}{|V_{N_{k+1}}|}$. So
as

$1\geq\overline{\delta}(\mathbf{G},\mathbf{v})\geq\underline{\delta}(\mathbf{G},\mathbf{v})=1,$

the burning density, $\delta(\mathbf{G},\mathbf{v})$, exists and equals $1$,
so Arsonist wins.

∎

Note that the lower bound conditions on the function $f$ in Proposition 4 are
necessary to guarantee a winning strategy for the Arsonist. To see this,
consider the following examples.

######  Example 5.

First, for $\alpha<1/2$, since the lower bound condition on the function $f$
in Proposition 4 reduces to simply $f(n)>0$, we consider a function $f$ that
alternates between $0$ and $\lfloor n^{\alpha}\rfloor$. Throughout, suppose
that Builder builds a path. Given any $N_{0}$ and $|V_{N_{0}}|$, let $f(n)=0$
for $N_{0}<n\leq N_{1}$, with $N_{1}$ large enough so that
$|V_{N_{1}}|<N_{1}^{\alpha}$. Then, for $N_{2}=N_{1}+\lfloor
N_{1}^{\alpha/2}\rfloor$, define $f(n)=\lfloor n^{\alpha}\rfloor$ when
$N_{1}<n\leq N_{2}$. The total number of vertices at time $N_{2}$ is

$|V_{N_{2}}|\geq|V_{N_{1}}|+N_{1}^{\alpha}\cdot\lfloor
N_{1}^{\alpha/2}\rfloor\geq|V_{N_{1}}|+N_{1}^{\alpha}\cdot(N_{1}^{\alpha/2}-1)\geq
N_{1}^{3\alpha/2}-N_{1}^{\alpha}.$

To bound from above the number of burning vertices at time $N_{2}$, we assume
that all vertices in $V_{N_{1}}$ are burning. As Builder constructs a path,
the vertices Arsonist burns from time $N_{1}+1$ to $N_{2}$ form (possibly
overlapping) intervals of lengths $1$ through $N_{2}-(N_{1}+1)=\lfloor
N_{1}^{\alpha/2}\rfloor-1$, with at most $N_{1}^{\alpha/2}$ additional
vertices burning due to spread from $V_{N_{1}}$. Together, this gives

$|B_{N_{2}}|\leq|V_{N_{1}}|+N_{1}^{\alpha/2}+\sum_{\ell=1}^{\lfloor
N_{1}^{\alpha/2}\rfloor-1}(2\ell-1)\leq
N_{1}^{\alpha}+N_{1}^{\alpha/2}+(N_{1}^{\alpha/2})^{2}\leq 3N_{1}^{\alpha}.$

Thus,

(4)
$\frac{|B_{N_{2}}|}{|V_{N_{2}}|}\leq\frac{3N_{1}^{\alpha}}{N_{1}^{3\alpha/2}-N_{1}^{\alpha}}.$

For $N_{1}$ sufficiently large, the upper bound in equation (4) is arbitrarily
small. Repeating these phases of growth shows that for any choice of fire
sources, $\underline{\delta}(\mathbf{G},\mathbf{v})=0$, so we do not have
$\delta(\mathbf{G},\mathbf{v})=1$ and Arsonist does not win.

######  Example 6.

Consider now an example where, for $1/2\leq\alpha<1$, the function $f$
fluctuates between $f(n)=\lfloor n^{\alpha}\rfloor$ and $f(n)=\lfloor
n^{2\alpha-1}\rfloor$. Again, assume that Builder builds a path.

Fix $0<\varepsilon<1/8$. Given any $N_{0}$, let $M_{0}$ be the number of
vertices added by time $N_{0}$. Assuming that for $N_{0}<n\leq N$, that
$f(n)=\lfloor n^{2\alpha-1}\rfloor$, then as $N$ tends to infinity, the number
of vertices at time $N$ is

$\displaystyle|V_{N}|$ $\displaystyle=M_{0}+\sum_{n=N_{0}+1}^{N}\lfloor
n^{2\alpha-1}\rfloor$
$\displaystyle=M_{0}+(1+o(1))\int_{N_{0}}^{N}x^{2\alpha-1}\ dx$
$\displaystyle=M_{0}+\frac{(1+o(1))}{2\alpha}\left(N^{2\alpha}-N_{0}^{2\alpha}\right)$
$\displaystyle=\frac{(1+o(1))}{2\alpha}N^{2\alpha},$

for any fixed value of $N_{0}$ or $M_{0}$. Thus, given $N_{0}$ and the number
of vertices added up to this point, let $N_{1}$ be large enough so that if,
for $N_{0}<n\leq N_{1}$, $f(n)=\lfloor n^{2\alpha-1}\rfloor$, then

$\left||V_{N_{1}}|-\frac{N_{1}^{2\alpha}}{2\alpha}\right|\leq\varepsilon
N_{1}^{2\alpha}.$

Set $N_{2}=N_{1}+\lfloor N_{1}^{\alpha}\rfloor$ and for $N_{1}<n\leq N_{2}$,
let $f(n)=\lfloor n^{\alpha}\rfloor$. To estimate the number of burning
vertices at time $N_{2}$, assume that all vertices in $V_{N_{1}}$ are burning
as are all vertices added up to time $N_{1}+\lfloor N_{1}^{\alpha}/2\rfloor$.
Accounting for the spread of burning vertices from these and the balls
surrounding the vertices Arsonist selected after time $N_{1}+\lfloor
N_{1}^{\alpha}/2\rfloor$, we see that

$\displaystyle|B_{N_{2}}|$
$\displaystyle\leq|V_{N_{1}}|+\sum_{n=N_{1}+1}^{N_{1}+\lfloor
N_{1}^{\alpha}/2\rfloor}n^{\alpha}+(N_{2}-(N_{1}+\lfloor
N_{1}^{\alpha}/2\rfloor))+\sum_{\ell=1}^{\lfloor N_{1}^{\alpha}\rfloor-\lfloor
N_{1}^{\alpha}/2\rfloor}(2\ell-1)$ (5)
$\displaystyle\leq\left(\frac{1}{2\alpha}+\varepsilon\right)N_{1}^{2\alpha}+\int_{N_{1}+1}^{N_{1}+N_{1}^{\alpha}/2+1}x^{\alpha}\
dx+\frac{N_{1}^{\alpha}}{2}+1+\left(\frac{N_{1}^{\alpha}}{2}+1\right)^{2}$

To estimate the integral in equation (5), we extend the inequality in Equation
(2) by noting

(6) $(1+x)^{\alpha+1}\leq 1+(\alpha+1)x+(\alpha+1)\alpha x^{2},$

which holds for $x<1$ for any $\alpha<1$. Therefore,

$\displaystyle\int_{N_{1}+1}^{N_{1}+N_{1}^{\alpha}/2+1}x^{\alpha}\ dx$
$\displaystyle=\frac{1}{\alpha+1}\left((N_{1}+N_{1}^{\alpha}/2+1)^{\alpha+1}-(N_{1}+1)^{\alpha+1}\right)$
$\displaystyle=\frac{(N_{1}+1)^{\alpha+1}}{\alpha+1}\left(\left(1+\frac{N_{1}^{\alpha}}{2(N_{1}+1)}\right)^{\alpha+1}-1\right)$
$\displaystyle\leq\frac{(N_{1}+1)^{\alpha+1}}{\alpha+1}\left(1+\frac{(\alpha+1)N_{1}^{\alpha}}{2(N_{1}+1)}+\frac{(\alpha+1)\alpha
N_{1}^{2\alpha}}{4(N_{1}+1)^{2}}-1\right)$ (by Equation (6))
$\displaystyle=\frac{N_{1}^{\alpha}(N_{1}+1)^{\alpha}}{2}+\frac{\alpha
N_{1}^{2\alpha}}{4(N_{1}+1)^{1-\alpha}}$
$\displaystyle\leq\frac{N_{1}^{2\alpha}}{2}(1+1/N_{1})^{\alpha}+\frac{\alpha
N_{1}^{3\alpha-1}}{4}$
$\displaystyle\leq\frac{N_{1}^{2\alpha}}{2}\left(1+\frac{2\alpha}{N_{1}}\right)+\frac{\alpha
N_{1}^{3\alpha-1}}{4}$ (by Equation (2)) (7)
$\displaystyle\leq\frac{N_{1}^{2\alpha}}{2}+2\alpha N_{1}^{3\alpha-1}.$

Since
$\left(\frac{N_{1}^{\alpha}}{2}+1\right)^{2}=\frac{N_{1}^{2\alpha}}{4}+N_{1}^{\alpha}+1\leq\frac{N_{1}^{2\alpha}}{4}+2N_{1}^{\alpha}$,
combining equations (5) and (7) gives

$\displaystyle|B_{N_{2}}|$
$\displaystyle\leq\left(\frac{3}{4}+\frac{1}{2\alpha}+\varepsilon\right)N_{1}^{2\alpha}+\frac{N_{1}^{\alpha}}{2}+1+2\alpha
N_{1}^{3\alpha-1}+2N_{1}^{\alpha}$
$\displaystyle\leq\left(\frac{3}{4}+\frac{1}{2\alpha}+\varepsilon\right)N_{1}^{2\alpha}+5N_{1}^{3\alpha-1}.$

Meanwhile,

$\displaystyle|V_{N_{2}}|$
$\displaystyle\geq|V_{N_{1}}|+\sum_{n=N_{1}+1}^{N_{1}+\lfloor
N_{1}^{\alpha}\rfloor}(n^{\alpha}-1)$ $\displaystyle\geq|V_{N_{1}}|+\lfloor
N_{1}^{\alpha}\rfloor((N_{1}+1)^{\alpha}-1)$
$\displaystyle\geq\left(\frac{1}{2\alpha}-\varepsilon\right)N_{1}^{2\alpha}+(N_{1}^{\alpha}-1)N_{1}^{\alpha}$
$\displaystyle=\left(1+\frac{1}{2\alpha}-\varepsilon\right)N_{1}^{2\alpha}-N_{1}^{\alpha}.$

Thus, the fraction of burning vertices is at time $N_{2}$ is bounded by

(8)
$\frac{|B_{N_{2}}|}{|V_{N_{2}}|}\leq\frac{\left(\frac{3}{4}+\frac{1}{2\alpha}+\varepsilon\right)N_{1}^{2\alpha}+5N_{1}^{3\alpha-1}}{\left(1+\frac{1}{2\alpha}-\varepsilon\right)N_{1}^{2\alpha}-N_{1}^{\alpha}}.$

For $N_{1}$ sufficiently large, the upper bound in equation (8) is arbitrarily
close to $\frac{3/4+1/(2\alpha)+\varepsilon}{1+1/(2\alpha)-\varepsilon}$,
which is strictly less than $1$. Repeating the construction gives a function
$f$ so that for any sequence of activated vertices,
$\underline{\delta}(\mathbf{G},\mathbf{v})<1$ and so Arsonist does not win.

Next, we consider the adversarial burning game in which the number of vertices
Builder is given grows either linearly or superlinearly.

######  Proposition 7.

Let $f:\mathbb{Z}^{+}\to\mathbb{Z}^{+}$ be a function so that either

  * •

$f=\theta(n)$, or

  * •

there exists $c>2$ so that for some $n_{0}$, for all $n\geq n_{0}$, $f(n)\geq
cn$.

Then given $f(n)$ new vertices at step $n$, Builder has a winning strategy in
the adversarial burning game.

###### Proof.

We consider the strategy in which Builder constructs an increasingly long path
by always adding new vertices to one end of the previous path.

First, consider the case where $f=\theta(n)$. Let $n_{0},\alpha,\beta>0$ (with
$\alpha\leq\beta$) be such that for each $n\geq n_{0}$, $\alpha n\leq
f(n)\leq\beta n$. Consider the state of the game on some turn $N>n_{0}$.
Regardless of Arsonist’s strategy, some initial portion of Builder’s path
consists entirely of burning vertices while fire sources that Arsonist has
burned more recently form small (potentially overlapping) intervals. To bound
the total number of burning vertices, we choose some turn $k_{0}$ satisfying
$N>k_{0}\geq n_{0}$ and we assume that the paths added in the process up to
turn $k_{0}$ are entirely burning and that fires started after turn $k_{0}$ do
not intersect. This gives us three collections of burning vertices: an initial
segment of length $\sum_{k=1}^{k_{0}}f(k)$, an additional $N-k_{0}$ vertices
extending that initial segment that are potentially burned from that segment,
and $N-k_{0}$ non-intersecting balls of radius $1$ through $N-k_{0}$, giving
the estimate

$|B_{N}|\leq\sum_{k=1}^{k_{0}}f(k)+(N-k_{0})+\sum_{\ell=1}^{N-k_{0}}(2\ell-1)=\sum_{k=1}^{k_{0}}f(k)+(N-k_{0})^{2}+O(N).$

The total number of vertices by turn $N$ is

$|V_{N}|=\sum_{k=1}^{N}f(k)\geq\sum_{k=1}^{k_{0}}f(k)+\sum_{k=k_{0}+1}^{N}\alpha
k\geq\sum_{k=1}^{k_{0}}f(k)+\frac{\alpha}{2}(N^{2}-k_{0}^{2}).$

Thus for any choice of $k_{0}$ we have a burning density of at most

$\displaystyle\frac{|B_{N}|}{|V_{N}|}$
$\displaystyle\leq\frac{\sum_{k=1}^{k_{0}}f(k)+(N-k_{0})^{2}+O(N)}{\sum_{k=1}^{k_{0}}f(k)+\frac{\alpha}{2}(N^{2}-k_{0}^{2})}$
$\displaystyle=1-\frac{\frac{\alpha}{2}(N^{2}-k_{0}^{2})-(N-k_{0})^{2}+O(N)}{\sum_{k=1}^{k_{0}}f(k)+\frac{\alpha}{2}(N^{2}-k_{0}^{2})}$

We choose

$k_{0}=\left\lfloor\frac{2}{2+\alpha}N\right\rfloor$

which gives

$\frac{\alpha}{2}(N^{2}-k_{0}^{2})-(N-k_{0})^{2}+O(N)=\frac{\alpha^{2}}{2(\alpha+2)}N^{2}+O(N).$

We also have

$\displaystyle\sum_{k=1}^{k_{0}}f(k)+\frac{\alpha}{2}(N^{2}-k_{0}^{2})$
$\displaystyle=\sum_{k=1}^{n_{0}-1}f(k)+\sum_{k=n_{0}}^{k_{0}}f(k)+\frac{\alpha}{2}(N^{2}-k_{0}^{2})$
$\displaystyle\leq\sum_{k=1}^{n_{0}-1}f(k)+\sum_{k=n_{0}}^{k_{0}}\beta
k+\frac{\alpha}{2}(N^{2}-k_{0}^{2})$
$\displaystyle=\beta\frac{k_{0}(k_{0}+1)}{2}+\frac{\alpha}{2}(N^{2}-k_{0}^{2})+\sum_{k=1}^{n_{0}-1}f(k)-\beta\frac{n_{0}(n_{0}-1)}{2}$
$\displaystyle=\left(\frac{\alpha^{3}+4\alpha^{2}+4\beta}{2(\alpha+2)^{2}}\right)N^{2}+O(N)$

and so

$\displaystyle\frac{\frac{\alpha}{2}(N^{2}-k_{0}^{2})-(N-k_{0})^{2}+O(N)}{\sum_{k=1}^{k_{0}}f(k)+\frac{\alpha}{2}(N^{2}-k_{0}^{2})}$
$\displaystyle\geq\frac{\frac{\alpha^{2}}{2(\alpha+2)}N^{2}+O(N)}{(\frac{\alpha^{3}+4\alpha^{2}+4\beta}{2(\alpha+2)^{2}})N^{2}+O(N)}$
$\displaystyle=\frac{\alpha^{2}(2+\alpha)}{\alpha^{3}+4\alpha^{2}+4\beta}+o(1).$

For sufficiently large $N$, we have

$\frac{|B_{N}|}{|V_{N}|}\leq
1-\frac{\alpha^{2}(2+\alpha)}{2(\alpha^{3}+4\alpha^{2}+4\beta)}+o(1)<1$

and so Builder wins.

Now if instead $c>2$ and $f(n)\geq cn$ when $n\geq n_{0}$, we may instead
bound

$|B_{N}|\leq\sum_{k=1}^{N}2k-1=N^{2}$

as

$|V_{N}|\geq|V_{n_{0}}|+\sum_{k=n_{0}+1}^{N}cn=\frac{c}{2}N^{2}+O(N)$

and thus once again we have

$\limsup_{N\to\infty}\frac{|B_{N}|}{|V_{N}|}\leq\lim_{N\to\infty}\frac{N^{2}}{\frac{c}{2}N^{2}+O(N)}=\frac{2}{c}<1.$

∎

Proposition 7 also covers the case of superlinear functions: if $f=\omega(n)$,
then given $f(n)$ new vertices at step $n$, since for $n$ sufficiently large,
$f(n)>2.1n$, Builder has a winning strategy.

In the case where the function $f$ fluctuates between a linear function and a
sublinear function, the Builder can no longer necessarily win, as shown by the
following example.

######  Example 8.

Consider a function $f$ for which there are $0<\alpha<1$ and $\beta>0$ so that
either $f(n)>\beta n$ or else $f(n)=\lfloor n^{\alpha}\rfloor$. At any given
time $N_{0}$, let $0<\varepsilon<1/2$ and let $N_{1}$ be such that letting
$f(n)>\beta n$ for $N_{0}<n\leq N_{1}$, gives

$|V_{N_{1}}|>\frac{(1-\varepsilon)\beta}{2}N_{1}^{2}.$

Set $N_{2}=N_{1}+\lceil\sqrt{2|V_{N_{1}}|}\rceil$ so that, using Equation (1),
by time $N_{2}$ Arsonist can burn all of the vertices in $V_{N_{1}}$ no matter
which sequence of graphs Builder chose and which fire sources Arsonist chose
before turn $N_{1}$. For $N_{1}<n\leq N_{2}$, let $f(n)=\lfloor
n^{\alpha}\rfloor$. Note that by the assumption on $N_{1}$,
$N_{1}<\sqrt{\frac{2}{\beta(1-\varepsilon)}|V_{N_{1}}|}<\sqrt{\frac{4}{\beta}|V_{N_{1}}|}$.
The number of new vertices added during this time is

$\displaystyle\sum_{n=N_{1}+1}^{N_{2}}f(n)$
$\displaystyle\leq\lceil\sqrt{2|V_{N_{1}}|}\rceil N_{2}^{\alpha}$
$\displaystyle=\lceil\sqrt{2|V_{N_{1}}|}\rceil\left(N_{1}+\lceil\sqrt{2|V_{N_{1}}|}\rceil\right)^{\alpha}$
$\displaystyle\leq
2\sqrt{|V_{N_{1}}|}\left(\sqrt{\frac{4}{\beta}|V_{N_{1}}|}+2\sqrt{|V_{N_{1}}|}\right)^{\alpha}$
$\displaystyle\leq 4(\beta^{-1/2}+1)^{\alpha}|V_{N_{1}}|^{(\alpha+1)/2}.$

Thus, the fraction of burning vertices at time $N_{2}$ is

$\frac{|B_{N_{2}}|}{|V_{N_{2}}|}\geq\frac{|V_{N_{1}}|}{|V_{N_{1}}|+4(\beta^{-1/2}+1)^{\alpha}|V_{N_{1}}|^{(\alpha+1)/2}}.$

Since $(\alpha+1)/2<1$, then for $N_{1}$ sufficiently large, the fraction of
burning vertices at time $N_{1}$ is arbitrarily close to $1$. Thus, repeating
this construction shows that there is a sequence of activated vertices with
$\overline{\delta}(\mathbf{G},\mathbf{v})=1$ and so Builder cannot have a
winning strategy.

##  4\. Further directions

While Theorem 2 resolves the question of which player wins the adversarial
burning game for a large collection of functions, there are clearly many
functions not covered by either the results given here or a direct application
of the proof techniques. As we have shown, it is possible to construct
examples that fluctuate between different growth rates in which neither player
wins, and even where the lower density is 0 and the upper burning density is
1.

While a classification of those functions for which either Arsonist or Builder
has a winning strategy seems to be out of reach, it is natural to seek to
expand the class of functions for which the winner is known. The most natural
question is whether Proposition 7 is best possible. The proposition resolves
the question for asymptotically linear functions as well as functions that
stay strictly larger than $2n$ but does not address, for example, a function
that alternates between $n$ and $\lceil n^{1.1}\rceil$.

######  Question 1.

Does there exist a function $f:\mathbb{Z}^{+}\to\mathbb{Z}^{+}$ such that
$f(n)=\Omega(n)$ and Builder does not have a winning strategy in the
adversarial burning game given $f(n)$ vertices on turn $n$?

One approach to answer Question 1 would be to determine whether the problem
exhibits monotonicity under certain conditions. It seems natural that if
Builder has a winning strategy given $f(n)$ vertices, any additional vertices
could only help.

######  Question 2.

Let $f,g:\mathbb{Z}^{+}\to\mathbb{Z}^{+}$ be functions such that $f(n)\leq
g(n)$ for all $n\in\mathbb{Z}^{+}$. If Builder wins the adversarial burning
game when given $f(n)$ vertices at every step $n$, does it necessarily follow
that Builder still wins if they are given $g(n)$ vertices at every step?

Because of the possibility that neither player wins, Question 2 can be
formulated from Arsonist’s perspective: if Arsonist already wins when Builder
is given $g(n)\geq f(n)$ vertices, what can we say when Builder is only given
$f(n)$ vertices? Note that, perhaps surprisingly, if $f(n)\leq g(n)$ and
Arsonist has a winning strategy for the function $g(n)$, it is not necessarily
true that Arsonist has a winning strategy for the function $f(n)$, as seen by
Examples 5 and 6 where the Arsonist can win with $g(n)=\lfloor
n^{\alpha}\rfloor$, but cannot win with a function that fluctuates between
$\lfloor n^{\alpha}\rfloor$ and a smaller function. However, in these
examples, it is only shown that Builder can bound the burning density away
from 1 infinitely often and leaves open the following problem.

######  Question 3.

Let $f,g:\mathbb{Z}^{+}\to\mathbb{Z}^{+}$ be functions such that $f(n)\leq
g(n)$ for all $n\in\mathbb{Z}^{+}$. If Arsonist wins the adversarial burning
game when Builder is given $g(n)$ vertices at every step $n$, does it
necessarily follow that Builder cannot win if they are given $f(n)$ vertices
at every step $n$?

One could also consider a weaker type of monotonicity. Suppose instead of
decreasing the number of vertices Builder is given each turn, we only require
that at each step the total number of vertices Builder has received is
smaller. That is, instead of requiring $f(n)\leq g(n)$ for each
$n\in\mathbb{Z}^{+}$, we have the weaker condition
$\sum_{k=1}^{n}f(k)\leq\sum_{k=1}^{n}g(k)$.

In each instance we analyzed a specific strategy for Builder, we considered
the consequences of Builder constructing a path. The conjecture that paths
have extremal burning number makes this a natural choice of strategy. However,
it is not uncommon in combinatorial games that an extremal example is not
optimal in the context of a game. This suggests the following question.

######  Question 4.

Let $f:\mathbb{Z}^{+}\to\mathbb{Z}^{+}$. If Builder has some winning strategy
in the adversarial burning game adding $f(n)$ vertices at step $n$, is
building a path guaranteed to be a winning strategy for Builder?

If true, one would no longer need to consider which strategy Builder chooses,
essentially reducing the question of determining a winner to bounding the
burning density of a path that gains $f(n)$ vertices at step $n$.

Finally, one may also consider variations of the adversarial burning game
where either Builder or Arsonist is replaced by a random process. Mitsche,
Prałat, and Roshanbin [16] studied the graph burning process when new fire
sources were selected uniformly at random, which generalizes naturally to the
adversarial game, replacing Arsonist by a uniform random process.
Alternatively, one could replace Builder with a _uniform random recursive
tree_ , which is generated by adding vertices one by one, selecting an
existing vertex uniformly at random to be the parent of each new vertex. For
more on recursive trees, see [10, 15].

## References

  * [1] N. Alon, Transmitting in the n-dimensional cube, _Discrete Applied Mathematics_ 37 (1992) 9–11.
  * [2] P. Bastide, M. Bonamy, A. Bonato, P. Charbit, S. Kamali, T. Pierron, and M. Rabie, _Improved pyrotechnics: Closer to the burning graph conjecture_ , arXiv preprint, arXiv:2110.10530 [math.CO], 2022.
  * [3] S. Bessy, A. Bonato, J. Janssen, D. Rautenbach, and E. Roshanbin, Bounds on the burning number, _Discrete Appl. Math._ , 235 (2018), 16–22.
  * [4] A. Bonato, A survey of graph burning, _Contrib. Discrete Math._ , 16 (2021), 185–197.
  * [5] A. Bonato, K. Gunderson, and A. Shaw, Burning the plane: Densities of the infinite Cartesian grid, _Graphs and Combinatorics_ 36 (2020), 1311–1335.
  * [6] A. Bonato, J. Janssen, and E. Roshanbin, Burning a graph as a model of social contagion, _Lecture Notes in Comput. Sci._ , 8882 (2014), 13–22.
  * [7] A. Bonato, J. Janssen, E. Roshanbin, How to burn a graph, _Internet Mathematics_ 1-2 (2016), 85–100.
  * [8] K. Chatterjee, L. Doyen, Energy parity games, _Theoret. Comput. Sci._ 458 (2012), 49–60.
  * [9] A. N. Day, V. Falgas-Ravry, Maker-breaker percolation games II: escaping to infinity, _J. Combin. Theory Ser. B_ 151 (2021), 482–508.
  * [10] M. Drmota, _Random trees: an interplay between combinatorics and probability_. Springer Science and Business Media, 2009.
  * [11] D. Gale and F. Stewart, Infinite games with perfect information, _Contributions to the Theory of Games_ 2 (1953) 2–16.
  * [12] Y. Gurevich, Infinite Games, _Current trends in theoretical computer science: essays and tutorials_ , World Scientific (1993) 235–244.
  * [13] D. Hefetz, C. Kusch, L. Narins, A. Pokrovskiy, C. Requilé, A. Sarid, Strong Ramsey games: drawing on an infinite board, _J. Combin. Theory Ser. A_ 150 (2017), 248–266.
  * [14] F. Lehner, Pursuit evasion on infinite graphs, _Theoret. Comput. Sci._ 655 (2016), part A, 30–40.
  * [15] H. Mahmoud and R. Smythe, A survey of recursive trees, _Theory Probab. Math. Statist._ , 51, (1995), 1–27.
  * [16] D. Mitsche, P. Prałat, and E. Roshanbin, Burning graphs—a probabilistic perspective, _Graphs Combin._ , 33 (2017), 449–471.
  * [17] J. von Neumann and O. Morgenstern, Theory of games and economic behavior. Princeton University Press, 2007. Originally published 1947.
  * [18] S. Norin and J. Turcotte, _The burning number conjecture holds asymptotically_ , arXiv preprint, arXiv:2207.04035 [math.CO] (2022).
  * [19] E. Roshanbin, Burning a graph as a model of social contagion, PhD thesis, Dalhousie University, Halifax, NS, 2016.