J. Phys. France 49, 2019-2025 (1988)
DOI: 10.1051/jphys:0198800490120201900

The Euclidean matching problem

Marc Mézard¹ et Giorgio Parisi<sup>2

1</sup>  Laboratoire Propre du Centre National de la Recherche Scientifique, associé à l'Ecole Normale Supérieure et à l'Université de Paris-Sud, 24, rue Lhomond, 75231 Paris, France
²  Università di Roma , « Tor Vergata », and INFN, Roma, Italia

Abstract
We study the matching problem in finite dimensions. The Euclidean correlations of the distances can be taken into account in a systematic way. With respect to the case of independent random distances which we have studied before, the adjonction of Euclidean triangular correlations gives rise to corrections which vanish when the dimension of space goes to infinity, and remain relatively small in any dimensions.

Résumé
Nous étudions le problème du couplage (« matching ») en dimension finie. Les corrélations euclidiennes entre les distances peuvent être prises en compte de manière systématique. Par rapport au cas des distances aléatoires indépendantes que nous avions étudiées précédemment, les corrélations triangulaires euclidiennes engendrent des corrections qui s'annulent dans la limite où la dimension de l'espace tend vers l'infini, et restent relativement petites à toute dimension.

PACS
0210 - Logic, set theory, and algebra.

Key words
matrix algebra -- polynomials