pipette
ESEspañol

Second-Order Cover Time of Random Regular Graphs

Lisa Hartung, Andreas Klippel

Preprint

In the authors' words

Let be a uniform random -regular graph on vertices, with fixed. Cooper and Frieze showed that the cover time of simple random walk on is asymptotically , where . We prove that, in probability over the graph and uniformly in the starting point, 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 -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.

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.