Linear cover time is exponentially unlikely (Q6670804)

The article answers positively a longstanding conjecture of Benjamini (2009) that linear cover time is exponentially unlikely for random walks on graphs.\N\N\textbf{Theorem.} For any \(C > 0\), there is an \(\varepsilon > 0\) such that, for any simple graph \(G\) on a vertex set \(V\) with \(n\) vertices, if \((X_t)_{t\ge0}\) is the usual simple random walk on \(G\), then\N\[\N\mathbb P\bigl( \{X_t\}_{t=0}^{Cn} = V \bigr) \le e^{-\varepsilon n}.\N\]\N\textit{I. Benjamini} et al. [Probab. Theory Relat. Fields 155, No. 1--2, 451--461 (2013; Zbl 1259.05154)] proved this when the maximum degree \(\Delta\) of \(G\) is bounded -- with \(\varepsilon\) depending on \(\Delta\). \textit{A. Yehudayoff} [Chic. J. Theor. Comput. Sci. 2012, Article No. 3, 6 p. (2012; Zbl 1286.05160)] proved it for trees, as well as observing that it holds for expanders from the large-deviation bound for random walks due to \textit{D. Gillman} [SIAM J. Comput. 27, No. 4, 1203--1220 (1998; Zbl 0911.60016)].\N\NWith some minor adjustments, Dubroff and Kahn can show that, for any \(C > 0\), there exist \(\varepsilon, \alpha > 0\) such that\N\[\N\mathbb P\bigl( \bigl|\{X_t\}_{t=0}^{Cn}\bigr| \ge (1 - \alpha) n \bigr) \le e^{-\varepsilon n}.\N\]\NThe majority of their work generalises from random walks to general reversible chains -- which can be viewed as \textit{weighted} random walks.\N\N\textbf{Theorem.} Let \((X_t)_{t\ge0}\) be a reversible Markov chain on \(V\), with \(|V| = n\), with equilibrium distribution \(\pi\). Suppose that there exists a subset \(W \subseteq V\) with \(|W| \ge \alpha n\) such that \(\pi_v / \pi_w \le K\) for all \(v,w \in W\). Then,\N\[\N\mathbb P\bigl( \{X_t\}_{t=0}^{Cn} = V \bigr) \le \exp\bigl( - \Omega(n) \bigr),\N\]\Nwhere the implied constant depends on \(C\), \(\alpha\) and \(K\).