Mathematics – Probability
Scientific paper
2010-01-05
Mathematics
Probability
14 pages, to appear in CPC
Scientific paper
The cover time of a graph is a celebrated example of a parameter that is easy to approximate using a randomized algorithm, but for which no constant factor deterministic polynomial time approximation is known. A breakthrough due to Kahn, Kim, Lovasz and Vu yielded a (log log n)^2 polynomial time approximation. We refine this upper bound, and show that the resulting bound is sharp and explicitly computable in random graphs. Cooper and Frieze showed that the cover time of the largest component of the Erdos-Renyi random graph G(n,c/n) in the supercritical regime with c>1 fixed, is asymptotic to f(c) n \log^2 n, where f(c) tends to 1 as c tends to 1. However, our new bound implies that the cover time for the critical Erdos-Renyi random graph G(n,1/n) has order n, and shows how the cover time evolves from the critical window to the supercritical phase. Our general estimate also yields the order of the cover time for a variety of other concrete graphs, including critical percolation clusters on the Hamming hypercube {0,1}^n, on high-girth expanders, and on tori Z_n^d for fixed large d. For the graphs we consider, our results show that the blanket time, introduced by Winkler and Zuckerman, is within a constant factor of the cover time. Finally, we prove that for any connected graph, adding an edge can increase the cover time by at most a factor of 4.
Barlow Martin T.
Ding Jian
Nachmias Asaf
Peres Yuval
No associations
LandOfFree
The evolution of the cover time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The evolution of the cover time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The evolution of the cover time will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-539755