2020/10/27 by Gaudio, Julia, Mossel, Elchanan
#FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2010.14661
Graph shotgun assembly refers to the problem of reconstructing a graph from a collection of local neighborhoods. In this paper, we consider shotgun assembly of \ER random graphs G(n, pn), where pn = n-α for 0 < α< 1. We consider both reconstruction up to isomorphism as well as exact reconstruction (recovering the vertex labels as well as the structure). We show that given the collection of distance-1 neighborhoods, G is exactly reconstructable for 0 < α< (1)/(3), but not reconstructable for (1)/(2) < α< 1. Given the collection of distance-2 neighborhoods, G is exactly reconstructable for α∈ (0, (1)/(2)) ∪ ((1)/(2), (3)/(5)), but not reconstructable for (3)/(4) < α< 1.