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

Eduardo Martínez-Pedroza

doi:10.5802/tsg.314

Eduardo Martínez-Pedroza ¹

¹ Memorial University St. John’s Newfoundland A1C 5S7 (Canada)

Séminaire de théorie spectrale et géométrie, Tome 33 (2015-2016), pp. 55-60.

Résumé

The firefighter game problem on locally finite connected graphs was introduced by Bert Hartnell [6]. 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 \geq 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 $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 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.

Publié le : 2018-08-27

DOI : 10.5802/tsg.314

Classification : 20F65, 43A07, 57M07, 05C57, 05C10, 05C25

Affiliations des auteurs :

Eduardo Martínez-Pedroza ¹

¹ Memorial University St. John’s Newfoundland A1C 5S7 (Canada)

@article{TSG_2015-2016__33__55_0,
     author = {Eduardo Mart{\'\i}nez-Pedroza},
     title = {A note on the relation between {Hartnell{\textquoteright}s} firefighter problem and growth of groups},
     journal = {S\'eminaire de th\'eorie spectrale et g\'eom\'etrie},
     pages = {55--60},
     publisher = {Institut Fourier},
     address = {Grenoble},
     volume = {33},
     year = {2015-2016},
     doi = {10.5802/tsg.314},
     language = {en},
     url = {https://proceedings.centre-mersenne.org/articles/10.5802/tsg.314/}
}

TY  - JOUR
AU  - Eduardo Martínez-Pedroza
TI  - A note on the relation between Hartnell’s firefighter problem and growth of groups
JO  - Séminaire de théorie spectrale et géométrie
PY  - 2015-2016
SP  - 55
EP  - 60
VL  - 33
PB  - Institut Fourier
PP  - Grenoble
UR  - https://proceedings.centre-mersenne.org/articles/10.5802/tsg.314/
DO  - 10.5802/tsg.314
LA  - en
ID  - TSG_2015-2016__33__55_0
ER  -

%0 Journal Article
%A Eduardo Martínez-Pedroza
%T A note on the relation between Hartnell’s firefighter problem and growth of groups
%J Séminaire de théorie spectrale et géométrie
%D 2015-2016
%P 55-60
%V 33
%I Institut Fourier
%C Grenoble
%U https://proceedings.centre-mersenne.org/articles/10.5802/tsg.314/
%R 10.5802/tsg.314
%G en
%F TSG_2015-2016__33__55_0

Eduardo Martínez-Pedroza. A note on the relation between Hartnell’s firefighter problem and growth of groups. Séminaire de théorie spectrale et géométrie, Tome 33 (2015-2016), pp. 55-60. doi : 10.5802/tsg.314. https://proceedings.centre-mersenne.org/articles/10.5802/tsg.314/

Bibliographie
Cité par

[1] Laurent Bartholdi; Bálint Virág Amenability via random walks, Duke Math. J., Volume 130 (2005) no. 1, pp. 39-56 | DOI | MR | Zbl

[2] Itai Benjamini; Oded Schramm Every graph with a positive Cheeger constant contains a tree with a positive Cheeger constant, Geom. Funct. Anal., Volume 7 (1997) no. 3, pp. 403-419 | DOI | MR | Zbl

[3] Martin R. Bridson; André Haefliger Metric spaces of non-positive curvature, Grundlehren der Mathematischen Wissenschaften, 319, Springer, 1999, xxii+643 pages | DOI | MR | Zbl

[4] Ching Chou Elementary amenable groups, Ill. J. Math., Volume 24 (1980) no. 3, pp. 396-407 http://projecteuclid.org/euclid.ijm/1256047608 | MR | Zbl

[5] Danny Dyer; Eduardo Martínez-Pedroza; Brandon Thorne The coarse geometry of Hartnell?s firefighter problem on infinite graphs, Discrete Math., Volume 340 (2017) no. 5, pp. 935-950 | Zbl

[6] Stephen Finbow; Bert L. Hartnell; Qiyan Li; Kyle Schmeisser On minimizing the effects of fire or a virus on a network, J. Comb. Math. Comb. Comput., Volume 33 (2000), pp. 311-322 | MR | Zbl

[7] Rostislav I. Grigorchuk On the Milnor problem of group growth, Dokl. Akad. Nauk SSSR, Volume 271 (1983) no. 1, pp. 30-33 | MR | Zbl

[8] Rostislav I. Grigorchuk; Andrzej Żuk On a torsion-free weakly branch group defined by a three state automaton, Int. J. Algebra Comput., Volume 12 (2002) no. 1-2, pp. 223-246 | DOI | MR | Zbl

[9] Andreas Thom Trees in groups of exponential growth MathOverflow question, http://mathoverflow.net/q/60011 (version: 2013-05-09)

[10] Joseph A. Wolf Growth of finitely generated solvable groups and curvature of Riemannian manifolds, J. Differ. Geom., Volume 2 (1968), pp. 421-446 | MR | Zbl

Cité par Sources :