Meeting and coalescence times for random walks in the largest component of the Erdős-Rényi random graph

Abstract

We prove that the stationary and worst-case expected meeting times of two independent continuous-time random walks on the largest component of the Erdős-Rényi random graph $G(n,p)$ have order $n$ throughout the strictly supercritical, the slightly supercritical and the critical regimes. Using these bounds along with a fine-tuned combination of comparison inequalities due to Oliveira (2012) and Kanade-Mallmann-Trenn-Sauerwald (KMS, 2023), we deduce that expected coalescence time and full voter-model consensus also have order $n$ throughout these three regimes.

Disclosure

“lure probability at most η/2, gives the displayed critical-window estimate after changing constants. Duality transfers all upper bounds from full coalescence to voter consensus. Tool and computational resource disclosure The authors used AI-assisted tools during the preparation of this manuscript for editorial and expository support, including improving formulations, organization, and presentation. These tools were not used as authors and did not replace the authors’ mathematical judg”

PDF page 44

Classification

Brainstorming or outlining

Multiplier

2

Verified

2026-08-23T18:53:58.506346Z

Structural counts