Annealed quantitative estimates for the quadratic 2D-discrete random matching problem

Francesco Mattesini; Nicolas Clozeau

arxiv: 2303.00353 · v2 · submitted 2023-03-01 · 🧮 math.PR · math.AP

Annealed quantitative estimates for the quadratic 2D-discrete random matching problem

Nicolas Clozeau , Francesco Mattesini This is my paper

Pith reviewed 2026-05-24 09:01 UTC · model grok-4.3

classification 🧮 math.PR math.AP

keywords random matchingoptimal transportMonge-Ampère equationempirical measuresα-mixingMarkov chainsRiemannian manifoldsquadratic cost

0 comments

The pith

The optimal transport plan between empirical measures of correlated random points on compact 2D manifolds is quantitatively approximated by the pushforward of the identity map under the exponential of the gradient of a solution to a regular

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper examines the quadratic random matching problem on closed compact 2-dimensional Riemannian manifolds with respect to the squared Riemannian distance. It considers two sequences of random points whose numbers are asymptotically equivalent, with common law absolutely continuous with positive bounded density. The central result is that the optimal transport plan between the empirical measures is quantitatively well-approximated by the pushforward (Id, exp(∇h^n))_# μ^n, where h^n solves a linear elliptic PDE coming from a regularized first-order linearization of the Monge-Ampère equation. The approximation is proved under stretched exponential α-mixing or for points generated by discrete-time Markov chains with unique absolutely continuous invariant measure. A reader would care because the result gives explicit control on the behavior of random optimal matchings in two dimensions under dependence.

Core claim

The optimal transport plan between the two empirical measures μ^n and ν^m is quantitatively well-approximated by (Id, exp(∇h^n))_# μ^n where h^n solves a linear elliptic PDE obtained by a regularized first-order linearization of the Monge-Ampère equation. This holds asymptotically as n tends to infinity with m equivalent to n, for samples of correlated random points satisfying stretched exponential decay of the α-mixing coefficient or arising from a discrete-time Markov chain possessing a unique absolutely continuous invariant measure with respect to the volume measure.

What carries the argument

The approximating map (Id, exp(∇h^n))_# μ^n, where h^n is the solution to the regularized linearized Monge-Ampère PDE, which serves as a quantitative proxy for the true optimal transport plan between the empirical measures.

If this is right

The approximation error vanishes at a rate controlled by the mixing decay and the density bounds.
The result extends quantitative matching estimates from independent samples to dependent samples generated by Markov chains.
The linear elliptic PDE provides an explicit, solvable proxy whose gradient yields a near-optimal matching map.
Asymptotic equivalence of the sample sizes n and m is sufficient for the approximation to hold uniformly.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same linearization technique may yield similar quantitative control when the cost is a small perturbation of the squared distance.
Numerical solution of the linear PDE could serve as a practical surrogate for computing matchings between large correlated datasets on surfaces.
The mixing assumptions suggest that the result may extend to other ergodic processes whose correlation decays sufficiently fast.

Load-bearing premise

The common law of the random points is absolutely continuous with respect to volume measure with strictly positive and bounded density, and the points satisfy either stretched exponential α-mixing or arise from a discrete-time Markov chain with a unique absolutely continuous invariant measure.

What would settle it

A sequence of point configurations on the torus whose common density vanishes on a positive-measure set, or whose mixing coefficients decay only polynomially, for which the Wasserstein distance between the true optimal plan and the PDE-derived map stays bounded away from zero as n grows.

read the original abstract

We study a random matching problem on closed compact $2$-dimensional Riemannian manifolds (with respect to the squared Riemannian distance), with samples of random points whose common law is absolutely continuous with respect to the volume measure with strictly positive and bounded density. We show that given two sequences of numbers $n$ and $m=m(n)$ of points, asymptotically equivalent as $n$ goes to infinity, the optimal transport plan between the two empirical measures $\mu^n$ and $\nu^{m}$ is quantitatively well-approximated by $\big(\mathrm{Id},\exp(\nabla h^{n})\big)_\#\mu^n$ where $h^{n}$ solves a linear elliptic PDE obtained by a regularized first-order linearization of the Monge-Amp\`ere equation. This is obtained in the case of samples of correlated random points for which a stretched exponential decay of the $\alpha$-mixing coefficient holds and for a class of discrete-time Markov chains having a unique absolutely continuous invariant measure with respect to the volume measure.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives quantitative annealed estimates for random OT on 2D manifolds by approximating the transport plan with a map from a regularized linearized Monge-Ampere PDE, under mixing or Markov assumptions on the points.

read the letter

The main point is that this work shows the optimal transport plan between two empirical measures on a compact 2D Riemannian manifold is quantitatively close to the map (Id, exp(∇h^n))#μ^n, where h^n comes from a regularized linearization of the Monge-Ampere equation. They get this for samples whose common law has positive bounded density, and they handle both stretched-exponential α-mixing and discrete-time Markov chains with a unique absolutely continuous invariant measure. The result is annealed, meaning averaged over the randomness of the points. This looks new in the correlated setting; most prior quantitative matching results I know of stay with independent samples. The linearization step lets them reduce the problem to a linear elliptic PDE, which is a clean way to get explicit control. The assumptions on density and mixing are stated plainly and seem chosen to give the needed concentration and regularity. One soft spot is that the abstract gives no explicit rates or constants, so the actual strength of the bounds will depend on how the remainder terms are handled in the proofs. The 2D manifold setting adds curvature terms that must be controlled, but nothing in the setup suggests an obvious obstruction. The stress-test note finds no internal inconsistency, which matches the direct structure described. This is a technical paper for people working on quantitative optimal transport and random matching on manifolds. A reader already familiar with the Monge-Ampere linearization technique will see the most value in the extension to correlated points. It shows clear engagement with the literature on the problem setup. I would send it to peer review so the details of the error estimates can be checked.

Referee Report

2 major / 3 minor

Summary. The paper claims that, on a compact 2-dimensional Riemannian manifold, for two sequences of n and m(n)∼n random points whose common law is absolutely continuous w.r.t. volume with strictly positive bounded density, the optimal transport plan between the empirical measures μ^n and ν^m is quantitatively approximated (in a suitable annealed sense) by the map (Id, exp(∇h^n))_#μ^n, where h^n solves a linear elliptic PDE obtained from a regularized first-order linearization of the Monge-Ampère equation. The result is proved both under stretched-exponential α-mixing of the point process and for discrete-time Markov chains possessing a unique absolutely continuous invariant measure.

Significance. If the quantitative estimates hold, the work supplies annealed control on the linearization error for the random matching problem in the correlated setting, extending earlier i.i.d. results to processes with mixing or Markovian dependence. The explicit use of the linearized Monge-Ampère PDE and the mixing hypotheses yields concrete rates that are potentially useful for applications in geometric probability and statistical optimal transport.

major comments (2)

[§2.2, (2.8)] §2.2, display (2.8): the regularization parameter ε_n appearing in the linearized PDE for h^n is introduced without an explicit relation to n; the subsequent error analysis in Theorem 1.1 therefore leaves the dependence of the approximation constant on ε_n implicit, which is load-bearing for the claimed quantitative bound.
[Theorem 1.1, (1.3)] Theorem 1.1, display (1.3): the high-probability bound is stated uniformly in the mixing coefficient α, yet the proof sketch in §4 only controls the α-mixing contribution via a generic exponential inequality; an explicit tracking of the stretched-exponential rate inside the final constant is needed to confirm the result is not vacuous under the stated hypothesis.

minor comments (3)

[Abstract] The abstract states that n and m are “asymptotically equivalent”; this should be replaced by the precise assumption m/n→1 that is used in the proofs.
[Introduction] Notation for the exponential map exp(∇h^n) is used from the introduction onward but is only defined in §2.1; a brief reminder in the statement of the main theorem would improve readability.
[§1.2] Several citations to the deterministic matching literature (e.g., the works of Ambrosio–Stra and Figalli) appear only in the introduction; they should be recalled at the points where the linearization technique is compared with those references.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We appreciate the referee's positive evaluation and recommendation for minor revision. The comments highlight areas where the quantitative aspects can be made more explicit, which we will address in the revision.

read point-by-point responses

Referee: [§2.2, (2.8)] §2.2, display (2.8): the regularization parameter ε_n appearing in the linearized PDE for h^n is introduced without an explicit relation to n; the subsequent error analysis in Theorem 1.1 therefore leaves the dependence of the approximation constant on ε_n implicit, which is load-bearing for the claimed quantitative bound.

Authors: We concur that an explicit relation between ε_n and n is necessary for a fully quantitative statement. In the updated manuscript, we will specify ε_n explicitly in terms of n (chosen to balance the linearization error with the approximation and mixing terms), and we will propagate this choice into the constants of Theorem 1.1. This revision will clarify the load-bearing dependence. revision: yes
Referee: [Theorem 1.1, (1.3)] Theorem 1.1, display (1.3): the high-probability bound is stated uniformly in the mixing coefficient α, yet the proof sketch in §4 only controls the α-mixing contribution via a generic exponential inequality; an explicit tracking of the stretched-exponential rate inside the final constant is needed to confirm the result is not vacuous under the stated hypothesis.

Authors: We acknowledge that the current presentation uses a generic bound for the mixing term. To address this, we will modify the proof in §4 to substitute the stretched-exponential decay rate of the α-mixing coefficient directly into the exponential inequality, thereby obtaining an explicit expression for the constant in (1.3) that depends on the mixing parameters. This will demonstrate that the bound remains meaningful and non-vacuous under the hypothesis. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper establishes a quantitative approximation of the optimal transport plan between empirical measures by the push-forward of a map derived from the regularized linearization of the Monge-Ampère equation. This rests on explicit assumptions (positive bounded density, stretched-exponential α-mixing or Markov invariance) that directly enable the necessary concentration and regularity estimates. No step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation; the argument proceeds via standard analytic techniques in optimal transport without renaming known results or smuggling ansatzes. The result is therefore independent of its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Review performed on abstract only; ledger is therefore incomplete and limited to assumptions explicitly named in the abstract.

axioms (2)

standard math Standard existence and regularity theory for the Monge-Ampère equation on compact Riemannian manifolds
Invoked implicitly when linearizing the Monge-Ampère equation to obtain the elliptic PDE for h^n
domain assumption Existence of a unique absolutely continuous invariant measure for the considered class of Markov chains
Stated as a hypothesis on the discrete-time Markov chains in the abstract

pith-pipeline@v0.9.0 · 5708 in / 1353 out tokens · 44047 ms · 2026-05-24T09:01:45.347294+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel (J(x)=½(x+x^{-1})−1 unique Aczél solution) unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

the optimal transport plan between the two empirical measures μ^n and ν^m is quantitatively well-approximated by (Id, exp(∇h^n))_# μ^n where h^n solves a linear elliptic PDE obtained by a regularized first-order linearization of the Monge-Ampère equation
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

−∇·ρ∇h^{n,t}=μ^{n,t}−ν^{m,t} (heat-regularized Poisson)
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean LogicNat ≃ Nat recovery unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

stretched exponential α-mixing / Markov invariant measure assumptions

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

60 extracted references · 60 canonical work pages · 1 internal anchor

[1]

Ajtai, J

M. Ajtai, J. Koml´ os, and G. Tusn´ ady. On optimal matchings.Combinatorica, 4:259–264, 1984

work page 1984
[2]

Alsmeyer

G. Alsmeyer. On the harris recurrence of iterated random Lipschitz functions and related convergence rate results. Journal of Theoretical Probability, 16(1):217–247, Jan 2003

work page 2003
[3]

Ambrosio and F

L. Ambrosio and F. Glaudo. Finer estimates on the 2-dimensional matching problem. Journal de l’ ´Ecole polytechnique—Math´ ematiques, 6:737–765, 2019

work page 2019
[4]

Ambrosio, F

L. Ambrosio, F. Glaudo, and D. Trevisan. On the optimal map in the 2-dimensional random matching problem. Discrete and Continuous Dynamical Systems , 39(12):7291–7308, 2019

work page 2019
[5]

Ambrosio, M

L. Ambrosio, M. Goldman, and D. Trevisan. On the quadratic random matching problem in two-dimensional domains. Electronic Journal of Probability, 27:1–35, 2022

work page 2022
[6]

Ambrosio, F

L. Ambrosio, F. Stra, and D. Trevisan. A PDE approach to a 2-dimensional matching problem. Probability Theory and Related Fields , 173(1):433–477, 2019

work page 2019
[7]

T. Aubin. Some nonlinear problems in Riemannian geometry . Springer Science & Business Media, 1998

work page 1998
[8]

R. B. Bapat and T. E. S. Raghavan. Doubly stochastic matrices, page 59–114. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1997

work page 1997
[9]

Barthe and C

F. Barthe and C. Bordenave. Combinatorial Optimization Over Two Random Point Sets , pages 483–535. Springer International Publishing, Heidelberg, 2013

work page 2013
[10]

Benamou and Y

J.-D. Benamou and Y. Brenier. A computational ﬂuid mechanics solution to the monge-kantorovich mass transfer problem. Numerische Mathematik, 84(3):375–393, 2000

work page 2000
[11]

Benedetto and E

D. Benedetto and E. Caglioti. Euclidean random matching in 2d for non-constant densities. Journal of Statistical Physics, 181(3):854–869, 2020

work page 2020
[12]

B. Borda. Empirical measures and random walks on compact spaces in the quadratic Wasserstein metric. Annales de l’Institut Henri Poincar´ e, Probabilit´ es et Statistiques, to appear, 2023

work page 2023
[13]

J. H. Boutet de Monvel and O. C. Martin. Almost sure convergence of the minimum bipartite matching functional in Euclidean space. Combinatorica, 22(4):523–530, 2002

work page 2002
[14]

Y. Brenier. Polar factorization and monotone rearrangement of vector-valued functions. Communications on Pure and Applied Mathematics , 44:375–417, 1991

work page 1991
[15]

Caglioti and F

E. Caglioti and F. Pieroni. Random matching in 2d with exponent 2 for densities deﬁned on unbounded sets, 2023

work page 2023
[16]

Caracciolo, C

S. Caracciolo, C. Lucibello, G. Parisi, and G. Sicuro. Scaling hypothesis for the Euclidean bipartite matching problem. Physical Review E, 90(1):012118, 2014

work page 2014
[17]

Caracciolo and G

S. Caracciolo and G. Sicuro. Scaling hypothesis for the Euclidean bipartite matching problem. II. correlation functions. Physical Review E, 91(6):062125, 2015

work page 2015
[18]

I. Chavel. Eigenvalues in Riemannian geometry . Academic press, 1984

work page 1984
[19]

Chung and L

F. Chung and L. Lu. Concentration inequalities and martingale inequalities: a survey. Internet mathematics, 3(1):79–127, 2006

work page 2006
[20]

V. P. Crawford and E. M. Knoer. Job matching with heterogeneous ﬁrms and workers. Econometrica, 49(2):437–450, 1981

work page 1981
[21]

Yu A. Davydov. Mixing conditions for markov chains.Theory of Probability & Its Applications, 18(2):312–328, 1974

work page 1974
[22]

Erbar, K

M. Erbar, K. Kuwada, and K.-T. Sturm. On the equivalence of the entropic curvature-dimension condition and bochner’s inequality on metric measure spaces. Inventiones mathematicae, 201(3):993–1071, 2015

work page 2015
[23]

Fournier and A

N. Fournier and A. Guillin. On the rate of convergence in Wasserstein distance of the empirical measure. Probability Theory and Related Fields , 162(3):707–738, Aug 2015

work page 2015
[24]

Gale and L

D. Gale and L. S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9–15, 1962

work page 1962
[25]

Gangbo and R

W. Gangbo and R. J. McCann. The geometry of optimal transportation. Acta Mathematica, 177(2):113–161, Sep 1996

work page 1996
[26]

Giaquinta and L

M. Giaquinta and L. Martinazzi. An introduction to the regularity theory for elliptic systems, harmonic maps and minimal graphs . Springer Science & Business Media, 2013

work page 2013
[27]

Gilbarg and N

D. Gilbarg and N. S. Trudinger. Elliptic partial diﬀerential equations of second order , volume 224. springer, 2015

work page 2015
[28]

Goldman and M

M. Goldman and M. Huesmann. A ﬂuctuation result for the displacement in the optimal matching problem. The Annals of Probability , 50(4):1446 – 1477, 2022

work page 2022
[29]

A large-scale regularity theory for the Monge-Ampere equation with rough data and application to the optimal matching problem

M. Goldman, M. Huesmann, and F. Otto. A large-scale regularity theory for the Monge-Ampere equation with rough data and application to the optimal matching problem. arXiv:1808.09250, Aug 2018

work page internal anchor Pith review Pith/arXiv arXiv 2018
[30]

Goldman and D

M. Goldman and D. Trevisan. Convergence of asymptotic costs for random Euclidean matching problems. Probability and Mathematical Physics , 2:121–142, 05 2021

work page 2021
[31]

M. Hairer. Convergence of markov processes. Lecture notes, 2021

work page 2021
[32]

Huesmann, F

M. Huesmann, F. Mattesini, and D. Trevisan. Wasserstein asymptotics for the empirical measure of fractional brownian motion on a ﬂat torus. Stochastic Processes and their Applications , 155:1–26, 2023. ANNEALED QUANTITATIVE ESTIMATES FOR THE 2D-DISCRETE RANDOM MATCHING PROBLEM 38

work page 2023
[33]

J. Jalowy. The Wasserstein distance to the circular law. Annales de l’Institut Henri Poincar´ e, Probabilit´ es et Statistiques, to appear, 2023

work page 2023
[34]

L. Koch. Geometric regularisation for optimal transport with strongly p-convex cost. in preparation, 2023+

work page 2023
[35]

M. Ledoux. On optimal matching of gaussian samples. Journal of Mathematical Sciences , 238(4):495–522, Apr 2019

work page 2019
[36]

M. Ledoux. On optimal matching of gaussian samples II. 2019

work page 2019
[37]

Ledoux and J.-X

M. Ledoux and J.-X. Zhu. On optimal matching of gaussian samples III. Probability and Mathematical Statistics, 2019

work page 2019
[38]

Lov´ asz and M

L. Lov´ asz and M. D. Plummer.Matching theory, volume 367. American Mathematical Soc., 2009

work page 2009
[39]

R. J. McCann. Polar factorization of maps on riemannian manifolds.Geometric & Functional Analysis GAFA, 11(3):589–608, Aug 2001

work page 2001
[40]

A. Mehta. Online matching and ad allocation. Foundations and Trends® in Theoretical Computer Science , 8(4):265–368, 2013

work page 2013
[41]

Merlev` ede, M

F. Merlev` ede, M. Peligrad, and E. Rio. Bernstein inequality and moderate deviations under strong mixing conditions. In High dimensional probability V: the Luminy volume , pages 273–292. Institute of Mathematical Statistics, 2009

work page 2009
[42]

Merlev` ede, M

F. Merlev` ede, M. Peligrad, and E. Rio. A Bernstein type inequality and moderate deviations for weakly dependent sequences. Probability Theory and Related Fields , 151(3):435–474, 2011

work page 2011
[43]

N. G. Meyers. An L p-estimate for the gradient of solutions of second order elliptic divergence equations. Annali della Scuola Normale Superiore di Pisa-Classe di Scienze , 17(3):189–206, 1963

work page 1963
[44]

M´ ezard and G

M. M´ ezard and G. Parisi. The Euclidean matching problem. J. Phys. France, 49(12):2019–2025, 1988

work page 2019
[45]

L. I. Nicolaescu. Lectures on the Geometry of Manifolds . World Scientiﬁc, 2020

work page 2020
[46]

R. Peyre. Comparison between W2 distance and ˙H-1 norm, and localization of Wasserstein distance. ESAIM: Control, Optimisation and Calculus of Variations , 24(4):1489–1501, 2018

work page 2018
[47]

A. Riekert. Convergence rates for empirical measures of markov chains in dual and Wasserstein distances. Statistics & Probability Letters , 189:109605, 2022

work page 2022
[48]

Santambrogio

F. Santambrogio. Optimal Transport for Applied Mathematicians: Calculus of Variations, PDEs, and Model- ing. Progress in Nonlinear Diﬀerential Equations and Their Applications. Springer International Publishing, 2015

work page 2015
[49]

G. Sicuro. Euclidean matching problems. In The Euclidean Matching Problem, pages 59–118. Springer, 2017

work page 2017
[50]

J. M. Steele. Probability theory and combinatorial optimization . SIAM, 1997

work page 1997
[51]

E. M. Stein. Topics in harmonic analysis related to the Littlewood-Paley theory.(am-63), volume 63. InTopics in Harmonic Analysis Related to the Littlewood-Paley Theory.(AM-63), Volume 63 . Princeton University Press, 2016

work page 2016
[52]

D. W. Stroock and J. Turetsky. Upper bounds on derivatives of the logarithm of the heat kernel. Communi- cations in Analysis and Geometry , 6(4):669–685, 1998

work page 1998
[53]

Talagrand

M. Talagrand. The Ajtai-Koml´ os-Tusn´ ady matching theorem for general measures. InProbability in Banach Spaces, 8: Proceedings of the Eighth International Conference , pages 39–54. Springer, 1992

work page 1992
[54]

J. A. Toth and S. Zelditch. Riemannian manifolds with uniformly bounded eigenfunctions.Duke Mathematical Journal, 111(1):97–132, 2002

work page 2002
[55]

C. Villani. Topics in optimal transportation, volume 58 of Graduate Studies in Mathematics. American Math- ematical Society, Providence, RI, 2003

work page 2003
[56]

C. Villani. Optimal Transport: Old and New . Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg, 2008

work page 2008
[57]

F.-Y. Wang. Analysis for Diﬀusion Processes on Riemannian Manifolds . WORLD SCIENTIFIC, 2013

work page 2013
[58]

F.-Y. Wang. Convergence in Wasserstein distance for empirical measures of semilinear SPDEs, 2021

work page 2021
[59]

Wang and B

F.-Y. Wang and B. Wu. Wasserstein convergence for empirical measures of subordinated diﬀusions on rie- mannian manifolds, 2021

work page 2021
[60]

Wang and J.-X

F.-Y. Wang and J.-X. Zhu. Limit theorems in Wasserstein distance for empirical measures of diﬀusion pro- cesses on Riemannian manifolds. Annales de l’Institut Henri Poincar´ e, Probabilit´ es et Statistiques, 59(1):437 – 475, 2023. (NICOLAS CLOZEAU) IST AUSTRIA, AUSTRIA Email address: NICOLAS.CLOZEAU@IST.AC.AT (FRANCESCO MATTESINI) UNIVERSIT ¨AT M ¨UNSTER...

work page 2023

[1] [1]

Ajtai, J

M. Ajtai, J. Koml´ os, and G. Tusn´ ady. On optimal matchings.Combinatorica, 4:259–264, 1984

work page 1984

[2] [2]

Alsmeyer

G. Alsmeyer. On the harris recurrence of iterated random Lipschitz functions and related convergence rate results. Journal of Theoretical Probability, 16(1):217–247, Jan 2003

work page 2003

[3] [3]

Ambrosio and F

L. Ambrosio and F. Glaudo. Finer estimates on the 2-dimensional matching problem. Journal de l’ ´Ecole polytechnique—Math´ ematiques, 6:737–765, 2019

work page 2019

[4] [4]

Ambrosio, F

L. Ambrosio, F. Glaudo, and D. Trevisan. On the optimal map in the 2-dimensional random matching problem. Discrete and Continuous Dynamical Systems , 39(12):7291–7308, 2019

work page 2019

[5] [5]

Ambrosio, M

L. Ambrosio, M. Goldman, and D. Trevisan. On the quadratic random matching problem in two-dimensional domains. Electronic Journal of Probability, 27:1–35, 2022

work page 2022

[6] [6]

Ambrosio, F

L. Ambrosio, F. Stra, and D. Trevisan. A PDE approach to a 2-dimensional matching problem. Probability Theory and Related Fields , 173(1):433–477, 2019

work page 2019

[7] [7]

T. Aubin. Some nonlinear problems in Riemannian geometry . Springer Science & Business Media, 1998

work page 1998

[8] [8]

R. B. Bapat and T. E. S. Raghavan. Doubly stochastic matrices, page 59–114. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1997

work page 1997

[9] [9]

Barthe and C

F. Barthe and C. Bordenave. Combinatorial Optimization Over Two Random Point Sets , pages 483–535. Springer International Publishing, Heidelberg, 2013

work page 2013

[10] [10]

Benamou and Y

J.-D. Benamou and Y. Brenier. A computational ﬂuid mechanics solution to the monge-kantorovich mass transfer problem. Numerische Mathematik, 84(3):375–393, 2000

work page 2000

[11] [11]

Benedetto and E

D. Benedetto and E. Caglioti. Euclidean random matching in 2d for non-constant densities. Journal of Statistical Physics, 181(3):854–869, 2020

work page 2020

[12] [12]

B. Borda. Empirical measures and random walks on compact spaces in the quadratic Wasserstein metric. Annales de l’Institut Henri Poincar´ e, Probabilit´ es et Statistiques, to appear, 2023

work page 2023

[13] [13]

J. H. Boutet de Monvel and O. C. Martin. Almost sure convergence of the minimum bipartite matching functional in Euclidean space. Combinatorica, 22(4):523–530, 2002

work page 2002

[14] [14]

Y. Brenier. Polar factorization and monotone rearrangement of vector-valued functions. Communications on Pure and Applied Mathematics , 44:375–417, 1991

work page 1991

[15] [15]

Caglioti and F

E. Caglioti and F. Pieroni. Random matching in 2d with exponent 2 for densities deﬁned on unbounded sets, 2023

work page 2023

[16] [16]

Caracciolo, C

S. Caracciolo, C. Lucibello, G. Parisi, and G. Sicuro. Scaling hypothesis for the Euclidean bipartite matching problem. Physical Review E, 90(1):012118, 2014

work page 2014

[17] [17]

Caracciolo and G

S. Caracciolo and G. Sicuro. Scaling hypothesis for the Euclidean bipartite matching problem. II. correlation functions. Physical Review E, 91(6):062125, 2015

work page 2015

[18] [18]

I. Chavel. Eigenvalues in Riemannian geometry . Academic press, 1984

work page 1984

[19] [19]

Chung and L

F. Chung and L. Lu. Concentration inequalities and martingale inequalities: a survey. Internet mathematics, 3(1):79–127, 2006

work page 2006

[20] [20]

V. P. Crawford and E. M. Knoer. Job matching with heterogeneous ﬁrms and workers. Econometrica, 49(2):437–450, 1981

work page 1981

[21] [21]

Yu A. Davydov. Mixing conditions for markov chains.Theory of Probability & Its Applications, 18(2):312–328, 1974

work page 1974

[22] [22]

Erbar, K

M. Erbar, K. Kuwada, and K.-T. Sturm. On the equivalence of the entropic curvature-dimension condition and bochner’s inequality on metric measure spaces. Inventiones mathematicae, 201(3):993–1071, 2015

work page 2015

[23] [23]

Fournier and A

N. Fournier and A. Guillin. On the rate of convergence in Wasserstein distance of the empirical measure. Probability Theory and Related Fields , 162(3):707–738, Aug 2015

work page 2015

[24] [24]

Gale and L

D. Gale and L. S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9–15, 1962

work page 1962

[25] [25]

Gangbo and R

W. Gangbo and R. J. McCann. The geometry of optimal transportation. Acta Mathematica, 177(2):113–161, Sep 1996

work page 1996

[26] [26]

Giaquinta and L

M. Giaquinta and L. Martinazzi. An introduction to the regularity theory for elliptic systems, harmonic maps and minimal graphs . Springer Science & Business Media, 2013

work page 2013

[27] [27]

Gilbarg and N

D. Gilbarg and N. S. Trudinger. Elliptic partial diﬀerential equations of second order , volume 224. springer, 2015

work page 2015

[28] [28]

Goldman and M

M. Goldman and M. Huesmann. A ﬂuctuation result for the displacement in the optimal matching problem. The Annals of Probability , 50(4):1446 – 1477, 2022

work page 2022

[29] [29]

A large-scale regularity theory for the Monge-Ampere equation with rough data and application to the optimal matching problem

M. Goldman, M. Huesmann, and F. Otto. A large-scale regularity theory for the Monge-Ampere equation with rough data and application to the optimal matching problem. arXiv:1808.09250, Aug 2018

work page internal anchor Pith review Pith/arXiv arXiv 2018

[30] [30]

Goldman and D

M. Goldman and D. Trevisan. Convergence of asymptotic costs for random Euclidean matching problems. Probability and Mathematical Physics , 2:121–142, 05 2021

work page 2021

[31] [31]

M. Hairer. Convergence of markov processes. Lecture notes, 2021

work page 2021

[32] [32]

Huesmann, F

M. Huesmann, F. Mattesini, and D. Trevisan. Wasserstein asymptotics for the empirical measure of fractional brownian motion on a ﬂat torus. Stochastic Processes and their Applications , 155:1–26, 2023. ANNEALED QUANTITATIVE ESTIMATES FOR THE 2D-DISCRETE RANDOM MATCHING PROBLEM 38

work page 2023

[33] [33]

J. Jalowy. The Wasserstein distance to the circular law. Annales de l’Institut Henri Poincar´ e, Probabilit´ es et Statistiques, to appear, 2023

work page 2023

[34] [34]

L. Koch. Geometric regularisation for optimal transport with strongly p-convex cost. in preparation, 2023+

work page 2023

[35] [35]

M. Ledoux. On optimal matching of gaussian samples. Journal of Mathematical Sciences , 238(4):495–522, Apr 2019

work page 2019

[36] [36]

M. Ledoux. On optimal matching of gaussian samples II. 2019

work page 2019

[37] [37]

Ledoux and J.-X

M. Ledoux and J.-X. Zhu. On optimal matching of gaussian samples III. Probability and Mathematical Statistics, 2019

work page 2019

[38] [38]

Lov´ asz and M

L. Lov´ asz and M. D. Plummer.Matching theory, volume 367. American Mathematical Soc., 2009

work page 2009

[39] [39]

R. J. McCann. Polar factorization of maps on riemannian manifolds.Geometric & Functional Analysis GAFA, 11(3):589–608, Aug 2001

work page 2001

[40] [40]

A. Mehta. Online matching and ad allocation. Foundations and Trends® in Theoretical Computer Science , 8(4):265–368, 2013

work page 2013

[41] [41]

Merlev` ede, M

F. Merlev` ede, M. Peligrad, and E. Rio. Bernstein inequality and moderate deviations under strong mixing conditions. In High dimensional probability V: the Luminy volume , pages 273–292. Institute of Mathematical Statistics, 2009

work page 2009

[42] [42]

Merlev` ede, M

F. Merlev` ede, M. Peligrad, and E. Rio. A Bernstein type inequality and moderate deviations for weakly dependent sequences. Probability Theory and Related Fields , 151(3):435–474, 2011

work page 2011

[43] [43]

N. G. Meyers. An L p-estimate for the gradient of solutions of second order elliptic divergence equations. Annali della Scuola Normale Superiore di Pisa-Classe di Scienze , 17(3):189–206, 1963

work page 1963

[44] [44]

M´ ezard and G

M. M´ ezard and G. Parisi. The Euclidean matching problem. J. Phys. France, 49(12):2019–2025, 1988

work page 2019

[45] [45]

L. I. Nicolaescu. Lectures on the Geometry of Manifolds . World Scientiﬁc, 2020

work page 2020

[46] [46]

R. Peyre. Comparison between W2 distance and ˙H-1 norm, and localization of Wasserstein distance. ESAIM: Control, Optimisation and Calculus of Variations , 24(4):1489–1501, 2018

work page 2018

[47] [47]

A. Riekert. Convergence rates for empirical measures of markov chains in dual and Wasserstein distances. Statistics & Probability Letters , 189:109605, 2022

work page 2022

[48] [48]

Santambrogio

F. Santambrogio. Optimal Transport for Applied Mathematicians: Calculus of Variations, PDEs, and Model- ing. Progress in Nonlinear Diﬀerential Equations and Their Applications. Springer International Publishing, 2015

work page 2015

[49] [49]

G. Sicuro. Euclidean matching problems. In The Euclidean Matching Problem, pages 59–118. Springer, 2017

work page 2017

[50] [50]

J. M. Steele. Probability theory and combinatorial optimization . SIAM, 1997

work page 1997

[51] [51]

E. M. Stein. Topics in harmonic analysis related to the Littlewood-Paley theory.(am-63), volume 63. InTopics in Harmonic Analysis Related to the Littlewood-Paley Theory.(AM-63), Volume 63 . Princeton University Press, 2016

work page 2016

[52] [52]

D. W. Stroock and J. Turetsky. Upper bounds on derivatives of the logarithm of the heat kernel. Communi- cations in Analysis and Geometry , 6(4):669–685, 1998

work page 1998

[53] [53]

Talagrand

M. Talagrand. The Ajtai-Koml´ os-Tusn´ ady matching theorem for general measures. InProbability in Banach Spaces, 8: Proceedings of the Eighth International Conference , pages 39–54. Springer, 1992

work page 1992

[54] [54]

J. A. Toth and S. Zelditch. Riemannian manifolds with uniformly bounded eigenfunctions.Duke Mathematical Journal, 111(1):97–132, 2002

work page 2002

[55] [55]

C. Villani. Topics in optimal transportation, volume 58 of Graduate Studies in Mathematics. American Math- ematical Society, Providence, RI, 2003

work page 2003

[56] [56]

C. Villani. Optimal Transport: Old and New . Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg, 2008

work page 2008

[57] [57]

F.-Y. Wang. Analysis for Diﬀusion Processes on Riemannian Manifolds . WORLD SCIENTIFIC, 2013

work page 2013

[58] [58]

F.-Y. Wang. Convergence in Wasserstein distance for empirical measures of semilinear SPDEs, 2021

work page 2021

[59] [59]

Wang and B

F.-Y. Wang and B. Wu. Wasserstein convergence for empirical measures of subordinated diﬀusions on rie- mannian manifolds, 2021

work page 2021

[60] [60]

Wang and J.-X

F.-Y. Wang and J.-X. Zhu. Limit theorems in Wasserstein distance for empirical measures of diﬀusion pro- cesses on Riemannian manifolds. Annales de l’Institut Henri Poincar´ e, Probabilit´ es et Statistiques, 59(1):437 – 475, 2023. (NICOLAS CLOZEAU) IST AUSTRIA, AUSTRIA Email address: NICOLAS.CLOZEAU@IST.AC.AT (FRANCESCO MATTESINI) UNIVERSIT ¨AT M ¨UNSTER...

work page 2023