Combinatorics Seminar
When: Sunday, December 19, 10am
Where: Schreiber 309
Speaker: Ori Gurel-Gurevich, University of British Columbia
Title: The unlikeliness of being covered
Abstract:
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.