论文标题
多项式和中间增长组的消防员问题
The firefighter problem on polynomial and intermediate growth groups
论文作者
论文摘要
我们证明，任何$ d $多项式增长的Cayley Graph $ g $都不满足$ \ {f（n）\} $ - 对于任何$ f = o（n^{d-2}）$的容器。这解决了消防员问题的渐近行为，众所周知，$ cn^{d-2} $消防员已经足够了，回答和加强了Develin和Hartke的猜想。我们还证明，中间生长辣椒图不满足多项式遏制，并根据组的生长速率给出明确的下限。当有更多的几何信息可用时，例如Grigorchuk的组，这些界限可以进一步改善。
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 $Cn^{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.
