Meeting and coalescence times for random walks in the largest component of the Erdős-Rényi random graph
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.13183
curl -X POST /api/v1/records/arxiv/2607.13183/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.13183/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'