Loading Events

« All Events

On the cover time of two classes of graph

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

Alan Frieze (Carnegie Mellon University)

E18-304

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 sufficiently 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 = ϵ3n → ∞ then w.h.p. Gn,p has a unique giant largest component. We show that if in addition, if ϵ=ϵ(n) → 0 then w.h.p. the cover time of Gn,p is asymptotic to n log2 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.

Details

Date:
October 26
Time:
11:00 am - 12:00 pm
Event Category:

Venue

E18-304
50 Ames Street
Cambridge, MA 02139

Other

Speaker Name(s)
Alan Frieze (Carnegie Mellon University)
speaker URL
https://www.math.cmu.edu/~af1p/