2020/09/30 by Michael Goldman, Dario Trevisan
Mathematics · Physics and Astronomy · #Bipartite graph #Context (archaeology) #Convergence (economics) #Euclidean distance #Euclidean geometry #Markov Chains and Monte Carlo Methods #Matching (statistics) #Mathematical proof #Point processes and geometric inequalities #Random permutation #Stochastic processes and statistical mechanics #Unit cube #math-ph #math.AP #math.MP #math.PR
paper · pdf · doi:10.2140/pmp.2021.2.121
published as Prob. Math. Phys. 2 (2021) 341-362
openalex created_date 2020/09/14 · arxiv created 2020/12/17 · openalex publication_date 2021/05/22 · arxiv updated 2021/06/02 · openalex updated_date 2026/08/05
We investigate the average minimum cost of a bipartite matching between two samples of n independent random points uniformly distributed on a unit cube in d ≥ 3 dimensions, where the matching cost between two points is given by any power p ≥ 1 of their Euclidean distance. As n grows, we prove convergence, after a suitable renormalization, towards a finite and positive constant. We also consider the analogous problem of optimal transport between n points and the uniform measure. The proofs combine sub-additivity inequalities with a PDE ansatz similar to the one proposed in the context of the matching problem in two dimensions and later extended to obtain upper bounds in higher dimensions.