Abstract: Proving a 2009 conjecture of Itai Benjamini, we show: For any C there is c > 0 so that for any simple random walk on an n-vertex graph G, the probability that the first Cn steps of the walk see every vertex is less than exp[-cn]. A first ingredient in the proof of this is a similar statement for Markov chains in which all transition probabilities are less than a suitable function of C. Joint with Quentin Dubroff.
Event Details
In-person Seminar - Jeff Kahn - Linear cover time is exponentially unlikely
- Event Date: October 7, 2021
- Event Start Time: 1:20 PM
- Event End Time: 2:20 PM
- Event Type: Mathematical Physics In Person Seminar
- Event Location: Hill Center 705