Exact matching of random graphs with constant correlation

DOI10.1007/s00440-022-01184-3zbMath1512.05361arXiv2110.05000OpenAlexW4313595333MaRDI QIDQ6041769

M. V. Rudel'son, Konstantin Tikhomirov, Cheng Mao

Publication date: 12 May 2023

Published in: Probability Theory and Related Fields (Search for Journal in Brave)

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

zbMATH Keywords

Erdős-Rényi graphs\(k\) alignment

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Spectral graph matching and regularized quadratic relaxations. I: Algorithm and Gaussian analysis ⋮ Matching recovery threshold for correlated random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved random graph isomorphism
• Efficient random graph matching via degree profiles
• Random Graph Isomorphism
• Distinguishing Vertices of Random Graphs
• High-Dimensional Probability
• Settling the Sharp Reconstruction Thresholds of Random Graph Matching
• Seeded graph matching via large neighborhood statistics
• Graph isomorphism in quasipolynomial time [extended abstract]