The mixing time of the giant component of a random graph (Q2930052)

The Erdős-Rényi random graph \(\mathcal{G}(n, m)\) is a graph chosen uniformly at random from all graphs with \(n\) vertices and \(m\) edges. One of the fundamental facts about these random graphs is that if \(c > 1\) and \(m \approx cn/2\), then there is asymptotically almost surely (a.a.s.) a unique linear-sized connected component, referred to as the giant component. In this paper, the authors study simple random walks on the giant component of \(\mathcal{G}(n, m)\), showing that the total variation mixing time for such a random walk is a.a.s. \(\Theta(\log^2 n)\).NEWLINENEWLINETheir proof divides into two steps. First, the authors show that the giant component of \(\mathcal{G}(n, m)\) is a.a.s. a decorated expander, an expander together with a number of small components such that each vertex is contained in a bounded number of these components. Then they show that the mixing time on a decorated expander of this variety is as required.NEWLINENEWLINESimilar results were proved independently by \textit{N. Fountoulakis} and \textit{B. A. Reed} [Probab. Theory Relat. Fields 137, No. 3--4, 475--486 (2007; Zbl 1113.60073); ``The evolution of the mixing rate'', Preprint, \url{arXiv:math/0701474}] using a different method, though they worked with the binomial random graph \(\mathcal{G}(n, p)\).