Shotgun assembly of Erdős-Rényi random graphs
Graph shotgun assembly refers to the problem of reconstructing a graph from a collection of local neighborhoods. In this paper, we consider shotgun assembly of \ER random graphs $G(n, p_n)$, where $p_n = n^{-\alpha}$ for $0 < \alpha < 1$. We consider both reconstruction up to isomorphism as...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Mathematical Statistics
2022
|
| Online Access: | https://hdl.handle.net/1721.1/145812 |
| _version_ | 1826192373864988672 |
|---|---|
| author | Gaudio, Julia Mossel, Elchanan |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Gaudio, Julia Mossel, Elchanan |
| author_sort | Gaudio, Julia |
| collection | MIT |
| description | Graph shotgun assembly refers to the problem of reconstructing a graph from a
collection of local neighborhoods. In this paper, we consider shotgun assembly
of \ER 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 $\alpha \in \left(0, \frac{1}{2}\right) \cup
\left(\frac{1}{2}, \frac{3}{5}\right)$, but not reconstructable for
$\frac{3}{4} < \alpha < 1$. |
| first_indexed | 2024-09-23T09:11:03Z |
| format | Article |
| id | mit-1721.1/145812 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T09:11:03Z |
| publishDate | 2022 |
| publisher | Institute of Mathematical Statistics |
| record_format | dspace |
| spelling | mit-1721.1/1458122022-10-13T03:40:59Z Shotgun assembly of Erdős-Rényi random graphs Gaudio, Julia Mossel, Elchanan Massachusetts Institute of Technology. Department of Mathematics Graph shotgun assembly refers to the problem of reconstructing a graph from a collection of local neighborhoods. In this paper, we consider shotgun assembly of \ER 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 $\alpha \in \left(0, \frac{1}{2}\right) \cup \left(\frac{1}{2}, \frac{3}{5}\right)$, but not reconstructable for $\frac{3}{4} < \alpha < 1$. 2022-10-12T18:49:24Z 2022-10-12T18:49:24Z 2022 2022-10-12T18:42:08Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/145812 Gaudio, Julia and Mossel, Elchanan. 2022. "Shotgun assembly of Erdős-Rényi random graphs." Electronic Communications in Probability, 27 (none). en 10.1214/22-ECP445 Electronic Communications in Probability Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf Institute of Mathematical Statistics Electronic Communications in Probability |
| spellingShingle | Gaudio, Julia Mossel, Elchanan Shotgun assembly of Erdős-Rényi random graphs |
| title | Shotgun assembly of Erdős-Rényi random graphs |
| title_full | Shotgun assembly of Erdős-Rényi random graphs |
| title_fullStr | Shotgun assembly of Erdős-Rényi random graphs |
| title_full_unstemmed | Shotgun assembly of Erdős-Rényi random graphs |
| title_short | Shotgun assembly of Erdős-Rényi random graphs |
| title_sort | shotgun assembly of erdos renyi random graphs |
| url | https://hdl.handle.net/1721.1/145812 |
| work_keys_str_mv | AT gaudiojulia shotgunassemblyoferdosrenyirandomgraphs AT mosselelchanan shotgunassemblyoferdosrenyirandomgraphs |