Title: The Firefighter Problem on $d$-dimensional Grids and Hartke's Conjecture
Speaker: Michael Capalbo, DIMACS
Date: October 3, 2005, 12:00 - 1:30 pm Location: DIMACS Center, CoRE Bldg, Room 433, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
First, fix an integer $d$, and let $H$ be an infinite $d$-dimensional grid. Consider the following game played on $H$, in time-steps 0,1,2,....
(1) Every vertex in $H$ is either `fire-proofed', `suseptible', or `on-fire', where each vertex on-fire stays on-fire, and each vertex fire-proofed stays fire-proofed.
(2) At time-step 0, a finite subset $S_0$ of the vertices of $H$ are on-fire, and every other vertex is suseptible.
(3) Every vertex at time-step $t$ that is adjacent in $H$ to a vertex on-fire by time-step $t$ becomes infected at time-step $t+1$, unless $v$ is fire-proofed during time-step $t+1$.
(4) At each time step $t$, we are allowed to fire-proof only $f(t)$ suseptible vertices.
S. Hartke conjectured the following. If $f$ is such that $f(t)/t^{d-2}$ vanishes for $t$ large, then for some finite $S_0$, an infinite number of vertices of $H$ will end up on-fire (i.e., fire-proofing only $f(t) vertices at each time-step $t$ is not enough to contain the fire). We prove that his conjecture is true.
This is joint work with James Abello.
see: DIMACS Computational and Mathematical Epidemiology Seminar Series 2005 - 2006