Shotgun assembly of random graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916803789193216 |
|---|---|
| author | Johnston, Tom Kronenberg, Gal Roberts, Alexander Scott, Alex |
| author_facet | Johnston, Tom Kronenberg, Gal Roberts, Alexander Scott, Alex |
| contents | In the graph shotgun assembly problem, we are given the balls of radius $r$ around each vertex of a graph and asked to reconstruct the graph. We study the shotgun assembly of the Erdős-Rényi random graph $\mathcal G(n,p)$ for a wide range of values of $r$. We determine the threshold for reconstructibility for each $r\geq 3$, extending and improving substantially on results of Mossel and Ross for $r=3$. For $r=2$, we give upper and lower bounds that improve on results of Gaudio and Mossel by polynomial factors. We also give a sharpening of a result of Huang and Tikhomirov for $r=1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_14218 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Shotgun assembly of random graphs Johnston, Tom Kronenberg, Gal Roberts, Alexander Scott, Alex Combinatorics Discrete Mathematics Probability In the graph shotgun assembly problem, we are given the balls of radius $r$ around each vertex of a graph and asked to reconstruct the graph. We study the shotgun assembly of the Erdős-Rényi random graph $\mathcal G(n,p)$ for a wide range of values of $r$. We determine the threshold for reconstructibility for each $r\geq 3$, extending and improving substantially on results of Mossel and Ross for $r=3$. For $r=2$, we give upper and lower bounds that improve on results of Gaudio and Mossel by polynomial factors. We also give a sharpening of a result of Huang and Tikhomirov for $r=1$. |
| title | Shotgun assembly of random graphs |
| topic | Combinatorics Discrete Mathematics Probability |
| url | https://arxiv.org/abs/2211.14218 |