Abstract: Square N by N matrices with non-negative entries whose columns and rows all sum to one form a convex set with N! vertices. Each vertex corresponds to a permutation on N letters, according to a theorem of Birkhoff and von Neumann.
In 1948 Birkhoff asked what the infinite dimensional analog of this theorem should be. We resolve this problem, by giving a condition on the support of a measure on the square which characterizes extremality among non-negative measures with the same x- and y-marginal projections. Our condition is used to derive a new sufficient condition for uniqueness of minimizer in Kantorovich's optimal transportation problem, in terms of the topology of the transportation cost.