Matching recovery threshold for correlated random graphs

DOI10.1214/23-AOS2305arXiv2205.14650MaRDI QIDQ6183756

No author found.

Publication date: 4 January 2024

Published in: The Annals of Statistics (Search for Journal in Brave)

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

zbMATH Keywords

correlated Erdős-Rényi random graphinformation thresholdmatching recovery

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (2)

Correlation detection in trees for planted graph alignment ⋮ A polynomial-time approximation scheme for the maximal overlap of two independent Erdős-Rényi graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The densest subgraph problem in sparse random graphs
• The cycle structure of random permutations
• Correlated randomly growing graphs
• Efficient random graph matching via degree profiles
• Load balancing and orientability thresholds for random hypergraphs
• Introduction to Random Graphs
• Generalized Sphere-Packing Bounds on the Size of Codes for Combinatorial Channels
• Performance of global load balancing by local adjustment
• Settling the Sharp Reconstruction Thresholds of Random Graph Matching
• Seeded graph matching via large neighborhood statistics
• Seeded graph matching for correlated Erd\H{o}s-R\'enyi graphs
• The Multiple-Orientability Thresholds for Random Hypergraphs
• Exact matching of random graphs with constant correlation
• Spectral graph matching and regularized quadratic relaxations. II: Erdős-Rényi graphs and universality
• The planted matching problem: sharp threshold and infinite-order phase transition
• Testing correlation of unlabeled random graphs

This page was built for publication: Matching recovery threshold for correlated random graphs