Shotgun Assembly of Linial-Meshulam Model

Abstract

In a recent paper [6], J. Gaudio and E. Mossel studied the shotgun assembly of the Erdős-Rényi graph $\mathcal{G}(n,p_n)$ with $p_n=n^{-\alpha }$, and showed that the graph is reconstructable form its $1$-neighbourhoods if $0<\alpha <1/3$ and not reconstructable from its $1$-neighbourhoods if $1/2<\alpha <1$. In this article, we generalise the notion of reconstruction of graphs to the reconstruction of simplicial complexes. We show that the Linial-Meshulam model $Y_d(n,p_n)$ on $n$ vertices with $p_n=n^{-\alpha }$ is reconstructable from its $1$-neighbourhoods when $0<\alpha <1/3$ and is not reconstructable form its $1$-neighbourhoods when $1/2<\alpha <1$.

14 pages, 2 figures