# Discrete Math Seminar: Linear cover time is exponentially unlikely

**Author: Lona** | Image: Lona

**Author: Lona** | Image: Lona

Speaker: Quentin Dubroff (Rutgers University)

Abstract: Proving a 2009 conjecture of Itai Benjamini, we show: For any $C$, there is $a>0$ such that for any simple random walk on an $n$-vertex graph $G$, the probability that the first $Cn$ steps of the walk hit every vertex of $G$ is at most $exp[−an]$. A first ingredient of the proof is a similar statement for Markov chains in which all transition probabilities are less than a suitable function of $C$. Joint with Jeff Kahn