{"id":"arxiv/2608.14839","url":"https://arxiv.org/abs/2608.14839","tags":["math.CO"],"score":0,"title":"Optimal Transport on Graphs and Stochastically Evolving Trees","domain":"math.CO","source":"arxiv","authors":["Fan Chung","Sawyer Jack Robertson"],"reviews":0,"subject":"math.CO","summary":"We give an effective algorithm for determining the transportation distance between two given probability density functions defined on the vertices of a graph $G=(V,E)$ by analyzing an associated polytope. The vertices of the polytope correspond to feasible flows on spanning trees in $G$, and the $1$-skeleton of the polytope is a projection of the spanning tree state graph associated with the Glauber dynamics on $G$. The optimal value of this transportation problem, known as the $1$-Wasserstein distance, can be computed by tracing the transportation cost along the vertices of this polytope.…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-14","reactions":{}}