The Mixing Time of the Giant Component of a Random Graph

被引：36

作者：

Benjamini, Itai ^{[1
]}

Kozma, Gady ^{[1
]}

Wormald, Nicholas ^{[2
]}

机构：

[1] Weizmann Inst Sci, Dept Math, IL-76100 Rehovot, Israel

[2] Monash Univ, Sch Math Sci, Clayton, Vic 3800, Australia

来源：

RANDOM STRUCTURES & ALGORITHMS | 2014年 / 45卷 / 03期

基金：

以色列科学基金会; 加拿大自然科学与工程研究理事会;

关键词：

mixing time; random walk; random graph; expander; giant component; INCIPIENT INFINITE CLUSTER; SIMPLE RANDOM-WALK; PERCOLATION; DIAMETER;

D O I：

10.1002/rsa.20539

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We show that the total variation mixing time of the simple random walk on the giant component of supercritical G(n,p) and G(n,m) is Theta(log(2) n). This statement was proved, independently, by Fountoulakis and Reed. Our proof follows from a structure result for these graphs which is interesting in its own right. We show that these graphs are "decorated expanders" - an expander glued to graphs whose size has constant expectation and exponential tail, and such that each vertex in the expander is glued to no more than a constant number of decorations. (C) 2014 Wiley Periodicals, Inc.

引用

页码：383 / 407

页数：25

共 50 条

[21] The Best Mixing Time for Random Walks on Trees
Andrew Beveridge
Jeanmarie Youngblood
Graphs and Combinatorics, 2016, 32 : 2211 - 2239
[22] The Best Mixing Time for Random Walks on Trees
Beveridge, Andrew
Youngblood, Jeanmarie
GRAPHS AND COMBINATORICS, 2016, 32 (06) : 2211 - 2239
[23] Isoperimetric inequalities and mixing time for a random walk on a random point process
Caputo, Pietro
Faggionato, Alessandra
ANNALS OF APPLIED PROBABILITY, 2007, 17 (5-6) : 1707 - 1744
[24] On the largest component of the random graph at a nearcritical stage
Pittel, B
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2001, 82 (02) : 237 - 269
[25] MIXING TIMES OF RANDOM WALKS ON DYNAMIC CONFIGURATION MODELS
Avena, Luca
Guldas, Hakan
van der Hofstad, Remco
den Hollander, Frank
ANNALS OF APPLIED PROBABILITY, 2018, 28 (04) : 1977 - 2002
[26] Random graph asymptotics on high-dimensional tori II: volume, diameter and mixing time
Markus Heydenreich
Remco van der Hofstad
Probability Theory and Related Fields, 2011, 149 : 397 - 415
[27] Uniform mixing time for random walk on lamplighter graphs
Komjathya, Julia
Miller, Jason
Peres, Yuval
ANNALES DE L INSTITUT HENRI POINCARE-PROBABILITES ET STATISTIQUES, 2014, 50 (04): : 1140 - 1160
[28] Component structure of the vacant set induced by a random walk on a random graph
Cooper, Colin
Frieze, Alan
PROCEEDINGS OF THE TWENTY-SECOND ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2011, : 1211 - 1221
[29] Building a random network with a given expected giant component
Lorenzo Federico
Ayoub Mounim
ANNALI DELL'UNIVERSITA' DI FERRARA, 2025, 71 (1)
[30] Mixing and relaxation time for random walk on wreath product graphs
Komjathy, Julia
Peres, Yuval
ELECTRONIC JOURNAL OF PROBABILITY, 2013, 18 : 1 - 23

← 1 2 3 4 5 →