{
  "id": "1402.3696",
  "version": "v1",
  "published": "2014-02-15T14:27:12.000Z",
  "updated": "2014-02-15T14:27:12.000Z",
  "title": "Connectivity of sparse Bluetooth networks",
  "authors": [
    "Nicolas Broutin",
    "Luc Devroye",
    "Gábor Lugosi"
  ],
  "categories": [
    "math.PR",
    "cs.DM",
    "cs.NI",
    "math.CO"
  ],
  "abstract": "Consider a random geometric graph defined on $n$ vertices uniformly distributed in the $d$-dimensional unit torus. Two vertices are connected if their distance is less than a \"visibility radius\" $r_n$. We consider {\\sl Bluetooth networks} that are locally sparsified random geometric graphs. Each vertex selects $c$ of its neighbors in the random geometric graph at random and connects only to the selected points. We show that if the visibility radius is at least of the order of $n^{-(1-\\delta)/d}$ for some $\\delta > 0$, then a constant value of $c$ is sufficient for the graph to be connected, with high probability. It suffices to take $c \\ge \\sqrt{(1+\\epsilon)/\\delta} + K$ for any positive $\\epsilon$ where $K$ is a constant depending on $d$ only. On the other hand, with $c\\le \\sqrt{(1-\\epsilon)/\\delta}$, the graph is disconnected, with high probability.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-02-15T14:27:12.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "60C05"
    ],
    "keywords": [
      "sparse bluetooth networks",
      "visibility radius",
      "high probability",
      "connectivity",
      "locally sparsified random geometric graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1402.3696B"
    }
  }
}