A spectral characterization for concentration of the cover time

Abstract

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 transitivity) that the maximal hitting time of a state is of the same order as the average hitting time.

19 pages. Some typos were fixed in this version

References in corpus (2)

• Characterization of cutoff for reversible Markov chains
• Tight inequalities among set hitting times in Markov chains

Cited by in corpus (2)

• Mean Field Behavior during the Big Bang Regime for Coalescing Random Walks
• Cutoff thermalization for Ornstein-Uhlenbeck systems with small Lévy noise in the Wasserstein distance