The transportation cost from the uniform measure to the empirical measure in dimension \(\geq 3\) (Q1336571)

Let \(X_ 1, \dots, X_ n\), \(X_ 1', \dots, X_ n'\) be \(2n\) independent variables, uniformly distributed over \([0,1]^ d\), with \(d \geq 3\). The transportation cost from \(X_ 1, \dots, X_ n\) towards \(X_ 1', \dots, X_ n'\) is \[ \theta : = \text{Min}_{\sigma \in S_ n} \frac1n \sum^ n_{i = 1} \varphi \left({X_ i - X_{\sigma (i)}' \over Kn^{-1/d}} \right), \] where \(S_ n\) denotes the \(n\)th symmetric group, \(K\) is a constant depending only upon \(d\), and \(\varphi\) is a convex function from \(\mathbb{R}^ d\) into \([0, \infty]\), null in 0. This work is devoted to prove the following tight result: Under the necessary condition that \(\{\varphi \leq t\}\) has Lebesgue measure greater than \(\text{Log} t\) for any \(t>0\), if \(\varphi\) verifies some mild regularity conditions, then \(\theta \leq 1\) with probability \(\geq 1 - Kn^{-2}\). This theorem extends previous results by Ajtai, Komlós, Tusnády, Leighton, Shor, Yukich, Rhee and the author himself, where the function \(\varphi\) was mainly the Euclidean norm or derived from it. The proof, based on a duality method, is hard, long, highly technical and involved.