Linear cover time is exponentially unlikely

Quentin Dubroff, Jeff Kahn

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 rand…