More specifically, for any positive integer $d$, let $H^d$ be a
$d$-dimensional infinite grid, where at each time-step ($0,1,2,
\ldots$), each vertex is in one of three states: {\em on-fire}, {\em
fireproofed}, or {\em suseptible}, where a vertex that is suseptible
becomes on-fire for the next time step if any of its neighbors are
on-fire already, unless it is fireproofed first. Suppose that at
time-step 0, some finite set $S_0$ of vertices is on-fire, and that at
each time-step $t$, we are allowed to fireproof $f(t)$ vertices of
$H^d$ to contain the set of vertices that eventually become on-fire to
a finite set. Hartke conjectured in his Ph.D. thesis that $f(t)$ would
have to be $\Omega(t^{d-2})$ for us to be successful for all such
$S_0$. The main result of this paper is that we prove his conjecture
to be correct.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2006/2006-11.ps.gz
DIMACS Home Page