{
  "id": "1401.7577",
  "version": "v2",
  "published": "2014-01-29T16:28:15.000Z",
  "updated": "2015-09-10T17:28:47.000Z",
  "title": "Localization in random geometric graphs with too many edges",
  "authors": [
    "Sourav Chatterjee",
    "Matan Harel"
  ],
  "comment": "50 pages, 1 figure",
  "categories": [
    "math.PR"
  ],
  "abstract": "Consider a random geometric graph $G(\\chi_n, r_n)$, given by connecting two vertices of a Poisson point process $\\chi_n$ of intensity $n$ on the unit torus whenever their distance is smaller than the parameter $r_n$. The model is conditioned on the rare event that the number of edges observed, $|E|$, is greater than $(1 + \\delta)\\mathbb{E}(|E|)$, for some fixed $\\delta >0$. This article proves that upon conditioning, with high probability there exists a ball of diameter $r_n$ which contains a clique of at least $\\sqrt{2 \\delta \\mathbb{E}(|E|)}(1 - \\epsilon)$ vertices, for any $\\epsilon >0$. Intuitively, this region contains all the \"excess\" edges the graph is forced to contain by the conditioning event, up to lower order corrections. As a consequence of this result, we prove a large deviations principle for the upper tail of the edge count of the random geometric graph.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-01-29T16:28:15.000Z",
      "comment": "45 pages, 1 figure",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2015-09-10T17:28:47.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60F10",
      "05C80",
      "60D05"
    ],
    "keywords": [
      "random geometric graph",
      "localization",
      "large deviations principle",
      "lower order corrections",
      "poisson point process"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 50,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1401.7577C"
    }
  }
}