Sharp threshold for percolation on expanders

DOI10.1214/10-AOP610MaRDI QIDQ662426zbMATH OpenOpenAlexWikidataFDO

Authors Itai Benjamini, Stéphane Boucheron, Gábor Lugosi, Raphaël Rossignol

Publication date 22 February 2012

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0906.3657

zbMATH Keywords

random graphpercolationsharp thresholdgiant componentexpander

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: We study the appearance of the giant component in random subgraphs of a given large finite graph G=(V,E) in which each edge is present independently with probability p. We show that if G is an expander with vertices of bounded degree, then for any c in ]0,1[, the property that the random subgraph contains a giant component of size c|V| has a sharp threshold.

Recommendations

• The sharp threshold for percolation on expander graphs
• Percolation on finite graphs and isoperimetric inequalities.
• Edge percolation on a random regular graph of low degree
• Percolation in general graphs
• On the Expansion of the Giant Component in Percolated (n, d,λ) Graphs

Cites work

• Analytic combinatorics
• Critical percolation on random regular graphs
• Edge percolation on a random regular graph of low degree
• Edge-Isoperimetric Inequalities and Influences
• Every monotone graph property has a sharp threshold
• Is the critical percolation probability local?
• Large deviations for sums of partly dependent random variables
• Percolation beyond \(\mathbb{Z}^ d\), many questions and a few answers
• Percolation on finite graphs and isoperimetric inequalities.
• Probability on trees and networks
• Submean variance bound for effective resistance of random electric networks
• The jackknife estimate of variance
• Threshold for monotone symmetric properties through a logarithmic Sobolev inequality

Cited in

(12)

• The sharp threshold for percolation on expander graphs
• Expansion in supercritical random subgraphs of the hypercube and its consequences
• Asymptotics in percolation on high-girth expanders
• Hypercontractivity for global functions and sharp thresholds
• Percolation on finite graphs and isoperimetric inequalities.
• Vertex percolation on expander graphs
• Expansion in supercritical random subgraphs of expanders and its consequences
• Algebraic bounds for heterogeneous site percolation on directed and undirected graphs
• The giant component after percolation of product graphs
• A note on the local weak limit of a sequence of expander graphs
• Critical parameters for loop and Bernoulli percolation
• Locality of random digraphs on expanders

This page was built for publication: Sharp threshold for percolation on expanders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q662426)