Discrete Math Seminar: Linear cover time is exponentially unlikely

CATEGORIES: Math, Seminar
January 31, 2023, 2:10-3:25pm | Zoom

Speaker: Quentin Dubroff (Rutgers University)

Abstract: Proving a 2009 conjecture of Itai Benjamini, we show: For any , there is �>0 such that for any simple random walk on an -vertex graph , the probability that the first �� steps of the walk hit every vertex of  is at most exp⁡[−��]. 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 . Joint with Jeff Kahn