MathDB

Krivelevich–Samotij percolation conjecture

Let GG be a finite graph, let λ(G)\lambda(G) denote the spectral radius of its adjacency matrix, and let GpG_p be obtained from GG by retaining each edge independently with probability pp. The conjecture asserts that the critical probability for the emergence of large connected components is pc(G)=1/λ(G)p_c(G)=1/\lambda(G): above p=1/λ(G)p=1/\lambda(G), GpG_p typically contains a connected component of order Ω(λ(G))\Omega(\lambda(G)), whereas below p=1/λ(G)p=1/\lambda(G) every connected component has order at most O(∣V(G)∣)O(\sqrt{|V(G)|}).

Progress summary

Open

The full conjecture remains open, but a weaker version under graph-expansion assumptions has been proved.

Krivelevich and Samotij conjectured that the percolation threshold for a large component in a finite graph is pc(G)=1/λ(G)p_c(G)=1/\lambda(G), with corresponding supercritical and subcritical component bounds. The retrieved sources do not report a proof or counterexample for this full spectral-radius formulation.

Known results

A 2024 preprint proves that if every set of at most kk vertices has edge boundary at least d∣S∣d|S|, then percolation with p=(1+ε)/dp=(1+\varepsilon)/d contains, with probability tending to 11, a component of order at least k/2k/2; this is a weaker expansion-based statement, not the full conjecture.

Current status (as of August 2026): the full Krivelevich–Samotij conjecture remains unsettled; only related expansion-based partial results were found.

Sources & referencesView supporting material

Primary source

arXiv

Additional references

percolationprobabilityrandom-graphs

Solutions 0

No solutions have been posted yet.