{"id":"arxiv/2611.06845","url":"https://arxiv.org/abs/2611.06845","tags":["math.PR","math.CO","math.MG"],"score":0,"title":"Matching Random Point Sets with Minimum Distortion","domain":"math.PR","source":"arxiv","authors":["Itai Benjamini","Mark Braverman","Elad Tzalik","Georgii Zakharov"],"reviews":0,"subject":"math.PR","summary":"How well can two independent random samples from a metric measure space be matched while preserving pairwise distances? Concretely, given two independent copies, each of $n$ points sampled from the space, what is their typical metric distortion as finite $n$-point metric spaces? We prove that the space $[0,1]$ equipped with the uniform measure already exhibits a rich behavior. We show that with high probability the distortion of the two independent samples is $n^{2/3}$ up to polylogarithmic factors. The lower bound reflects two competing obstructions. A bijection that maps points close to…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-04","reactions":{}}