Skip to content
DraconiticResearch
Search Sources API
201,683 studies31 sourcesUpdated 43 min ago
PreprintCC BY 4.0arXiv

Second-Order Cover Time of Random Regular Graphs

  • Lisa Hartung
  • Andreas Klippel
Open at sourcePDFDOICite

Abstract

Let GN be a uniform random d-regular graph on N vertices, with d≥3 fixed. Cooper and Frieze showed that the cover time of simple random walk on GN is asymptotically θdNlog N, where θd=(d−1)/(d−2). We prove that, in probability over the graph and uniformly in the starting point, (Tcov−θdNlog 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 the latter with capacities on the infinite d-regular tree. We also obtain Gumbel limits for lazy, continuous-time and finitely many independent walks. For the unvisited set, we prove weighted laws of large numbers, spatial Poisson limits in the cover-time window, and joint Poisson limits for fixed tree-component shapes in their disappearance windows.

Related

  1. A second-moment proof of quenched equals annealed for the Potts model on random regular graphs
    Remco van der Hofstad, Kai-Chun Huang, Noela Müller +1
    arXivPreprintCC BY-NC-SA 4.0Full textProbabilityarXiv
  2. Edge universality of random regular graphs of growing degrees
    Jiaoyang Huang, Horng‐Tzer Yau
    The Annals of ProbabilityPeer-reviewedLicence not statedFull text16 citedStatisticsOpenAlex
  3. When are random regular triangle-free graphs bipartite?
    Gregory DeCamillis, Pu Gao
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Analysis of Polynomial Threshold Functions on Random Regular Graphs: Computational Complexity of Detecting Noisy Random Lifts
    Xifan Yu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. The singularity probability of dense random regular graphs
    Zeyan Song, Hanchao Wang, Shengyan Yin +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{hartung2026secondorder,
  title = {{Second-Order Cover Time of Random Regular Graphs}},
  author = {Lisa Hartung and Andreas Klippel},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.26363},
  eprint = {2610.26363},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.26363},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Second-Order Cover Time of Random Regular Graphs
AU  - Lisa Hartung
AU  - Andreas Klippel
PY  - 2026
DA  - 2026/10/19
PB  - arXiv
DO  - 10.48550/arxiv.2610.26363
UR  - https://arxiv.org/abs/2610.26363
AB  - Let G_N be a uniform random d-regular graph on N vertices, with d≥3 fixed. Cooper and Frieze showed that the cover time of simple random walk on G_N is asymptotically θ_dNlog N, where θ_d=(d−1)/(d−2). We prove that, in probability over the graph and uniformly in the starting point, (T_cov−θ_dNlog 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 the latter with capacities on the infinite d-regular tree. We also obtain Gumbel limits for lazy, continuous-time and finitely many independent walks. For the unvisited set, we prove weighted laws of large numbers, spatial Poisson limits in the cover-time window, and joint Poisson limits for fixed tree-component shapes in their disappearance windows.
ER  -