Speaker: Han Huang (Georgia Tech)

Title: When can we recover an Erdos-Renyi graph from its 1-neighbors?

Abstract:

Suppose we have a graph G. For each vertex v of G, we observed the local structure of the G at this vertex v. Precisely, we have the induced subgraph containing all vertices at a distance at most 1 to v (including v), but the labels of the neighbors of v have been removed. Now, can we reconstruct graph G based on these 1-neighbor structures at each vertex? This question was proposed by Mossel and Ross, which was motivated by DNA shotgun assembly.

To reconstruct the graph, the local structures need to have sufficient complexity. Previously, Gaudio and Mossel show that for the Erdos Renyi graph G(n,p), one cannot reconstruct the graph from its local structures when p = o(n^{-1/2}). For such values of p, unique reconstruction is not possible because the number of typical realizations of Erdos Renyi Graphs is much more than the number of typical realizations of the overall local structures. Recently, with Tikhomirov, we managed to confirm that the transition for the unique reconstruction of G(n,p) graphs happens at the level when p is at n^{-1/2} up to a polylog n factor.