printable pdf
比利时vs摩洛哥足彩 ,
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

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