2022/11/25 by Johnston, Tom, Kronenberg, Gal, Roberts, Alexander +1
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2211.14218
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) for a wide range of values of r. We determine the threshold for reconstructibility for each r≥ 3, extending and improving substantially on results of Mossel and Ross for r=3. For 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.