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 条

[1] The evolution of the mixing rate of a simple random walk on the giant component of a random graph
Fountoulakis, N.
Reed, B. A.
RANDOM STRUCTURES & ALGORITHMS, 2008, 33 (01) : 68 - 86
[2] The cover time of the giant component of a random graph
Cooper, Colin
Frieze, Alan
RANDOM STRUCTURES & ALGORITHMS, 2008, 32 (04) : 401 - 439
[3] Anatomy of a Young Giant Component in the Random Graph
Ding, Jian
Kim, Jeong Han
Lubetzky, Eyal
Peres, Yuval
RANDOM STRUCTURES & ALGORITHMS, 2011, 39 (02) : 139 - 178
[4] On a random graph with immigrating vertices: Emergence of the giant component
Aldous, DJ
Pittel, B
RANDOM STRUCTURES & ALGORITHMS, 2000, 17 (02) : 79 - 102
[5] Giant component of the soft random geometric graph
Penrose, Mathew D.
ELECTRONIC COMMUNICATIONS IN PROBABILITY, 2022, 27
[6] MIXING TIME OF NEAR-CRITICAL RANDOM GRAPHS
Ding, Jian
Lubetzky, Eyal
Peres, Yuval
ANNALS OF PROBABILITY, 2012, 40 (03) : 979 - 1008
[7] Phase transition for the vacant set left by random walk on the giant component of a random graph
Wassmer, Tobias
ANNALES DE L INSTITUT HENRI POINCARE-PROBABILITES ET STATISTIQUES, 2015, 51 (02): : 756 - 780
[8] Giant vacant component left by a random walk in a random d-regular graph
Cerny, Jiri
Teixeira, Augusto
Windisch, David
ANNALES DE L INSTITUT HENRI POINCARE-PROBABILITES ET STATISTIQUES, 2011, 47 (04): : 929 - 968
[9] The Cover Time of the Giant Component of a Random Graph (vol 32, pg 401, 2008)
Cooper, Colin
Frieze, Alan
RANDOM STRUCTURES & ALGORITHMS, 2009, 34 (02) : 300 - 304
[10] How to determine if a random graph with a fixed degree sequence has a giant component
Joos, Felix
Perarnau, Guillem
Rautenbach, Dieter
Reed, Bruce
2016 IEEE 57TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2016, : 695 - 703

← 1 2 3 4 5 →