Optimal transport meets graph spectra

papers [2, 3, 1]. We explain, in the setting of discrete spaces, the definition of optimal transport distance, its dual formula, exact formula for one-dimensional measures, its relation to linear programming and various interactions with graph spectra. Remark 1. I will not pursue to give strictly mathematical proofs, but instead try to explain what’s going on with a formula and the underlying intuitions. 1. Basics about optimal transport problem on discrete spaces Let’s start from a simple (even naive) transport problem. x factory or production unit y shop or consumption place Suppose you are the manager who are thinking of transport products from the factory x to a shop y. x can be a bakery producing breads, y can be a cafe ́ shop. The amount of products at x, denoted by µx equals to the amount needed at y, denoted by ν(y). That is µ(x) = ν(y). (1.1) Then it makes no difference in mathematics to normalize both quantities to be 1 unit. That is, we can suppose µ(x) = ν(y) = 1. (1.2