{
  "id": "1312.7170",
  "version": "v1",
  "published": "2013-12-27T01:48:50.000Z",
  "updated": "2013-12-27T01:48:50.000Z",
  "title": "The acquaintance time of (percolated) random geometric graphs",
  "authors": [
    "Tobias Muller",
    "Pawel Pralat"
  ],
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "In this paper, we study the acquaintance time $\\AC(G)$ defined for a connected graph $G$. We focus on $\\G(n,r,p)$, a random subgraph of a random geometric graph in which $n$ vertices are chosen uniformly at random and independently from $[0,1]^2$, and two vertices are adjacent with probability $p$ if the Euclidean distance between them is at most $r$. We present asymptotic results for the acquaintance time of $\\G(n,r,p)$ for a wide range of $p=p(n)$ and $r=r(n)$. In particular, we show that with high probability $\\AC(G) = \\Theta(r^{-2})$ for $G \\in \\G(n,r,1)$, the \"ordinary\" random geometric graph, provided that $\\pi n r^2 - \\ln n \\to \\infty$ (that is, above the connectivity threshold). For the percolated random geometric graph $G \\in \\G(n,r,p)$, we show that with high probability $\\AC(G) = \\Theta(r^{-2} p^{-1} \\ln n)$, provided that $p n r^2 \\geq n^{1/2+\\eps}$ and $p < 1-\\eps$ for some $\\eps>0$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-12-27T01:48:50.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "acquaintance time",
      "high probability",
      "percolated random geometric graph",
      "random subgraph",
      "connectivity threshold"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1312.7170M"
    }
  }
}