Cover times, blanket times, and majorizing measures

DOI10.4007/ANNALS.2012.175.3.8zbMATH Open1250.05098arXiv1004.4371OpenAlexW2019415463MaRDI QIDQ431644

Author name not available (Why is that?)

Publication date: 29 June 2012

Published in: (Search for Journal in Brave)

Abstract: We exhibit a strong connection between cover times of graphs, Gaussian processes, and Talagrand's theory of majorizing measures. In particular, we show that the cover time of any graph $G$ is equivalent, up to universal constants, to the square of the expected maximum of the Gaussian free field on $G$, scaled by the number of edges in $G$. This allows us to resolve a number of open questions. We give a deterministic polynomial-time algorithm that computes the cover time to within an O(1) factor for any graph, answering a question of Aldous and Fill (1994). We also positively resolve the blanket time conjectures of Winkler and Zuckerman (1996), showing that for any graph, the blanket and cover times are within an O(1) factor. The best previous approximation factor for both these problems was $O((loglogn{)}^2)$ for $n$-vertex graphs, due to Kahn, Kim, Lovasz, and Vu (2000).

Full work available at URL: https://arxiv.org/abs/1004.4371

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Cover times, blanket times, and majorizing measures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q431644)