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

Research output: Contribution to journalArticle

Standard

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

In: Random Structures and Algorithms, Vol. 33, No. 1, 01.08.2008, p. 68-86.

Research output: Contribution to journalArticle

Harvard

APA

Vancouver

Author

Bibtex

@article{3ae35946001749d8b53f70e8d0b9c8ef,
title = "The evolution of the mixing rate of a simple random walk on the giant component of a random graph",
abstract = "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.",
keywords = "random graph, giant component, mixing time",
author = "Nikolaos Fountoulakis and BA Reed",
year = "2008",
month = aug,
day = "1",
doi = "10.1002/rsa.20210",
language = "English",
volume = "33",
pages = "68--86",
journal = "Random Structures and Algorithms",
issn = "1042-9832",
publisher = "Wiley",
number = "1",

}

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 -