Shotgun assembly of random graphs
Tom Johnston, Gal Kronenberg, Alexander Roberts, Alex Scott · Probability Theory and Related Fields · 2025
Abstract In the graph shotgun assembly problem, we are given the balls of radius r around each vertex of a graph and asked to reconstruct the graph. We study the shotgun assembly of the Erdős-Rényi random graph $${\mathcal {G}}(n,p)$$ G ( n , p ) for a wide range of values of r. We determine the threshold for reconstructibility for each $$r\ge 3$$ r ≥ 3 , extending and improving substantially on results of Mossel and Ross for $$r=3$$ r = 3 . For $$r=2$$ r = 2 , we give upper and lower bounds that improve on results of Gaudio and Mossel by polynomial factors. We also give a sharpening of a result of Huang and Tikhomirov for $$r=1$$ r = 1 .