Graph-theory open problems

2-reconstructibility threshold in G(n,p)

Question · arXiv:2211.14218

arXiv Question high confidence— first stated 2025-06-23
Authors: Tom Johnston, Gal Kronenberg, Alexander Roberts, Alex Scott

Status open high confidence

The labelled question asks when $\mathcal{G}(n,p)$ is 2-reconstructible, and specifically whether there is a threshold around $n^{-3/4}$ up to a polylogarithmic factor. No follow-up resolving the $r=2$ threshold was found in the May 2026 review.

Reviewer notes. The exact labelled question is about 2-reconstructibility only. The earlier placeholder and review incorrectly broadened it to both r=1 and r=2.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Question. Determine when $\mathcal{G}(n,p)$ is 2-reconstructible. Is there a threshold around $n^{-3/4}$ (up to a polylogarithmic factor)?

Context

The paper determines the sharp threshold for $r$-reconstructibility for every $r\geq 3$. For $r=2$ it improves the bounds of Gaudio and Mossel by polynomial factors but does not pin down the exact threshold.

Source paper

Shotgun assembly of random graphs
Tom Johnston, Gal Kronenberg, Alexander Roberts, Alex Scott · 2025-06-23
https://arxiv.org/abs/2211.14218

Related conjectures

  • implied by Second phase transition in r-neighbourhood shotgun assembly partial (plausible) I recovered the truncated Question from the paper's PDF: 'Determine when G(n,p) is 2-reconstructible. Is there a threshold around n^{-3/4} (up to a polylogarithmic factor)?' — it concerns only r=2 (the sole Question environment in the paper; r=1 gets no Question), not r in {1,2} as the ingested record guessed. The source, instantiated at r=2, asserts existence of a sharp second threshold t(n) for 2-reconstructibility, which answers the qualitative existence part of the Question; but it says nothing about the threshold's location, so it neither 'determines when' nor confirms the specific guess n^{-3/4}. The restriction implication thus covers only part of the target's content, and the target as ingested was truncated, so I cap the verdict at plausible. Direction (general statement -> r=2 instance) is as claimed.

View in the relation graph — relations are AI-reviewed, not formally verified.