Sharp threshold for percolation on expanders

DOI10.1214/10-AOP610zbMATH Open1239.60090arXiv0906.3657OpenAlexW3098041426WikidataQ58374456 ScholiaQ58374456MaRDI QIDQ662426FDOQ662426

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)

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.

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

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

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)

Cites Work

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

Cited In (12)

• The sharp threshold for percolation on expander graphs
• Expansion in supercritical random subgraphs of the hypercube and its consequences
• Hypercontractivity for global functions and sharp thresholds
• Asymptotics in percolation on high-girth expanders
• 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)