Settling the Sharp Reconstruction Thresholds of Random Graph Matching

DOI10.1109/TIT.2022.3169005zbMath1505.60015arXiv2102.00082OpenAlexW3127515714MaRDI QIDQ5096999

Yihong Wu, Jiaming Xu, Sophie H. Yu

Publication date: 19 August 2022

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2102.00082

zbMATH Keywords

recoveringErdős-Rényi graphshidden vertex correspondence between two edge-correlated random graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Information theory (general) (94A15) Statistical aspects of information-theoretic topics (62B10)

Related Items (4)

Exact matching of random graphs with constant correlation ⋮ Testing correlation of unlabeled random graphs ⋮ Matching recovery threshold for correlated random graphs ⋮ Unnamed Item

This page was built for publication: Settling the Sharp Reconstruction Thresholds of Random Graph Matching