Random-link matching problems on random regular graphs

Abstract

We study the random-link matching problem on random regular graphs, alongside with two relaxed versions of the problem, namely the fractional matching and the so-called "loopy" fractional matching. We estimated the asymptotic average optimal cost using the cavity method. Moreover, we also study the finite-size corrections due to rare topological structures appearing in the graph at large sizes. We estimate these contributions using the cavity approach, and we compare our results with the output of numerical simulations. The analysis also clarifies the meaning of the finite-size contributions appearing in the fully-connected version of the problem, that has been already analyzed in the literature.

References in corpus (16)

• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Maximum Weight Matching via Max-Product Belief Propagation
• The number of matchings in random graphs
• How to Compute Loop Corrections to Bethe Approximation
• Scaling hypothesis for the Euclidean bipartite matching problem
• Charting the replica symmetric phase
• Scaling hypothesis for the Euclidean bipartite matching problem II. Correlation functions
• Finite size corrections to disordered Ising models on Random Regular Graphs
• Finite size corrections to disordered systems on Erdös-Rényi random graphs
• On the finite size corrections to some random matching problems
• Quadratic stochastic Euclidean bipartite matching problem
• One-loop diagrams in the Random Euclidean Matching Problem
• Fluctuations in the random-link matching problem
• One-dimensional disordered Ising models by replica and cavity methods
• The Random Fractional Matching Problem

Cited by in corpus (5)

• Recovery thresholds in the sparse planted matching problem
• Criticality and conformality in the random dimer model
• The Ising spin glass on random graphs at zero temperature: not all spins are glassy in the glassy phase
• Thermodynamics of the Fredrickson-Andersen Model on the Bethe Lattice
• The Sherrington-Kirkpatrick model for spin glasses: A new approach for the solution