{
  "id": "2501.02433",
  "version": "v1",
  "published": "2025-01-05T03:56:41.000Z",
  "updated": "2025-01-05T03:56:41.000Z",
  "title": "On the jump of the cover time in random geometric graphs",
  "authors": [
    "Carlos Martinez",
    "Dieter Mitsche"
  ],
  "comment": "28 pages",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "In this paper we study the cover time of the simple random walk of the giant component of supercritical $d$-dimensional random geometric graphs on $n$ vertices. We show that the cover time undergoes a jump at the connectivity threshold radius $r_c$: with $r_g$ denoting the threshold for having a giant component, we show that if the radius $r$ satisfies $r_c < r \\le (1-\\varepsilon)r_g$ for any $\\varepsilon > 0$, the cover time of the giant component is asymptotically almost surely $\\Theta(n \\log^2 n$). On the other hand, we show that for $r \\ge (1+\\varepsilon)r_c$, the cover time of the graph is asymptotically almost surely $\\Theta(n \\log n)$ (which was known for $d=2$ only for a radius larger by a constant factor).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2025-01-05T03:56:41.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "60D05",
      "05C81"
    ],
    "keywords": [
      "giant component",
      "dimensional random geometric graphs",
      "connectivity threshold radius",
      "cover time undergoes",
      "simple random walk"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 28,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}