{
  "id": "1508.07355",
  "version": "v1",
  "published": "2015-08-28T21:33:19.000Z",
  "updated": "2015-08-28T21:33:19.000Z",
  "title": "On the trace of random walks on random graphs",
  "authors": [
    "Alan Frieze",
    "Michael Krivelevich",
    "Peleg Michaeli",
    "Ron Peled"
  ],
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "We study graph-theoretic properties of the trace of a random walk on a random graph. We show that for any $\\varepsilon>0$ there exists $C>1$ such that the trace of the simple random walk of length $(1+\\varepsilon)n\\ln{n}$ on the random graph $G\\sim G(n,p)$ for $p>C\\ln{n}/n$ is, with high probability, Hamiltonian and $\\Theta(\\ln{n})$-connected. In the special case $p=1$ (i.e. when $G=K_n$), we show a hitting time result according to which, with high probability, exactly one step after the last vertex has been visited, the trace becomes Hamiltonian, and one step after the last vertex has been visited for the $k$'th time, the trace becomes $2k$-connected.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-08-28T21:33:19.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C81",
      "05C45",
      "05C80",
      "60G50"
    ],
    "keywords": [
      "random graph",
      "high probability",
      "study graph-theoretic properties",
      "simple random walk",
      "th time"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}