# On the cover time of two classes of graph

## October 26 @ 11:00 am - 12:00 pm

Alan Frieze (Carnegie Mellon University)

E18-304

### Event Navigation

**Abstract:**

**Dense Graphs:**We consider abritrary graphs

*G*with n vertices and minimum degree at least n. where δ > 0 is constant. If the conductance of

*G*is suﬃciently large then we obtain an asymptotic expression for the cover time

*CG*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

*CG*.

**Emerging Giant:**Let

*p*=

^{1+ϵ}⁄

_{n}. It is known that if

*N*= ϵ

^{3}n → ∞ then w.h.p.

*G*

_{n,p}has a unique giant largest component. We show that if in addition, if ϵ=ϵ(n) → 0 then w.h.p. the cover time of

*G*

_{n,p}is asymptotic to

*n*log

^{2}

*N*.

Joint work with Wesley Pegden and Tomasz Tkocz.

** Biography: **Alan Frieze is a professor of Mathematics at Carnegie Mellon University. His main interests are in the applications of Probabilistic Combinatorics Probabilistic Combinatorics and its applications in Theoretical Computer Science and Operations Research. He received the 1991 Fulkerson Prize for his work on computing the volume of a convex body. He is a Guggenheim Fellow, a SIAM Fellow, an AMS Fellow and a Simons Fellow.