Skip to Content

Sponsors

No results

Tags

No results

Types

No results

Search Results

Events

No results
Search events using: keywords, sponsors, locations or event type
When / Where
All occurrences of this event have passed.
This listing is displayed for historical purposes.

Presented By: Department of Mathematics

Colloquium Series Seminar

Sumner Myers Award Lecture

When can we recover an Erdos-Renyi graph from its local structure?

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 local 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. Speaker(s): Han Huang (Georgia Tech)

Explore Similar Events

  •  Loading Similar Events...

Back to Main Content