{
  "id": "2208.09876",
  "version": "v1",
  "published": "2022-08-21T12:48:39.000Z",
  "updated": "2022-08-21T12:48:39.000Z",
  "title": "Shotgun threshold for sparse Erdős-Rényi graphs",
  "authors": [
    "Jian Ding",
    "Jiangyi Yang",
    "Heng Ma"
  ],
  "comment": "38pages, 5 figures",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "In the shotgun assembly problem for a graph, we are given the empirical profile for rooted neighborhoods of depth $r$ (up to isomorphism) for some $r\\geq 1$ and we wish to recover the underlying graph up to isomorphism. When the underlying graph is an Erd\\H{o}s-R\\'enyi $\\mathcal G(n, \\frac{\\lambda}{n})$, we show that the shotgun assembly threshold $r_* \\approx \\frac{ \\log n}{\\log (\\lambda^2 \\gamma_\\lambda)^{-1}}$ where $\\gamma_\\lambda$ is the probability for two independent Poisson-Galton-Watson trees with parameter $\\lambda$ to be rooted isomorphic with each other. Our result sharpens a constant factor in a previous work by Mossel and Ross (2019) and thus solves a question therein.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-08-21T12:48:39.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "05C80"
    ],
    "keywords": [
      "sparse erdős-rényi graphs",
      "shotgun threshold",
      "independent poisson-galton-watson trees",
      "isomorphism",
      "shotgun assembly threshold"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 38,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}