# Julia Gaudio: Shotgun Assembly of Erdos-Renyi Random Graphs

Time: Mon 2021-06-07 15.15 - 16.15

Location:

Lecturer: Julia Gaudio (MIT)

### Abstract

Graph shotgun assembly refers to the problem of reconstructing a graph from a collection of local neighborhoods. We consider shotgun assembly of Erdos-Renyi random graphs $$G(n, p_n)$$, where $$p_n = n^{-\alpha}$$ for $$0 < \alpha < 1$$. We consider both reconstruction up to isomorphism as well as exact reconstruction (recovering the vertex labels as well as the structure). We show that given the collection of distance-1 neighborhoods, $$G$$ is exactly reconstructable for $$0 < \alpha < \frac{1}{3}$$, but not reconstructable for $$\frac{1}{2} < \alpha < 1$$. Given the collection of distance-2 neighborhoods, $$G$$ is exactly reconstructable for $$0 < \alpha < \frac{3}{5}$$, but not reconstructable for $$\frac{3}{4} < \alpha < 1$$.

This is based on joint work with Elchanan Mossel.

Zoom notes: This meeting ID – 621 4469 8204 – will be the recurring meeting for the Statistics and Probability Seminar.

Page responsible:webmaster@math.kth.se
Belongs to: Department of Mathematics
Last changed: Jun 02, 2021