2015/12/28 by Huang, Brice, Mossel, Elchanan, Sun, Nike +2 · 1 citation
#05C60 #05C80 #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.1512.08473
Mossel and Ross (2019) introduce the shotgun assembly problem for random graphs: what radius R ensures that the random graph G can be uniquely recovered from its list of rooted R-neighborhoods, with high probability? Here we consider this question for random regular graphs of fixed degree d≥3. A result of Bollobás (1982) implies efficient recovery at R = (1 + ε) \frac12 logd-1n with high probability -- moreover, this recovery algorithm uses only a summary of the distances in each neighborhood. We show that using the full neighborhood structure gives a sharper bound R = (log n + loglog n)/(2log(d-1)) + O(1) , which we prove is tight up to the O(1) term. One consequence of our proof is that if G,H are independent graphs where G follows the random regular law, then with high probability the graphs are non-isomorphic; furthermore, this can be efficiently certified by testing the R-neighborhood list of H against the R-neighborhood of a single adversarially chosen vertex of G.