Linear cover time is exponentially unlikely

Abstract

Proving a 2009 conjecture of Itai Benjamini, we show: For any C there is an $\epsilon >0$ such that for any simple graph $G$ on $V$ of size $n$, and $X_0,\dots$ an ordinary random walk on $G$, $P(\{X_0,\dots ,X_{Cn}\}=V)<e^{-\epsilon n}.$ A first ingredient in the proof of this is a similar statement for Markov chains in which all transition probabilities are sufficiently small relative to $C$.

20 pages; appendix added