##### Department of Mathematics,

University of California San Diego

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

### Math 295 - Mathematics Colloquium

## Alan Frieze

#### Carnegie-Mellon University

## On the cover time of dense and random graphs

##### Abstract:

The cover time of a graph $G$ is the maximum over vertices $v\in V(G)$ of the expected time for a simple random walk to visit all vertices of $G$, starting at $v$. We will review what we know about this question and then focus on two recent results. {\bf Dense Graphs:} We consider abritrary graphs $G$ with $n$ vertices and minimum degree at least $\delta n$ where $\delta>0$ is constant. If the conductance of $G$ is sufficiently large then we obtain an asymptotic expression for the cover time $C_G$ of $G$ as the solution to some explicit transcendental equation. Failing this, if the mixing time of a random walk on $G$ is of a lesser magnitude than the cover time, then we can obtain an asymptotic deterministic estimate via a decomposition into a bounded number of dense subgraphs with high conductance. Failing this we give a deterministic asymptotic 2-approximation of $C_G$. Joint work with Colin Cooper and Wesley Pegden. {\bf Emerging Giant:} Let $p=\frac{1+\epsilon}{n}$. It is known that if $N=\epsilon^3n\to\infty$ then w.h.p. $G_{n,p}$ has a unique giant largest component. We show that if in additon, $\epsilon=\epsilon(n)\to 0$ then w.h.p. the cover time of $G_{n,p}$ is asymptotic to $n\log^2N$. Joint work with Wesley Pegden and Tomasz Tkocz.

Host: Jacques Verstraete

### January 8, 2019

### 2:00 PM

### AP&M 6402

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