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