All Articles

Discrete Math Seminar: Linear cover time is exponentially unlikely

Author: Lona | Image: Lona

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