Scaling and non-standard matching theorems
Michel Talagrand · Comptes Rendus Mathématique · 2018
Consider the standard Gaussian measure μ on R 2 . Consider independent r.v.s ( X i ) i ≤ N distributed according to μ , and an independent copy ( Y i ) i ≤ N of these r.v.s. We prove that, for some number C and N large, we have ( log N ) 2 C ≤ E inf π ∑ i ≤ N d ( X i , Y π ( i ) ) 2 ≤ C ( log N ) 2 , where the infimum is over all permutations π of { 1 , … , N } . The striking point of this result is the factor ( log N ) 2 . Indeed, if instead of μ we consider the uniform distribution on the unit square, it is well known that the proper factor is log N . The upper bound was proved by Michel Ledoux (2017) [3].