Si considerano 2N punti e una matrice l(i,j)=l(j,i) di 'distanze' tra di loro. Un matching consiste in accoppiare questi punti. Tale matching ha un costo uguale alla somma delle distanze tra i punti di ogni coppia. Nel caso in cui gli l(i,j) siano variabili aleatorie indipendenti e uniformamente distribuite su [0,1], mostriamo col metodo della cavita che nel limite N infinito, la probabilita che un punto sia collegato al suo k-esimo vicino nel matching di costo minimo e 2^(-k), come congetturato da J. Houdayer et al. (cond-mat/9803195)

Ritorno all'elenco dei poster