Shotgun assembly of unlabeled Erdos-Renyi graphs
成果类型：
Article
署名作者：
Huang, Han; Tikhomirov, Konstantin
署名单位：
University of Missouri System; University of Missouri Columbia; Carnegie Mellon University
刊物名称：
PROBABILITY THEORY AND RELATED FIELDS
ISSN/ISSBN：
0178-8051
DOI：
10.1007/s00440-024-01347-4
发表日期：
2025
页码：
575-624
关键词：
摘要：
Given a positive integer n, an unlabeled graph G on n vertices, and a vertex v of G, let N-G(v) be the subgraph of G induced by vertices of G of distance at most one from v. We show that there are universal constants C, c > 0 with the following property. Let the sequence (p(n))(n=1)(8) satisfy n(-1/2) log(n)(C) <= pn <= c. For each n, let Gamma(n) be an unlabeled G(n, p(n)) Erdos-Renyi graph. Then with probability 1 - o(n)(1), any unlabeled graph (Gamma) over tilde (n) on n vertices with {N (Gamma) over tilde (n) (v)}(v) = {N-Gamma n (v)}(v) must coincide with Gamma(n). This establishes (Theta) over tilde (n(-1/2)) as the transition range for the density parameter pn between reconstructability and non-reconstructability of Erdos-Renyi graphs from their 1-neighborhoods, and resolves a problem of Gaudio and Mossel from (Electron Commun Probab 27: 1-14, 2022)