The probability of unusually large components for critical percolation on random d-regular graphs

Umberto De Ambroggio, Matthew Roberts

Research output: Contribution to journalArticlepeer-review

Abstract

Let d≥3 be a fixed integer, p∈(0,1), and let n≥1 be a positive integer such that dn is even. Let G(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 G(n,d,p). We show that, when p is of the form p=(d−1)^{−1}(1+λn^{−1∕3}) for λ∈R, and A is large,

P(|Cmax|>An^{2∕3})≍A^{−3∕2}e^{−A^3(d−1)(d−2)/8d^2+λA^2(d−1)/2d−λ^2A(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 An^{2∕3}.
Original languageEnglish
Pages (from-to)1-55
Number of pages55
JournalElectronic Journal of Probability
Volume28
Early online date11 Jul 2023
DOIs
Publication statusE-pub ahead of print - 11 Jul 2023

Bibliographical note

Funding Statement
Both authors would like to thank the Royal Society for their generous funding, of a PhD scholarship for UDA and a University Research Fellowship for MR.

Keywords

  • Component size
  • Exploration process
  • Percolation
  • Random regular graph

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'The probability of unusually large components for critical percolation on random d-regular graphs'. Together they form a unique fingerprint.

Cite this