Large-deviations/thermodynamic approach to percolation on the complete graph

Abstract

We present a large-deviations/thermodynamic approach to the classic problem of percolation on the complete graph. Specifically, we determine the large-deviation rate function for the probability that the giant component occupies a fixed fraction of the graph while all other components are ``small.'' One consequence is an immediate derivation of the ``cavity'' formula for the fraction of vertices in the giant component. As a by-product of our analysis we compute the large-deviation rate functions for the probability of the event that the random graph is connected, the event that it contains no cycles and the event that it contains only ``small'' components.

16 pages, 1 figure; revised version accomodating literature remarks of the referees

References in corpus (5)

• Complete Analysis of Phase Transitions and Ensemble Equivalence for the Curie-Weiss-Potts Model
• On large deviation properties of Erdos-Renyi random graphs
• Mean-field driven first-order phase transitions in systems with long-range interactions
• Rigorous analysis of discontinuous phase transitions via mean-field bounds
• Critical region for droplet formation in the two-dimensional Ising model

Cited by in corpus (10)

• Large-deviation properties of largest component for random graphs
• Large deviations of empirical neighborhood distribution in sparse random graphs
• Large-deviation properties of the largest biconnected component for random graphs
• Large deviation theory of percolation on multiplex networks
• The cut metric, random graphs, and branching processes
• Limit Theorems and Coexistence Probabilities for the Curie-Weiss Potts Model with an external field
• Exploring hypergraphs with martingales
• Thermodynamic versus Topological Phase Transitions: Cusp in the Kertész Line
• Large deviations of connected components in the stochastic block model
• Large Deviation Properties of Minimum Spanning Trees for Random Graphs