2026/07/26 by Zhenyuan Zhang
#math.PR
We prove tight asymptotics of the cover time τcov(d) of a continuous-time branching random walk on the Hamming graph \0,1,…,b-1\d, as d→∞. We focus on the slow-branching regime, where particles move at rate one and branch at rate λ∈(0,1). For b>2, we show that τcov(d)=x_⋆ d+λ-1log d+O\mathbb P(1). For b=2, we show that τcov(d)=x_⋆ d+χ-1loglog d+O\mathbb P(1). Here, x_⋆ and χ are explicit positive constants depending only on b and λ. 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.