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

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

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.

Details

Original languageEnglish
Pages (from-to)68-86
Number of pages19
JournalRandom Structures and Algorithms
Volume33
Issue number1
Publication statusPublished - 1 Aug 2008

Keywords

  • random graph, giant component, mixing time