Cover time and spectral gap for reversible random walks

Question

I am looking for a theorem which say something like this: if the cover time of a reversible Markov chain is small, then the spectral gap is large. Here the spectral gap means $1-|\lambda_2|$, that is, we ignore the smallest eigenvalue of the chain.

The only result I was able to find in this direction is from Bounds on the Cover Time, Broder and Karlin, FOCS 88. There it is assumed that the transition matrix of the chain is doubly stochastic (but not necessarily reversible) and aperiodic; roughly speaking, the paper shows that under these assumptions if the cover time is $O(n \log n)$, then $1-\max(|\lambda_2|, |\lambda_n|)$ is at least $n^{-1}$.

Intuitively, it seems very plausible that if you can cover all the vertices of a graph quickly, then mixing time ought to be small. In particular, if you can cover all the vertices of a graph in $n^2$ time, surely you should be able to rule out a spectral gap of, say, $n^{-1000}$?

One possible obstacle that would break the implication between small cover time and large spectral gap is bipartiteness: on a bipartite graph, you can have a small cover time with an eigenvalue of $-1$. By in my question, I am bypassing this issue by ignoring the smallest eigenvalue.

Answer 1

Roughly speaking, the mixing time is the worst-case hitting time of the half the vertices. Cover time is a stopping time when ALL subsets of vertices are hit. In other words, it is always larger than the the mixing time. Thus is your example one cannot have mixing time $n^{1000}$ and cover time $n^2$.

Making this intuition precise requires a bit of care since we need to relate mixing times to eigenvalue gap, take not half the vertices but half the stationary distribution $\pi$, etc. None of this is difficult. Start with this paper by Lovasz and Winkler, which gives the above version of the mixing time and relates it to more standard mixing time in total variation.