Marek Biskup, Lincoln Chayes and S. Alex Smith
Large-deviations/thermodynamic approach to percolation on the complete graph
(29K, ZIP)
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. One consequence is an immediate derivation of the "cavity" formula for the fraction of sites in the giant component. As a by-product of our analysis we compute also the large-deviation rate functions for the probabilities of the event that the random graph is connected, the event that it contains no loops and the event that it contains only "small" components.