All Articles

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