Percolation on dense graph sequences

DOI10.1214/09-AOP478MaRDI QIDQ2268697zbMATH OpenFDO

Authors Béla Bollobás, Christian Borgs, Jennifer T. Chayes, Oliver Riordan

Publication date 8 March 2010

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

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

zbMATH Keywords

random graphsPercolationcut metric

Mathematics Subject Classification ID

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

Abstract: In this paper we determine the percolation threshold for an arbitrary sequence of dense graphs $(G_n)$. Let $lambd{a}_n$ be the largest eigenvalue of the adjacency matrix of $G_n$, and let $G_n(p_n)$ be the random subgraph of $G_n$ obtained by keeping each edge independently with probability $p_n$. We show that the appearance of a giant component in $G_n(p_n)$ has a sharp threshold at $p_n=1/lambd{a}_n$. In fact, we prove much more: if $(G_n)$ converges to an irreducible limit, then the density of the largest component of $G_n(c/n)$ tends to the survival probability of a multi-type branching process defined in terms of this limit. Here the notions of convergence and limit are those of Borgs, Chayes, Lov'asz, S'os and Vesztergombi. In addition to using basic properties of convergence, we make heavy use of the methods of Bollob'as, Janson and Riordan, who used multi-type branching processes to study the emergence of a giant component in a very broad family of sparse inhomogeneous random graphs.

Recommendations

• Percolation in general graphs
• Percolation on sparse random graphs with given degree sequence
• Percolation on sequences of graphs
• The sharp threshold for percolation on expander graphs
• Percolation on random graphs with a fixed degree sequence

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• Component behavior near the critical point of the random graph process
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Counting graph homomorphisms
• Inequalities with applications to percolation and reliability
• Largest random component of a k-cube
• Limits of dense graph sequences
• Percolation on finite graphs and isoperimetric inequalities.
• Proof of the Van den Berg–Kesten Conjecture
• Random subgraphs of finite graphs. II: The lace expansion and the triangle condition
• Random subgraphs of finite graphs. III: The phase transition for the \(n\)-cube
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• Recurrence of distributional limits of finite planar graphs
• The Evolution of Random Graphs
• The Evolution of Random Subgraphs of the Cube
• The birth of the infinite cluster: Finite-size scaling in percolation
• The emergence of a giant component in random subgraphs of pseudo-random graphs
• The phase transition in inhomogeneous random graphs

Cited in

(33)

• Edge sampling using local network information
• The local limit of the uniform spanning tree on dense graphs
• Berry-Esseen bounds for generalized \(U\)-statistics
• Supercritical percolation on finite transitive graphs I: uniqueness of the giant component
• Large deviation analysis for layered percolation problems on the complete graph
• Existence of a Percolation Threshold on Finite Transitive Graphs
• scientific article; zbMATH DE number 7306863 (Why is no real title available?)
• Spectral bounds in random graphs applied to spreading phenomena and percolation
• On the first and second largest components in the percolated random geometric graph
• The cut metric, random graphs, and branching processes
• Adaptive estimation of nonparametric geometric graphs
• Percolation on dense random graphs with given degrees
• Graphon mean field systems
• Sparse random graphs with clustering
• Connectivity of Poissonian inhomogeneous random multigraphs
• Continuity of the percolation threshold in randomly grown graphs.
• Homology-changing percolation transitions on finite graphs
• Percolation on sequences of graphs
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Connectivity of inhomogeneous random graphs
• The GHP scaling limit of uniform spanning trees of dense graphs
• Pandemic spread in communities via random graphs
• The Giant Component in a Random Subgraph of a Given Graph
• Percolation on sparse random graphs with given degree sequence
• Clique percolation
• The giant component after percolation of product graphs
• Percolation in general graphs
• Algebraic bounds for heterogeneous site percolation on directed and undirected graphs
• Percolation on Sparse Random Graphs with Given Degree Sequence
• The disk-percolation model on graphs
• Compatible Sequences and a Slow Winkler Percolation
• Optimization on the smallest eigenvalue of grounded Laplacian matrix via edge addition
• Triangle percolation in mean field random graphs-with PDE

This page was built for publication: Percolation on dense graph sequences

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