Infection spread for the frog model on trees

Christopher Hoffman, Tobias Johnson, Matthew Junge

Published 2017-10-16Version 1

Consider the frog model with initial density of particles $\mu$. On the infinite $d$-ary tree for $\mu = \Omega(d^2)$, we show that the set of activated sites contains a linearly expanding ball. This helps us deduce that on the full $d$-ary tree of height $n$,it takes $O(n\log n)$ steps to visit all sites of the tree with high probability. Conversely, a different argument shows that it takes $\exp(\Omega(\sqrt{n}))$ steps if $\mu=O(d)$. Both bounds are sharp. It was previously unknown whether the cover time was polynomial or superpolynomial for any value of $\mu$.