On optimal matchings (Q1056968)

For two sets \(\{x_ 1,...,x_ n\}\), \(\{y_ 1,...,y_ n\}\) the transportation cost is defined as \(\min \{d(x_{\pi (1)},y_ 1)+...+d(x_{\pi (n)},y_ n): \pi\) permutation\(\}\), where d stands for distance. Consider now i.i.d. random variables \(X_ 1,...,X_ n\), \(Y_ 1,...,Y_ n\), uniformly distributed on the unit square, with associated random transportation cost \(T_ n\). It is shown in this paper that, for suitable constants \(C_ 1,C_ 2>0\), the probability of the event \[ C_ 1(n \log n)^{1/2}<T_ n<C_ 2(n \log n)^{1/2} \] converges to 1 as n tends to infinity.