### 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