Percolation on dense graph sequences

DOI10.1214/09-AOP478zbMATH Open1190.60090arXivmath/0701346MaRDI QIDQ2268697FDOQ2268697

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

Publication date: 8 March 2010

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

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.

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

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

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)

Cites Work

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

Cited In (24)

• Graphon mean field systems
• Sparse random graphs with clustering
• Spectral bounds in random graphs applied to spreading phenomena and percolation
• Connectivity of Poissonian inhomogeneous random multigraphs
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Pandemic spread in communities via random graphs
• Adaptive estimation of nonparametric geometric graphs
• The local limit of the uniform spanning tree on dense graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimization on the smallest eigenvalue of grounded Laplacian matrix via edge addition
• Supercritical percolation on finite transitive graphs I: uniqueness of the giant component
• Connectivity of inhomogeneous random graphs
• The disk-percolation model on graphs
• Algebraic bounds for heterogeneous site percolation on directed and undirected graphs
• The GHP scaling limit of uniform spanning trees of dense graphs
• The Giant Component in a Random Subgraph of a Given Graph
• The giant component after percolation of product graphs
• The cut metric, random graphs, and branching processes
• Homology-changing percolation transitions on finite graphs
• On the first and second largest components in the percolated random geometric graph
• Berry-Esseen bounds for generalized \(U\)-statistics
• Compatible Sequences and a Slow Winkler Percolation
• Percolation on Sparse Random Graphs with Given Degree Sequence

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)