# The evolution of the mixing rate of a simple random walk on the giant component of a random graph

Research output: Contribution to journal › Article

## Standard

**The evolution of the mixing rate of a simple random walk on the giant component of a random graph.** / Fountoulakis, Nikolaos; Reed, BA.

Research output: Contribution to journal › Article

## Harvard

*Random Structures and Algorithms*, vol. 33, no. 1, pp. 68-86. https://doi.org/10.1002/rsa.20210

## APA

*Random Structures and Algorithms*,

*33*(1), 68-86. https://doi.org/10.1002/rsa.20210

## Vancouver

## Author

## Bibtex

}

## RIS

TY - JOUR

T1 - The evolution of the mixing rate of a simple random walk on the giant component of a random graph

AU - Fountoulakis, Nikolaos

AU - Reed, BA

PY - 2008/8/1

Y1 - 2008/8/1

N2 - In this article 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 O(root ln n), proving that the mixing time in this case is Theta((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 Theta(ln n/ ln d) a.a.s.. We proved these results during the 2003-04 academic year. Similar results but for constant d were later proved independently by Benjamini et al. in [3]. (C) 2008 Wiley Periodicals, Inc.

AB - In this article 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 O(root ln n), proving that the mixing time in this case is Theta((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 Theta(ln n/ ln d) a.a.s.. We proved these results during the 2003-04 academic year. Similar results but for constant d were later proved independently by Benjamini et al. in [3]. (C) 2008 Wiley Periodicals, Inc.

KW - random graph

KW - giant component

KW - mixing time

U2 - 10.1002/rsa.20210

DO - 10.1002/rsa.20210

M3 - Article

VL - 33

SP - 68

EP - 86

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 1

ER -