Abstract

We consider the problem of reconstructing graphs or labelled graphs from neighborhoods of given radius r. The question of inferring a graph is a generalization of the DNA shotgun problem where the graph is an interval and the nodes are labelled by A, C, G, T. The graph shotgun problem is motivated in part by applications in neuroscience. We provide some necessary and some sufficient conditions for correct recovery both in combinatorial terms and for some generative models including Ising model on lattices and Erdos-Renyi random graphs. Joint work with Elchanan Mossel.