Combinatorics Seminar
When: Sunday, January 16, 10am
Where: Schreiber 309
Speaker: Ohad Feldheim, Tel Aviv University
Title: The Firefighter Problem on the grid
Abstract:
The firefighter problem deals with monotone dynamic processes in
graphs. A fire spreads through a graph, from burning vertices to
their unprotected neighbors. In every round, a small amount of
unburnt vertices can be permanently protected by firefighters.
For infinite graphs, the problem is deciding what is the minimal
number of vertices the firefighters need to protect every turn
in order to eventually stop the fire from advancing?
We use potential functions to prove tight lower and upper bounds
on the amount of firefighters needed to control a fire in
the Cartesian planar grid and in the strong planar grid, resolving
two conjectures of Ng and Raff.
Joint work with Rani Hod.