The Evolution of the Mixing Rate

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

In this paper we present a study of the mixing time of a random walk on the largest component of a supercritical random graph, also known as the giant component. We identify local obstructions that slow down the random walk, when the average degree d is at most (ln n lnln n)^{1/2}, proving that the mixing time in this case is O((ln n/d)^2) asymptotically almost surely. As the average degree grows these become negligible and it is the diameter of the largest component that takes over, yielding mixing time O(ln n/ln d). We proved these results during the 2003-04 academic year. Similar results but for constant d were later proved independently by I. Benjamini, G. Kozma and N. Wormald.
15 pages

Keywords

Combinatorics, Probability, 05C80 (Primary), 60J10 (Secondary)

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/122137

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0701474
 http://arxiv.org/abs/math/0701474

Collections

arXiv