Monge solutions and uniqueness in multi-marginal optimal transport via graph theory

We study a multi-marginal optimal transport problem with surplus b(x1, ldots, xm)=sum_i,j∈ P xi· xj, where Psubseteq Q:=i,j: i, j ∈ 1,2,...m, i neq j. We reformulate this problem by associating each surplus of this type with a graph with m vertices whose set of edges is indexed by P. We then establish uniqueness and Monge solution results for two general classes of surplus functions. Among many other examples, these classes encapsulate the Gangbo and 'Swicech surplus [12] and the surplus sumi=1m-1xi· xi+1 + xm· x1 studied in an earlier work by the present authors [23].