Second-Order Cover Time of Random Regular Graphs
En palabras de los autores
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.
Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.