Answers are grounded in this paper and cite their sources.
The behavior of the random graph G(n,p) around the critical probability pc = 1 n is well understood. When p = (1 + O(n1/3))pc the components are roughly of size n2/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))pc with ϵ(n)n1/3 →∞ (the subcritical regime) the largest component is concentrated around 2ϵ−2 log(ϵ3n). When p = (1 + ϵ(n))pc with ϵ(n)n1/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.
No takes yet. Share an insight, caveat, or question.
Nachmias et al. (2009) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: