Scaling hypothesis for the Euclidean bipartite matching problem. II. Correlation functions

We analyze the random Euclidean bipartite matching problem on the hypertorus in $d$ dimensions with quadratic cost and we derive the two-point correlation function for the optimal matching, using a proper ansatz introduced by Caracciolo et al. [Phys. Rev. E 90, 012118 (2014)] to evaluate the average optimal matching cost. We consider both the grid-Poisson matching problem and the Poisson-Poisson matching problem. We also show that the correlation function is strictly related to the Green's function of the Laplace operator on the hypertorus.

Figure 1

gP Euclidean bipartite matching with $N=225$ and $p=2$ on the torus.

Figure 2

Theoretical predictions for the correlation functions $C_2\left(\mathbf{x}\right)$ and $c_2\left(\mathbf{x}\right)$ for the Euclidean bipartite matching problem in two dimensions and numerical results. Numerical results for the wall-to-wall correlation functions and corresponding theoretical predictions are also presented. (a) Section $C_2(r_1,0)$ and $C_2^{\text{g}\text{P}}(r_1,0)$ of the correlation function both in the PP case for $N={10}^4$ and in the gP case for $N=3600$ and corresponding theoretical predictions. (b) Section $c_2(r_1,0)$ for $N={10}^4$ and $c_2^{\text{g}\text{P}}(r_1,0)$ for $N=3600$ of the correlation function and theoretical predictions, Eqs. (44) and (46): Note that the theoretical curves overlap. (c) Rescaled wall-to-wall correlation function in two dimensions for the PP matching problem with $N=3600$ on the unit flat torus. The continuous line corresponds to the analytical prediction. (d) Rescaled wall-to-wall correlation function in two dimensions for the gP matching problem with $N=3600$ on the unit flat torus. The continuous line corresponds to the analytical prediction.

Figure 3

Wall-to-wall correlation function in three dimensions for the gP matching problem with $d=3$ and $N=9261$ on the unit flat hypertorus.