{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T16:53:33Z","timestamp":1763830413404},"reference-count":45,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2011,2,15]],"date-time":"2011-02-15T00:00:00Z","timestamp":1297728000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2011,5]]},"abstract":"<jats:p>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, Lov\u00e1sz and Vu [25] yielded a (log log<jats:italic>n<\/jats:italic>)<jats:sup>2<\/jats:sup>polynomial time approximation. We refine the upper bound of [25], 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 Erd\u0151s\u2013R\u00e9nyi random graph<jats:italic>G<\/jats:italic>(<jats:italic>n, c<\/jats:italic>\/<jats:italic>n<\/jats:italic>) in the supercritical regime with<jats:italic>c<\/jats:italic>&gt; 1 fixed, is asymptotic to \u03d5(<jats:italic>c<\/jats:italic>)<jats:italic>n<\/jats:italic>log<jats:sup>2<\/jats:sup><jats:italic>n<\/jats:italic>, where \u03d5(<jats:italic>c<\/jats:italic>) \u2192 1 as<jats:italic>c<\/jats:italic>\u2193 1. However, our new bound implies that the cover time for the critical Erd\u0151s\u2013R\u00e9nyi random graph<jats:italic>G<\/jats:italic>(<jats:italic>n<\/jats:italic>, 1\/<jats:italic>n<\/jats:italic>) has order<jats:italic>n<\/jats:italic>, 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}<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup>, on high-girth expanders, and on tori \u2124<jats:italic><jats:sup>d<\/jats:sup><jats:sub>n<\/jats:sub><\/jats:italic>for fixed large<jats:italic>d<\/jats:italic>. This approach also gives a simpler proof of a result of Aldous [2] that the cover time of a uniform labelled tree on<jats:italic>k<\/jats:italic>vertices is of order<jats:italic>k<\/jats:italic><jats:sup>3\/2<\/jats:sup>. For the graphs we consider, our results show that the<jats:italic>blanket<\/jats:italic>time, introduced by Winkler and Zuckerman [45], 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.<\/jats:p>","DOI":"10.1017\/s0963548310000489","type":"journal-article","created":{"date-parts":[[2011,2,15]],"date-time":"2011-02-15T16:28:54Z","timestamp":1297787334000},"page":"331-345","source":"Crossref","is-referenced-by-count":15,"title":["The Evolution of the Cover Time"],"prefix":"10.1017","volume":"20","author":[{"given":"MARTIN T.","family":"BARLOW","sequence":"first","affiliation":[]},{"given":"JIAN","family":"DING","sequence":"additional","affiliation":[]},{"given":"ASAF","family":"NACHMIAS","sequence":"additional","affiliation":[]},{"given":"YUVAL","family":"PERES","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2011,2,15]]},"reference":[{"key":"S0963548310000489_ref24","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(200003)16:2<131::AID-RSA1>3.0.CO;2-3"},{"key":"S0963548310000489_ref32","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010305"},{"key":"S0963548310000489_ref27","first-page":"579","article-title":"The Galton\u2013Watson process with mean one and finite variance","volume":"11","author":"Kesten","year":"1966","journal-title":"Teor. Verojatnost. i Primenen."},{"key":"S0963548310000489_ref28","volume-title":"Random Mappings","author":"Kolchin","year":"1986"},{"key":"S0963548310000489_ref38","doi-asserted-by":"publisher","DOI":"10.1214\/07-AOP358"},{"key":"S0963548310000489_ref20","volume-title":"An Introduction to Probability Theory and its Applications","author":"Feller","year":"1971"},{"key":"S0963548310000489_ref14","unstructured":"[14] Ding J. , Lee J. R. and Peres Y. Cover times, blanket times, and majorizing measures. Preprint. Available at: http:\/\/arxiv.org\/abs\/1004.4371."},{"key":"S0963548310000489_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20201"},{"key":"S0963548310000489_ref12","unstructured":"[12] Ding J. , Kim J. H. , Lubetzky E. and Peres Y. Anatomy of a young giant component in the random graph. Random Struct. Alg., to appear. Available at: http:\/\/arxiv.org\/abs\/0906.1839."},{"key":"S0963548310000489_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-006-0152-8"},{"key":"S0963548310000489_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0801-3_7"},{"key":"S0963548310000489_ref18","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060106"},{"key":"S0963548310000489_ref25","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892134"},{"key":"S0963548310000489_ref6","doi-asserted-by":"publisher","DOI":"10.2307\/1999405"},{"key":"S0963548310000489_ref33","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20011"},{"key":"S0963548310000489_ref30","unstructured":"[30] Kozma G. and Nachmias A. A note about critical percolation on finite graphs. J. Theoret. Probab., to appear."},{"key":"S0963548310000489_ref36","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58179-0_49"},{"key":"S0963548310000489_ref16","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","article-title":"On random graphs I","volume":"6","author":"Erd\u0151s","year":"1959","journal-title":"Publ. Math. Debrecen"},{"key":"S0963548310000489_ref31","volume-title":"Markov Chains and Mixing Times","author":"Levin","year":"2009"},{"key":"S0963548310000489_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90019-8"},{"key":"S0963548310000489_ref42","volume-title":"Multidimensional Diffusion Processes","author":"Stroock","year":"1979"},{"key":"S0963548310000489_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01270385"},{"key":"S0963548310000489_ref39","unstructured":"[39] Nachmias A. and Peres Y. Critical percolation on random regular graphs. Random Struct. Alg., to appear."},{"key":"S0963548310000489_ref13","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548310000301"},{"key":"S0963548310000489_ref3","unstructured":"[3] Aldous D. and Fill J. A. Reversible Markov Chains and Random Walks on Graphs. In preparation. http:\/\/www.stat.berkeley.edu\/~aldous\/RWG\/book.html."},{"key":"S0963548310000489_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/BF00532583"},{"key":"S0963548310000489_ref44","doi-asserted-by":"publisher","DOI":"10.1007\/BF01046996"},{"key":"S0963548310000489_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/0022-1236(67)90017-1"},{"key":"S0963548310000489_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01048271"},{"key":"S0963548310000489_ref22","unstructured":"[22] Heydenreich M. and van der Hofstad R. Random graph asymptotics on high-dimensional tori II: Volume, diameter and mixing time. Probability Theory and Related Fields, to appear."},{"key":"S0963548310000489_ref34","volume-title":"Probability on Trees and Networks","author":"Lyons","year":"2008"},{"key":"S0963548310000489_ref35","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176991686"},{"key":"S0963548310000489_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-009-0208-4"},{"key":"S0963548310000489_ref17","first-page":"343","article-title":"On the evolution of random graphs","volume":"38","author":"Erd\u0151s","year":"1961","journal-title":"Bull. Inst. Internat. Statist."},{"key":"S0963548310000489_ref37","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-009-0032-4"},{"key":"S0963548310000489_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-3352-7_8"},{"key":"S0963548310000489_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(91)90149-T"},{"key":"S0963548310000489_ref23","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548310000489_ref19","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060406"},{"key":"S0963548310000489_ref40","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100033879"},{"key":"S0963548310000489_ref41","doi-asserted-by":"publisher","DOI":"10.1214\/07-AOP361"},{"key":"S0963548310000489_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20051"},{"key":"S0963548310000489_ref4","first-page":"218","volume-title":"20th Annual Symposium on Foundations of Computer Science","author":"Aleliunas","year":"1979"},{"key":"S0963548310000489_ref43","volume-title":"The Generic Chaining: Upper and Lower Bounds of Stochastic Processes","author":"Talagrand","year":"2005"},{"key":"S0963548310000489_ref45","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199612)9:4<403::AID-RSA4>3.0.CO;2-0"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548310000489","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,5]],"date-time":"2023-06-05T06:39:31Z","timestamp":1685947171000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548310000489\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,2,15]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,5]]}},"alternative-id":["S0963548310000489"],"URL":"https:\/\/doi.org\/10.1017\/s0963548310000489","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,2,15]]}}}