Premium
Critical percolation on random regular graphs
Author(s) -
Nachmias Asaf,
Peres Yuval
Publication year - 2010
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20277
Subject(s) - random graph , mathematics , limiting , brownian motion , combinatorics , excursion , percolation (cognitive psychology) , percolation threshold , graph , component (thermodynamics) , subadditivity , statistical physics , discrete mathematics , physics , statistics , thermodynamics , quantum mechanics , law , mechanical engineering , neuroscience , political science , engineering , biology , electrical resistivity and conductivity
The behavior of the random graph G ( n , p ) around the critical probability p c = $ {1 \over n} $ is well understood. When p = (1 + O ( n 1/3 )) p c the components are roughly of size n 2/3 and converge, when scaled by n −2/3 , to excursion lengths of a Brownian motion with parabolic drift. In particular, in this regime, they are not concentrated. When p = (1 ‐ ϵ( n )) p c with ϵ( n ) n 1/3 →∞ (the subcritical regime) the largest component is concentrated around 2ϵ −2 log(ϵ 3 n ). When p = (1 + ϵ( n )) p c with ϵ( n ) n 1/3 →∞ (the supercritical regime), the largest component is concentrated around 2ϵ n and a duality principle holds: other component sizes are distributed as in the subcritical regime. Itai Benjamini asked whether the same phenomenon occurs in a random d ‐regular graph. Some results in this direction were obtained by (Pittel, Ann probab 36 (2008) 1359–1389). In this work, we give a complete affirmative answer, showing that the same limiting behavior (with suitable d dependent factors in the non‐critical regimes) extends to random d ‐regular graphs. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010