A note on the relation between Hartnell's firefighter problem and growth of groups

DOI10.5802/TSG.314arXiv1701.02614WikidataQ129268886 ScholiaQ129268886MaRDI QIDQ6281752FDOQ6281752

Publication date: 10 January 2017

Abstract: The firefighter game problem on locally finite connected graphs was introduced by Bert Hartnell. The game on a graph

G

can be described as follows: let

f_{n}

be a sequence of positive integers; an initial fire starts at a finite set of vertices; at each (integer) time

n g e q 1

,

f_{n}

vertices which are not on fire become protected, and then the fire spreads to all unprotected neighbors of vertices on fire; once a vertex is protected or is on fire, it remains so for all time intervals. The graph

G

has the emph{

f_{n}

-containment property} if every initial fire admits an strategy that protects

f_{n}

vertices at time

n

so that the set of vertices on fire is eventually constant. If the graph

G

has the containment property for a sequence of the form

f_{n} = C n^{d}

, then the graph is said to have emph{polynomial containment}. In [5], it is shown that any locally finite graph with polynomial growth has polynomial containment; and it is remarked that the converse does not hold. That article also raised the question of whether the equivalence of polynomial growth and polynomial containment holds for Cayley graphs of finitely generated groups. In this short note, we remark how the equivalence holds for elementary amenable groups and for non-amenable groups from results in the literature.

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Games on graphs (graph-theoretic aspects) (05C57) Geometric group theory (20F65) Means on groups, semigroups, etc.; amenable groups (43A07) Games involving graphs (91A43)

This page was built for publication: A note on the relation between Hartnell's firefighter problem and growth of groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6281752)