The critical probability for percolation on finite graphs

Abstract

We determine the critical probability for Bernoulli bond percolation on essentially any finite graph. Namely, letting $λ(G)$ denote the spectral radius (maximum eigenvalue) of $G$, we prove that the critical probability is at $1/λ(G)$: above this probability there is typically a component of order $Ω(λ(G))$, whereas below it all components are of order at most $O(\sqrt{|G|})$. These results in particular confirm a conjecture of Krivelevich and Samotij about percolation on graphs of a given average degree, and vastly extend theorems of Bollobás, Borgs, Chayes, and Riordan, who proved analogous results but only for dense graphs. Our theorems are optimal in many regimes, and also demonstrate that percolation has an unexpectedly subtle behaviour on graphs whose spectral radius is roughly the square root of their maximum degree.

Disclosure

“for very helpful discussions in the early phases of this project. Statement of AI use: ChatGPT 5.5 suggested the proof of Lemma 2.4, but all of the other ideas in the paper, as well as all of the writing, are due entirely to the authors. ChatGPT 5.6 was used to proofread this paper. 6 This is because there will be Ω(log s) vertices on the smaller side lying in the same component of Gp , each having roughly s neighbours in the larger side. 7 On the other hand, fo”

PDF page 20

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-22T18:18:16.578602Z

Structural counts