Papers › The number of optimal matchings for Euclidean Assignment on the line
The number of optimal matchings for Euclidean Assignment on the line
Sergio Caracciolo, Vittorio Erba, Andrea Sportiello
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We consider the Random Euclidean Assignment Problem in dimension d=1, with linear cost function. In this version of the problem, in general, there is a large degeneracy of the ground state, i.e. there are many different optimal matchings (say, ∼exp(S_N) at size N). We characterize all possible optimal matchings of a given instance of the problem, and we give a simple product formula for their number. Then, we study the probability distribution of S_N (the zero-temperature entropy of the model), in the uniform random ensemble. We find that, for large N, S_N ∼1/2 N logN + N s + 𝒪( logN ), where s is a random variable whose distribution p(s) does not depend on N. We give expressions for the asymptotics of the moments of p(s), both from a formulation as a Brownian process, and via singularity analysis of the generating functions associated to S_N. The latter approach provides a combinatorial framework that allows to compute an asymptotic expansion to arbitrary order in 1/N for the mean and the variance of
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections