Eur. Phys. J. B 22, 229-237 (2001)
https://doi.org/10.1007/PL00011144

Neighborhood preferences in random matching problems

Dipartimento di Fisica, INFM and INFN, Università di Roma 1 "La Sapienza" , P.le A. Moro, 2, 00185 Roma, Italy

Corresponding authors: ^a giorgio.parisi@roma1.infn.it - ^b matthieu.ratieville@roma1.infn.it

Received: 14 February 2001
Published online: 15 July 2001

Abstract

We consider a class of random matching problems where the distance between two points has a probability law which, for a small distance l, goes like l^r. In the framework of the cavity method, in the limit of an infinite number of points, we derive equations for p_k, the probability for some given point to be matched to its kth nearest neighbor in the optimal configuration. These equations are solved in two limiting cases: r=0 -where we recover pk=1/2^k, as numerically conjectured by Houdayer et al. and recently rigorously proved by Aldous - and r → +∞. For 0<r<+∞, we are not able to solve the equations analytically, but we compute the leading behavior of p_k for large k.