{
  "id": "1111.6687",
  "version": "v2",
  "published": "2011-11-29T04:25:14.000Z",
  "updated": "2012-11-09T15:32:58.000Z",
  "title": "Upper Tails for Cliques",
  "authors": [
    "Bobby DeMarco",
    "Jeff Kahn"
  ],
  "comment": "25 pages",
  "doi": "10.1002/rsa.20440",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "With $\\xi_{k}=\\xi_{k}^{n,p}$ the number of copies of $K_k$ in the usual (Erd\\H{o}s-R\\'enyi) random graph $G(n,p)$, $p\\geq n^{-2/(k-1)}$ and $\\eta>0$, we show when $k>1$ $$\\Pr(\\xi_k> (1+\\eta)\\E \\xi_k) < \\exp [-\\gO_{\\eta,k} \\min\\{n^2p^{k-1}\\log(1/p), n^kp^{\\binom{k}{2}}\\}].$$ This is tight up to the value of the constant in the exponent.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-11-09T15:32:58.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60F10",
      "05C80"
    ],
    "keywords": [
      "upper tails",
      "random graph"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 25,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1111.6687D"
    }
  }
}