On the cover time of the emerging giant

Abstract

Let $p=\frac{1+\epsilon }{n}$. It is known that if $N={\epsilon }^{3}n\to \infty$ then w.h.p. $G_{n,p}$ has a unique giant largest component. We show that if in addition, $\epsilon =\epsilon (n)\to 0$ then w.h.p. the cover time of $G_{n,p}$ is asymptotic to $n{\log }^{2}N$; previously Barlow, Ding, Nachmias and Peres had shown this up to constant multiplicative factors.

arXiv commentWe fixed an error in the proof