ACO The ACO Seminar (2021–2022)

November 4, 3:30pm, Wean 8220
Quentin Dubroff, Rutgers University
Linear cover time is exponentially unlikely

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.


Back to the ACO home page Back to the ACO Seminar schedule