2021/12/09 by Umberto De Ambroggio, De Ambroggio, Umberto, Matthew I. Roberts +1
Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2112.05002
openalex publication_date 2021/12/09 · openalex created_date 2021/12/31 · openalex updated_date 2026/07/28
Let d≥ 3 be a fixed integer, p∈ (0,1), and let n≥ 1 be a positive integer such that dn is even. Let \mathbbG(n, d, p) be a (random) graph on n vertices obtained by drawing uniformly at random a d-regular (simple) graph on [n] and then performing independent p-bond percolation on it, i.e. we independently retain each edge with probability p and delete it with probability 1-p. Let |Cmax| be the size of the largest component in \mathbbG(n, d, p). We show that, when p is of the form p=(d-1)-1(1+λn-1/3) for λ∈ ℝ, and A is large, ℙ(|Cmax|gt;An2/3)\asymp A-3/2e-(A3(d-1)(d-2))/(8d2)+(λA2(d-2)2)/(2d(d-1))-(λ2 A(d-1))/(2(d-2)). This improves on a result of Nachmias and Peres. We also give an analogous asymptotic for the probability that a particular vertex is in a component of size larger than An2/3.