Combinatorial problems related to optimal transport and parking functions

Abstract

In the first part of this work, we provide contributions to optimal transport through work on the discrete Earth Mover's Distance (EMD).We provide a new formula for the mean EMD by computing three different formulas for the sum of width-one matrices: the first two formulas apply the theory of abstract simplicial complexes and result from a shelling of the order complex, whereas the last formula uses Young tableaux. Subsequently, we employ this result to compute the EMD under different cost matrices satisfying the Monge property. Additionally, we use linear programming to compute the EMD under non-Monge cost matrices, giving an interpretation of the EMD as a distance measure on pie charts. Furthermore, we generalize our result to the $n$-dimensional EMD, by providing two different formulas for the sum of width--one tensors: once approaching the problem from the perspective of Young tableaux and once through the theory of abstract simplicial complexes by shelling of the $n$-dimensional order complex. In the second part, we provide contributions to the topic of parking functions.We provide background on the topic and show a connection to the first part of this work through certain statistics on parking functions used in the shuffle conjecture. Furthermore, we provide enumerative formulas for different generalizations of parking functions, allowing cars to have varying lengths. Additionally, we show a surprising connection between certain restricted parking objects and the Quicksort algorithm. At last, we will use the intersection of a subset of parking functions and Fubini rankings to characterize and enumerate Boolean algebras in the weak Bruhat order of $S_n$.