{
  "id": "1203.0132",
  "version": "v1",
  "published": "2012-03-01T10:18:47.000Z",
  "updated": "2012-03-01T10:18:47.000Z",
  "title": "Largest sparse subgraphs of random graphs",
  "authors": [
    "Nikolaos Fountoulakis",
    "Ross J. Kang",
    "Colin McDiarmid"
  ],
  "comment": "15 pages",
  "journal": "Eur. J. Comb. 35 (2014), 232-244",
  "doi": "10.1016/j.ejc.2013.06.012",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "For the Erd\\H{o}s-R\\'enyi random graph G(n,p), we give a precise asymptotic formula for the size of a largest vertex subset in G(n,p) that induces a subgraph with average degree at most t, provided that p = p(n) is not too small and t = t(n) is not too large. In the case of fixed t and p, we find that this value is asymptotically almost surely concentrated on at most two explicitly given points. This generalises a result on the independence number of random graphs. For both the upper and lower bounds, we rely on large deviations inequalities for the binomial distribution.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-03-01T10:18:47.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "05A16"
    ],
    "keywords": [
      "random graph",
      "largest sparse subgraphs",
      "largest vertex subset",
      "large deviations inequalities",
      "precise asymptotic formula"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1203.0132F"
    }
  }
}