Second-Order Cover Time of Random Regular Graphs
Let $G_N$ be a uniform random $d$-regular graph on $N$ vertices, with $d\ge3$ fixed. Cooper and Frieze showed that the cover time of simple random walk on $G_N$ is asymptotically $θ_dN\log N$, where $θ_d=(d-1)/(d-2)$. We prove that, in probability over the graph and uniformly in the starting point, $(T_{\rm cov}-θ_dN\log N)/(θ_dN)$ converges in distribution to a standard Gumbel law, confirming a prediction of Tishby, Biham, and Katzav [40]. The proof reduces late points to avoidance probabilities of finite sets via factorial moments, estimates these by Green-matrix capacities, and compares…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.26363
curl -X POST /api/v1/records/arxiv/2610.26363/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.26363/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'