Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 16 min ago
PreprintarXiv licencearXiv

The second reconstruction transition for random graphs from 2-neighborhoods

  • Yiming Chen
Open at sourcePDFDOICite

Abstract

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 p≥ n−3/4(log n)3. Together with the non-reconstructibility result of Johnston, Kronenberg, Roberts and Scott, our result locates the second reconstruction transition at the scale p=n−3/4 up to polylogarithmic factors, resolving a question they posed. Our proof relies on a global rigidity argument exploiting 5-cycle constraints.

Related

  1. Second-Order Cover Time of Random Regular Graphs
    Lisa Hartung, Andreas Klippel
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  2. A second-moment proof of quenched equals annealed for the Potts model on random regular graphs
    Remco van der Hofstad, Kai-Chun Huang, Noela Müller +1
    arXivPreprintCC BY-NC-SA 4.0Full textProbabilityarXiv
  3. A first order phase transition for lower tails in sparse random graphs
    Byron Chin
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  4. Planar graphs whose second largest eigenvalue does not exceed 1
    Zihao Geng, Zhiwen Wang, Wen-Jun Li +3
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Second order estimates on transition layers for the Allen-Cahn equation with homogeneous Neumann boundary conditions: Part I - Boundary-orthogonal transition layers
    Akashdeep Dey, Wenkui Du, Davide Parise +1
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsGeometry & topologyarXiv

Cite

BibTeXRIS
BibTeX
@misc{chen2026second,
  title = {{The second reconstruction transition for random graphs from 2-neighborhoods}},
  author = {Yiming Chen},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.07890},
  eprint = {2611.07890},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.07890},
}
RIS
TY  - UNPB
TI  - The second reconstruction transition for random graphs from 2-neighborhoods
AU  - Yiming Chen
PY  - 2026
DA  - 2026/11/05
PB  - arXiv
DO  - 10.48550/arxiv.2611.07890
UR  - https://arxiv.org/abs/2611.07890
AB  - 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 p≥ n^−3/4(log n)^3. Together with the non-reconstructibility result of Johnston, Kronenberg, Roberts and Scott, our result locates the second reconstruction transition at the scale p=n^−3/4 up to polylogarithmic factors, resolving a question they posed. Our proof relies on a global rigidity argument exploiting 5-cycle constraints.
ER  -