Large-Deviations/Thermodynamic approach to percolation on the complete graph
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. (C) 2007 Wiley Periodicals, Inc.
percolation erdos-renyi random graph large deviations random forests