The firefighter problem on polynomial and intermediate growth groups

DOI10.1016/J.DISC.2020.112077MaRDI QIDQ2198398zbMATH OpenOpenAlexFDO

Authors Gideon Amir, Rangel Baldasso, Gady Kozma

Publication date 10 September 2020

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2002.11205

zbMATH Keywords

Cayley graphsfirefighter problem

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Games on graphs (graph-theoretic aspects) (05C57) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Games involving graphs (91A43)

Abstract: We prove that any Cayley graph $G$ with degree $d$ polynomial growth does not satisfy $f(n)$-containment for any $f=o(n^{d-2})$. This settles the asymptotic behaviour of the firefighter problem on such graphs as it was known that $C{n}^{d-2}$ firefighters are enough, answering and strengthening a conjecture of Develin and Hartke. We also prove that intermediate growth Cayley graphs do not satisfy polynomial containment, and give explicit lower bounds depending on the growth rate of the group. These bounds can be further improved when more geometric information is available, such as for Grigorchuk's group.

Recommendations

• A note on the relation between Hartnell’s firefighter problem and growth of groups
• Fire retainment on Cayley graphs
• The coarse geometry of Hartnell's firefighter problem on infinite graphs
• Firefighting on trees and Cayley graphs
• A generalization of the firefighter problem on \(\mathbb Z \times \mathbb Z\)

Cites work

• A note on the relation between Hartnell’s firefighter problem and growth of groups
• Fire containment in grids of dimension three and higher
• Firefighting on trees and Cayley graphs
• Isoperimetricity for groups and manifolds
• The coarse geometry of Hartnell's firefighter problem on infinite graphs

Cited in

(7)

• Fire retainment on Cayley graphs
• Surviving rate of graphs and firefighter problem
• Multi-layered planar firefighting
• Coarse geometry of the fire retaining property and group splittings
• The coarse geometry of Hartnell's firefighter problem on infinite graphs
• The branching number of intermediate growth trees
• The lamplighter groups have infinite weak cop number

This page was built for publication: The firefighter problem on polynomial and intermediate growth groups

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