##### Department of Mathematics,

University of California San Diego

****************************

### Math 288 - Probability and Statistics Seminar

## Ben Morris

#### University of California at Davis

## A Large deviation bound for the cover time

##### Abstract:

For random walk on a graph, the cover time $T$ is the number of steps required to visit every vertex at least once. We prove the following large deviation bound for the cover time: For every $A>0$ and $d>0$ there is a constant $c>0$ such that for all $n$ and graphs on $n$ vertices of maximum degree $d$, we have $P(T < An) < \exp(-cn)$. \\ \noindent Joint work with Itai Benjamini and Ori Gurel-Gurevich.

Host: Jason Schweinsberg

### July 22, 2010

### 10:00 AM

### AP&M 7321

****************************