Combinatorics Seminar

When: Sunday, December 19, 10am
Where: Schreiber 309
Speaker: Ori Gurel-Gurevich, University of British Columbia
Title: The unlikeliness of being covered


We will show that the probability that a simple random walk will cover 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 Ben Morris.