{
  "id": "math/0506255",
  "version": "v3",
  "published": "2005-06-13T21:32:15.000Z",
  "updated": "2006-06-10T00:16:24.000Z",
  "title": "Large-deviations/thermodynamic approach to percolation on the complete graph",
  "authors": [
    "Marek Biskup",
    "Lincoln Chayes",
    "S. Alex Smith"
  ],
  "comment": "16 pages, 1 figure; revised version accomodating literature remarks of the referees",
  "journal": "Random Structures & Algorithms 31 (2007), no. 3, 354-370",
  "doi": "10.1002/rsa.20169",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2006-06-10T00:16:24.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "60F10",
      "05C80"
    ],
    "keywords": [
      "complete graph",
      "large-deviations/thermodynamic approach",
      "large-deviation rate function",
      "percolation",
      "giant component occupies"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005math......6255B"
    }
  }
}