2021/08/22 by Huang, Han, Tikhomirov, Konstantin
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2108.09636
Given a positive integer n, an unlabeled graph G on n vertices, and a vertex v of G, let NG(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 (pn)n=1^∞ satisfy n-1/2logC n≤ pn≤ c. For each n, let Γn be an unlabeled G(n,pn) Erdös-Rényi graph. Then with probability 1-on(1), any unlabeled graph Γn on n vertices with \N Γn(v)\v=\NΓn(v)\v must coincide with Γn. This establishes Θ(n-1/2) as the transition range for the density parameter pn between reconstructability and non-reconstructability of Erdös-Rényi graphs from their 1-neighborhoods, and resolves a problem of Gaudio and Mossel.