A Spectral Characterization for Concentration of the Cover Time
A Spectral Characterization for Concentration of the Cover Time
We prove that for a sequence of finite vertex-transitive graphs of increasing sizes, the cover times are asymptotically concentrated if and only if the product of the spectral-gap and the expected cover time diverges. In fact, we prove this for general reversible Markov chains under the much weaker assumption (than …