DIMACS Computational and Mathematical Epidemiology Seminar Series


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