Mean field and corrections for the Euclidean Minimum Matching problem

Jacques Boutet de Monvel ¹, Olivier C. Martin ¹

Physical Review Letters 79 (1997) 167-170

Consider the length $L_{MM}^E$ of the minimum matching of N points in d-dimensional Euclidean space. Using numerical simulations and the finite size scaling law $< L_{MM}^E > = \\beta_{MM}^E(d) N^{1-1/d}(1+A/N+… )$, we obtain precise estimates of $\\beta_{MM}^E(d)$ for $2 \\le d \\le 10$. We then consider the approximation where distance correlations are neglected. This model is solvable and gives at $d \\ge 2$ an excellent « random link\’\’ approximation to $\\beta_{MM}^E(d)$. Incorporation of three-link correlations further improves the accuracy, leading to a relative error of 0.4% at d=2 and 3. Finally, the large d behavior of this expansion in link correlations is discussed.

• 1. Division de Physique Théorique, IPN,
  Université Paris XI – Paris Sud