Shotgun assembly of unlabeled Erdos-Renyi graphs

Abstract

Given a positive integer $n$, an unlabeled graph $G$ on $n$ vertices, and a vertex $v$ of $G$, let $N_G(v)$ be the subgraph of $G$ induced by vertices of $G$ of distance at most one from $v$. We show that there are universal constants $C,c>0$ with the following property. Let the sequence $(p_n{)}_{n=1}^{\infty }$ satisfy $n^{-1/2}{\log }^{C}n\le p_n\le c$. For each $n$, let ${\Gamma }_n$ be an unlabeled $G(n,p_n)$ Erdös-Rényi graph. Then with probability $1-o_n(1)$, any unlabeled graph ${\tilde{\Gamma }}_n$ on $n$ vertices with $\{N_{{\tilde{\Gamma }}_n}(v){\}}_v=\{N_{{\Gamma }_n}(v){\}}_v$ must coincide with ${\Gamma }_n$. This establishes $\tilde{\Theta }(n^{-1/2})$ as the transition range for the density parameter $p_n$ between reconstructability and non-reconstructability of Erdös-Rényi graphs from their $1$-neighborhoods, and resolves a problem of Gaudio and Mossel.

a revision