Scaling hypothesis for the Euclidean bipartite matching problem

We propose a simple yet very predictive form, based on a Poisson's equation, for the functional dependence of the cost from the density of points in the Euclidean bipartite matching problem. This leads, for quadratic costs, to the analytic prediction of the large $N$ limit of the average cost in dimension $d=1,2$ and of the subleading correction in higher dimension. A nontrivial scaling exponent, ${\gamma }_d=\frac{d-2}{d}$, which differs from the monopartite's one, is found for the subleading correction. We argue that the same scaling holds true for a generic cost exponent in dimension $d>2$.

Figure 1

Numerical simulations for $d=1$; the fit was performed using the three-parameter fit function $f_1^{\left(2\right)}\left(N\right)={\alpha }_1^{\left(2\right)}+\frac{e_1^{\left(2\right)}}{N}+\frac{c}{N^2}$.

Figure 2

Numerical simulations for $d=2$. We fitted our numerical data for ${\beta }_N^{\left(2\right)}\left(2\right)$ using the function $f_2^{\left(2\right)}\left(N\right)=alnN+e_2^{\left(2\right)}+\frac{b}{lnN}$. The $\frac{1}{lnN}$ correction was suggested by the right-hand plot.

Figure 3

Numerical simulations for $d>2$. We fitted our numerical data for ${\beta }_N^{\left(2\right)}\left(d\right)$ using the function $f_d^{\left(2\right)}\left(N\right)=e_d^{\left(2\right)}+{\alpha }_d^{\left(2\right)}{N}^{-{\gamma }_d}+\frac{c}{N}$. The expected value for ${\alpha }_d^{\left(2\right)}$ was $\frac{1}{2{\pi }^2}{\zeta }_d\left(1\right)$.

Figure 4

Numerical simulations for $d>2$. We fitted our numerical data for ${\beta }_N^{\left(p\right)}\left(d\right)$ using the function $f_d^{\left(p\right)}\left(N\right)=e_d^{\left(p\right)}+{\alpha }_d^{\left(p\right)}{N}^{-{\gamma }_d}+\frac{c}{N}$. We plotted the results obtained for $p=1,3,4$. Fit results are presented in Table 2.