- This event has passed.
Stochastics and Statistics Seminar
On the cover time of two classes of graph
October 26, 2018 @ 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 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.
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.
Website: https://www.math.cmu.edu/~af1p/
