Shotgun Assembly of Random Geometric Graphs

Abstract

In a recent work, Huang and Tikhomirov considered the shotgun assembly for Erd\H os-Rényi graphs $\mathcal{G}(n,p_n)$ with $p_n=n^{-\alpha }$, and showed that the graph is reconstructable if $0<\alpha <\frac{1}{2}$ and not reconstructable if $\frac{1}{2}<\alpha <1$ from its $1$-neighbourhoods. In this article, we consider random geometric graphs $G(n,r)$, where $r^2=n^{-\alpha }$ and $0<\alpha <1$, on flat torus. Interestingly, unlike the results for the Erd\H os-Rényi random graphs, we show that the random geometric graph is always reconstructable from its 1-neighbourhoods.

The proof is not complete. The probability bound obtained in Lemma 4 is not enough to complete the proof the main theorem