The second reconstruction transition for random graphs from 2-neighborhoods

Yiming Chen

We prove that, with high probability, the Erdős--Rényi random graph $G(n,p)$ is reconstructible up to isomorphism from the multiset of its rooted induced 2-neighborhoods whenever $…