Title: Erdo ̋s–Renyi shotgun reconstruction

Abstract: We say that a graph G is reconstructible from its r-neighbourhoods if all graphs H having the same collection of r-balls as G up to isomorphism, are isomorphic to G. We are interested in the reconstruction of the Erdo ̋s–Renyi graph G(n,p) for a wide range of values of r, aiming to determine the values of p for which G(n, p) is r-reconstructible with high probability. Mossel and Ross showed that the the graph G(n, p) can be reconstructed from its 3-neighbourhoods with high probability provided that p ≫ log^2(n)/n. Later, Gaudio and Mossel studied reconstruction from the 1- and 2-neighbourhoods, giving bounds on the values of p for which G(n, p) is reconsructible. For 1-neighbourhoods, this was improved very recently by Huang and Tikhomirov who determined the correct threshold up to logarithmic factors, around n^{−1/2}. In this talk we will show new bounds on p for the r-reconstructibility problem in G(n, p). We improve the bounds for 2-neighbourhoods given by Gaudio and Mossel by polynomial factors. We also improve the result of Huang and Tikhomirov for 1-neighbourhoods, showing that the logarithmic factor is necessary. Finally, we determine the exact thresholds for r-reconstructibility for r ≥ 3. 
This is a joint work with Tom Johnston, Alexander Roberts, and Alex Scott.