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

Abstract

We prove tight asymptotics of the cover time $τ_{\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 $λ\in(0,1)$. For $b>2$, we show that $τ_{\mathrm{cov}}(d)=x_\star d+λ^{-1}\log d+O_{\mathbb P}(1)$. For $b=2$, we show that $τ_{\mathrm{cov}}(d)=x_\star d+χ^{-1}\log\log d+O_{\mathbb P}(1)$. Here, $x_\star$ 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.

Disclosure

“Acknowledgments The author has supplied the key mathematical arguments to generative AI. During the revision process, GPT 5.5 pro and 5.6 pro were used to prepare figures and simulations, to expand omitted details, to review literature, and to produce neater proofs, particularly the elementary lemmas in the appendices. Every AI-assisted argument has been reviewed”

PDF page 33

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T19:10:44.162146Z

Structural counts