Second phase transition in r-neighbourhood shotgun assembly

Status partial high confidence

The source paper itself establishes the second phase transition for all r≥3, proving that if p=ω(t(n)) then G is reconstructible from its r-neighbourhoods and if p=o(t(n)) (and p=ω(n^{-(2r+1)/(2r)})) then G is not reconstructible. The conjecture remains open for r=1 and r=2, for which the paper provides improved but non-matching upper and lower bounds; an explicit open problem asks whether the threshold for r=2 is around n^{-3/4} up to polylogarithmic factors. No subsequent paper resolving either of these cases was found in the indexed literature.

Reviewer notes. The Springer published version (DOI 10.1007/s00440-025-01380-x, Probability Theory and Related Fields, 2025) corresponds to the same arXiv paper and does not appear to add new results for r=1 or r=2. The conjecture is partially resolved by the source paper itself for all r≥3; the remaining open cases are r=1 (where the lower bound is n^{-1/2} up to polylogarithmic factors, improving Huang–Tikhomirov) and r=2 (where bounds improve Gaudio–Mossel by polynomial factors but a polylogarithmic gap persists around the conjectured threshold n^{-3/4}). No follow-up paper resolving these cases was found after searching.

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