Critical Percolation on Random Regular Graphs
The behavior of the random graph G(n,p) around the Critical probability p(c) = 1/n is well understood. When p = (1 + O(n(1/3)))p(c), componentrs 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 - epsilon(n))p(c) with epsilon(n)n(1/3) -> infinity (the subcritical regime) the largest component is concentrated around 2 epsilon(-2) log (epsilon(2)n). When p = (1 + epsilon(n))p(c) with epsilon(n)n(1/3) -> infinity (the supercritical regime), the largest component is concentrated around 2 epsilon 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 behaviour (with suitable d dependent factors in the non-critical regimes) extends to random d-regular graphs. (C) 2009 Wiley Periodicals, Inc. Random Struct. Alg., 36 111-148, 2010
percolation random regular graph