Precise cover times for branching random walks on Hamming graphs: (iterated) logarithmic corrections

Abstract

We prove tight asymptotics of the cover time $\tau_{\mathrm{cov}}(d)$ of a continuous-time branching random walk on the Hamming graph $\{0,1,\dots,b-1\}^d$, as $d\to\infty$. We focus on the slow-branching regime, where particles move at rate one and branch at rate $\lambda\in(0,1)$. For $b>2$, we show that $\tau_{\mathrm{cov}}(d)=x_\star d+\lambda^{-1}\log d+O_{\mathbb P}(1)$. For $b=2$, we show that $\tau_{\mathrm{cov}}(d)=x_\star d+\chi^{-1}\log\log d+O_{\mathbb P}(1)$. Here, $x_\star$ and $\chi$ are explicit positive constants depending only on $b$ and $\lambda$. Our results sharpen previously known linear-order estimates. The dichotomy reflects the geometry of the last uncovered region: for $b>2$, there are exponentially many antipodes, whereas the binary hypercube has a unique antipode and its neighbors govern the final coverage. Our proofs combine classic spine change of measure techniques and many-to-few estimates with a multiscale decomposition of the genealogy and a weighted martingale analysis of the early population.