Intrinsic Sparsity of Kantorovich solutions

Abstract

Let $X,Y$ be two finite sets of points having $\#X = m$ and $\#Y = n$ points with $\mu = (1/m)(\delta _{x_1} + \dots + \delta _{x_m})$ and $\nu = (1/n) (\delta _{y_1} + \dots + \delta _{y_n})$ being the associated uniform probability measures. A result of Birkhoff implies that if $m = n$, then the Kantorovich problem has a solution which also solves the Monge problem: optimal transport can be realized with a bijection $\pi : X \rightarrow Y$. This is impossible when $m \ne n$. We observe that when $m \ne n$, there exists a solution of the Kantorovich problem such that the mass of each point in $X$ is moved to at most $n/\gcd (m,n)$ different points in $Y$ and that, conversely, each point in $Y$ receives mass from at most $m/\gcd (m,n)$ points in $X$.