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

Abstract

We prove tight asymptotics of the cover time $\ddot{I}{„}_{\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 $\hat{I}»\in (0,1)$. For $b>2$, we show that $\ddot{I}{„}_{\mathrm{cov}}(d)=x_{\star }d+\hat{I}{»}^{-1}\log d+O_{\mathbb{P}}(1)$. For $b=2$, we show that $\ddot{I}{„}_{\mathrm{cov}}(d)=x_{\star }d+\ddot{I}{‡}^{-1}\log \log d+O_{\mathbb{P}}(1)$. Here, $x_{\star }$ and $\ddot{I}‡$ are explicit positive constants depending only on $b$ and $\hat{I}»$. 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.

50 pages, 8 figures