Abstract
We study the random-link matching problem on random regular graphs, along with two relaxed versions of the problem, namely the fractional matching and the so-called 'loopy' fractional matching. We estimate the asymptotic average optimal cost using the cavity method. Moreover, we 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, which have already been analyzed in the literature.
| Original language | English |
|---|---|
| Journal | Journal of Statistical Mechanics: Theory and Experiment |
| Volume | 2020 |
| Issue number | 033301 |
| Early online date | 11 Mar 2020 |
| DOIs | |
| Publication status | E-pub ahead of print - 11 Mar 2020 |