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)

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