Seminar Details
Linear Cover Time is Exponentially Unlikely
- Start Date: November 8, 2021
- Event Start Time: 2:00 PM
- Event End Time: 3:00 PM
- Seminar Series: Rutgers Discrete Mathematics Seminar
- Presenter(s): Quentin Dubroff - Rutgers University
- Event Location: Hill Center-Room 705
- Event Additional Info: <p>See: <a href="https://sites.google.com/view/rutgersdmseminar">https://sites.google.com/view/rutgersdmseminar</a></p>
- Presentation Type: Stand Alone Presentation
- 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.