Cover times, blanket times, and majorizing measures - Mathematics > ProbabilityReportar como inadecuado

Cover times, blanket times, and majorizing measures - Mathematics > Probability - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: We exhibit a strong connection between cover times of graphs, Gaussianprocesses, and Talagrand-s theory of majorizing measures. In particular, weshow that the cover time of any graph $G$ is equivalent, up to universalconstants, 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 numberof open questions. We give a deterministic polynomial-time algorithm thatcomputes the cover time to within an O1 factor for any graph, answering aquestion of Aldous and Fill 1994. We also positively resolve the blanket timeconjectures of Winkler and Zuckerman 1996, showing that for any graph, theblanket and cover times are within an O1 factor. The best previousapproximation factor for both these problems was $O\log \log n^2$ for$n$-vertex graphs, due to Kahn, Kim, Lovasz, and Vu 2000.

Autor: Jian Ding, James R. Lee, Yuval Peres



Documentos relacionados