# More precise statement about lower bounds on the cover time of general graphs

Uriel Feige has shown in 1995 in his paper "A Tight Lower Bound on the Cover Time for Random Walks on Graphs", the following result:

For any graph $G$ on $n$ vertices, and any starting vertex $u$ $$E_u[G]\ge n\ln{n}+o(n\ln{n}).$$

Here $E_u[G]$ denotes the cover time, that is, the expected number of steps that it takes a walk that starts at $u$ to visit all vertices of $G$.

Let $C_u[G]$ denote the number of steps that it takes a walk that starts at $u$ to visit all vertices of $G$. In that case, $E_u[G] = \mathbb{E}(C_u[G])$. Say that an event occurs with high probability (or whp) if it's probability tends to $1$ when $n$ tends to $\infty$. Clearly, if for a vertex $u$, $C_u[G]\ge n\ln{n}+o(n\ln{n})$ whp, then $E_u[G]\ge n\ln{n} + o(n\ln{n})$. However, the opposite does not follow.

Still, is it true that the following (stronger) result holds?

For any graph $G$ on $n$ vertices, and any starting vertex $u$ $$C_u[G]\ge n\ln{n}+o(n\ln{n})$$ whp.

If not, is there any non-trivial lower bound for general graphs? For specific graphs? It is known, for example, for the complete graph $K_n$ (this is simply a coupon-collector problem).

A general result of Aldous is that if the expected cover time is much larger than the maximal expected hitting time (maximum over all vertices) then the cover time concentrates, i.e. $C/EC\sim 1$. The bound is non asymptotic. See Theorem 1 in http://scf.berkeley.edu/~aldous/Papers/me47.pdf