Sharp threshold for r-reconstructibility in G(n,p)
Question · arXiv:2211.14218
Status open high confidence
The question concerns the exact threshold for $r$-reconstructibility of $\mathcal{G}(n,p)$ for $r \in \{1,2\}$, the two radii for which Johnston, Kronenberg, Roberts, and Scott provide only upper and lower bounds rather than a sharp threshold. For $r=2$, a gap remains around $n^{-3/4}$ (up to polylogarithmic factors); for $r=1$, a gap persists around $n^{-1/2}$. No follow-up paper resolving either case was found in the indexed literature.
Reviewer notes. No follow-up paper resolving the exact threshold for r=1 or r=2 was found. The paper (arXiv:2211.14218) was first posted in November 2022 and published in Probability Theory and Related Fields in June 2025; the sharp threshold for all r≥3 is fully resolved in the paper itself. For r=2, the open question is whether the threshold is near n^{-3/4} (up to polylogarithmic factors); for r=1, the gap is around n^{-1/2}. Searched arXiv and web through May 2026 without finding any resolution.
Context
The paper determines the sharp threshold for $r$-reconstructibility for every $r\geq 3$. For $r=2$ it improves bounds of Gaudio and Mossel by polynomial factors, and for $r=1$ it sharpens a result of Huang and Tikhomirov, but in neither case is the exact threshold pinned down.
Notes. The labelled [qu] environment confirms an explicit open question is posed; its verbatim statement was not provided in the supplied paper content, so the statement_text above is inferred from context.
Source paper
Shotgun assembly of random graphs
Tom Johnston, Gal Kronenberg, Alexander Roberts, Alex Scott · 2025-06-23
https://arxiv.org/abs/2211.14218