{
  "id": "math/0612827",
  "version": "v2",
  "published": "2006-12-28T14:00:22.000Z",
  "updated": "2008-06-27T09:04:21.000Z",
  "title": "Asymptotic normality of the $k$-core in random graphs",
  "authors": [
    "Svante Janson",
    "Malwina J. Luczak"
  ],
  "comment": "Published in at http://dx.doi.org/10.1214/07-AAP478 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)",
  "journal": "Annals of Applied Probability 2008, Vol. 18, No. 3, 1085-1137",
  "doi": "10.1214/07-AAP478",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "We study the $k$-core of a random (multi)graph on $n$ vertices with a given degree sequence. In our previous paper [Random Structures Algorithms 30 (2007) 50--62] we used properties of empirical distributions of independent random variables to give a simple proof of the fact that the size of the giant $k$-core obeys a law of large numbers as ${{n\\to \\infty}}$. Here we develop the method further and show that the fluctuations around the deterministic limit converge to a Gaussian law above and near the threshold, and to a non-normal law at the threshold. Further, we determine precisely the location of the phase transition window for the emergence of a giant $k$-core. Hence, we deduce corresponding results for the $k$-core in $G(n,p)$ and $G(n,m)$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2008-06-27T09:04:21.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80"
    ],
    "keywords": [
      "asymptotic normality",
      "random graphs",
      "random structures algorithms",
      "deterministic limit converge",
      "independent random variables"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2006math.....12827J"
    }
  }
}