UC Davis Mathematics

Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Linear cover time is exponentially unlikely

Mathematical Physics & Probability

Speaker: Ben Morris, UC Davis
Location: 1147 MSB
Start time: Wed, Jan 26 2011, 4:10PM

We show that the probability that a simple random walk covers a finite, bounded degree graph in linear time is exponentially small. More precisely, for every D and C, there exists a=a(D,C)>0 such that for any graph G, with n vertices and maximal degree D, the probability that a simple random walk, started anywhere in G, will visit every vertex of G in its first Cn steps is at most exp(-an). Joint work with Itai Benjamini and Ori Gurel-Gurevich.