Premium
Large‐deviations/thermodynamic approach to percolation on the complete graph
Author(s) -
Biskup Marek,
Chayes Lincoln,
Smith S. A.
Publication year - 2007
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20169
Subject(s) - giant component , mathematics , large deviations theory , graph , rate function , random graph , statistical physics , percolation (cognitive psychology) , combinatorics , event (particle physics) , discrete mathematics , statistics , physics , quantum mechanics , neuroscience , biology
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 byproduct 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. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007