Combinatorial Problems Related to Optimal Transport and Parking Functions

Mr. Jan Kretschmann
University of Wisconsin-Milwaukee
Dissertator

In the first part, we show 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 the sum of width-one matrices. We give different formulas using the theory of abstract simplicial complexes as well as Young tableaux. We apply this result to compute the EMD under different cost matrices. Furthermore, we generalize our result to higher dimensions, making use of multiset Eulerian polynomials.
In the second part, we highlight work related to parking functions. We state prerequisites and show a connection to the first part of this work through certain statistics used in the shuffle conjecture. Additionally, we provide enumerative formulas for generalizations and restrictions of parking functions, allowing cars to have varying lengths and showing a connection to the Quicksort algorithm. Finally, we will use parking objects to enumerate Boolean algebras in the Bruhat order.

Advisor: Profs. Jeb Willenbring and Pamela Harris

Committee Members:
Profs. Jeb Willenbring, Pamela Harris, Allen Bell, David Spade, and Richard Stockbridge