On the Cover Time for Random Walks on Random Graphs

Abstract

The cover time, C, for a simple random walk on a realization, G_N, of [Gscr ](N, p), the random graph on N vertices where each two vertices have an edge between them with probability p independently, is studied. The parameter p is allowed to decrease with N and p is written on the form f(N)/N, where it is assumed that f(N)[ges ]c log N for some c>1 to asymptotically ensure connectedness of the graph. It is shown that if f(N) is of higher order than log N, then, with probability 1−o(1), (1−ε)N log N[les ]E[C[mid ]G_N] [les ](1+ε)N log N for any fixed ε>0, whereas if f(N)=O(log N), there exists a constant a>0 such that, with probability 1−o(1), E[C[mid ]G_N] [ges ](1+a)N log N. It is furthermore shown that if f(N) is of higher order than (log N)³ then Var(C[mid ]G_N)= o((N log N)²) with probability 1−o(1), so that with probability 1−o(1), the stronger statement that (1−ε)N log N[les ]C[les ](1+ε)N log N holds.