Shotgun assembly of random regular graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2015
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908684679905280 |
|---|---|
| author | Huang, Brice Mossel, Elchanan Sun, Nike Zhang, Claire Zhou, Leqi |
| author_facet | Huang, Brice Mossel, Elchanan Sun, Nike Zhang, Claire Zhou, Leqi |
| contents | Mossel and Ross (2019) introduce the shotgun assembly problem for random graphs: what radius $R$ ensures that the random graph $G$ can be uniquely recovered from its list of rooted $R$-neighborhoods, with high probability? Here we consider this question for random regular graphs of fixed degree $d\ge3$. A result of Bollobás (1982) implies efficient recovery at $R = (1 + ε) \frac12 \log_{d-1}n$ with high probability -- moreover, this recovery algorithm uses only a summary of the distances in each neighborhood. We show that using the full neighborhood structure gives a sharper bound \[
R = \frac{\log n + \log\log n}{2\log(d-1)} + O(1)\,, \] which we prove is tight up to the $O(1)$ term. One consequence of our proof is that if $G,H$ are independent graphs where $G$ follows the random regular law, then with high probability the graphs are non-isomorphic; furthermore, this can be efficiently certified by testing the $R$-neighborhood list of $H$ against the $R$-neighborhood of a single adversarially chosen vertex of $G$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1512_08473 |
| institution | arXiv |
| publishDate | 2015 |
| record_format | arxiv |
| spellingShingle | Shotgun assembly of random regular graphs Huang, Brice Mossel, Elchanan Sun, Nike Zhang, Claire Zhou, Leqi Probability 05C80, 05C60 Mossel and Ross (2019) introduce the shotgun assembly problem for random graphs: what radius $R$ ensures that the random graph $G$ can be uniquely recovered from its list of rooted $R$-neighborhoods, with high probability? Here we consider this question for random regular graphs of fixed degree $d\ge3$. A result of Bollobás (1982) implies efficient recovery at $R = (1 + ε) \frac12 \log_{d-1}n$ with high probability -- moreover, this recovery algorithm uses only a summary of the distances in each neighborhood. We show that using the full neighborhood structure gives a sharper bound \[ R = \frac{\log n + \log\log n}{2\log(d-1)} + O(1)\,, \] which we prove is tight up to the $O(1)$ term. One consequence of our proof is that if $G,H$ are independent graphs where $G$ follows the random regular law, then with high probability the graphs are non-isomorphic; furthermore, this can be efficiently certified by testing the $R$-neighborhood list of $H$ against the $R$-neighborhood of a single adversarially chosen vertex of $G$. |
| title | Shotgun assembly of random regular graphs |
| topic | Probability 05C80, 05C60 |
| url | https://arxiv.org/abs/1512.08473 |