On the finite size corrections to some random matching problems

Abstract

We get back to the computation of the leading finite size corrections to some random link matching problems, first adressed by Mezard and Parisi [J. Physique 48 (1987) 1451-1459]. In the so-called bipartite case, their result is in contradiction with subsequent works. We show that they made some mistakes, and correcting them, we get the expected result. In the non bipartite case, we agree with their result but push the analytical treatment further

22 pages, 3 figures

Cited by in corpus (18)

• Scaling hypothesis for the Euclidean bipartite matching problem
• Topology trivialization and large deviations for the minimum in the simplest random optimization
• Random multi-index matching problems
• Loop expansion around the Bethe approximation through the $M$-layer construction
• Finite size corrections to disordered systems on Erdös-Rényi random graphs
• Near optimal configurations in mean field disordered systems
• Random Euclidean matching problems in one dimension
• One-loop diagrams in the Random Euclidean Matching Problem
• Finite-size corrections in the random assignment problem
• Fluctuations in the random-link matching problem
• Anomalous scaling of the optimal cost in the one-dimensional random assignment problem
• Criticality and conformality in the random dimer model
• Random-link matching problems on random regular graphs
• The Random Fractional Matching Problem
• Phase transition in the bipartite z-matching
• Average optimal cost for the Euclidean TSP in one dimension
• Phase transition in the assignment problem for random matrices
• On the number of $k$-cycles in the assignment problem for random matrices