Topology and Information in Regularized Transport on Graphs
Abstract
We study how two geometries of mass on a finite graph interact: the information geometry of the generalized entropy Fq used for regularized transport, and the arithmetic of divisors governed by the Riemann--Roch theorem of Baker and Norine and by the Jacobian. Because the correction term of Fq is affine, Fq-regularization at strength γ is Tsallis regularization at temperature γ/q. Over the reals, chip-firing connects all configurations of equal degree, so the Jacobian enters transport only through integrality. We introduce the transport defect, the worst-case cost of steering d chips towards a target by chip-firing, and prove 1/d≤δTV(D)≤(d−r(D))/d=(g−1−r(K−D))/d≤min(1,g/d) whenever g≥1; vertex multiplicities give a lower bound and an equality criterion. A regularized topological gap Γq,γ(D,E) tends to the chip-move defect as γ→0, lies in an explicit window, has a high-temperature slope given by Tsallis coupling entropies, and admits a positive regime if and only if g≥1. Dual potentials certify exactly the convex relaxation of a linear system; the remainder is an integrality gap. Zeros in optimal plans occur only for q>1, by a mechanism different from the sign change of Γ. Exact computations on $1784$ divisor classes find the rank bound $(d-r(D))/d$ attained in $1769$ of them, an observed frequency. Experiments on honeycomb and Erdős--Rényi networks with 102 to 105 nodes test the statements on regularized plans, not Γ; over 103≤ n≤105 their transport costs are consistent with growth like n1/2 and log n, respectively.
Related
- A Distributed Accelerated Preconditioned ADMM for Solving Quadratically Regularized Optimal Transport on Bipartite Graphs
- Sparsity of Quadratically Regularized Optimal Transport: Scalar Case
- Entropy-Regularized Optimal Transport for Time-Varying Multi-Agent Coverage Control
- Accelerating Sinkhorn for Entropy-Regularized Optimal Transport
- Geometry and Convergence of Quadratically Regularized Optimal Transport I
BibTeX
@misc{yoshizawa2026topology,
title = {{Topology and Information in Regularized Transport on Graphs}},
author = {Shintaro Yoshizawa},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.09968},
eprint = {2611.09968},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.09968},
}
RIS
TY - UNPB
TI - Topology and Information in Regularized Transport on Graphs
AU - Shintaro Yoshizawa
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.09968
UR - https://arxiv.org/abs/2611.09968
AB - We study how two geometries of mass on a finite graph interact: the information geometry of the generalized entropy F_q used for regularized transport, and the arithmetic of divisors governed by the Riemann--Roch theorem of Baker and Norine and by the Jacobian. Because the correction term of F_q is affine, F_q-regularization at strength γ is Tsallis regularization at temperature γ/q. Over the reals, chip-firing connects all configurations of equal degree, so the Jacobian enters transport only through integrality. We introduce the transport defect, the worst-case cost of steering d chips towards a target by chip-firing, and prove 1/d≤δ_TV(D)≤(d−r(D))/d=(g−1−r(K−D))/d≤min(1,g/d) whenever g≥1; vertex multiplicities give a lower bound and an equality criterion. A regularized topological gap Γ_q,γ(D,E) tends to the chip-move defect as γ→0, lies in an explicit window, has a high-temperature slope given by Tsallis coupling entropies, and admits a positive regime if and only if g≥1. Dual potentials certify exactly the convex relaxation of a linear system; the remainder is an integrality gap. Zeros in optimal plans occur only for q>1, by a mechanism different from the sign change of Γ. Exact computations on $1784$ divisor classes find the rank bound $(d-r(D))/d$ attained in $1769$ of them, an observed frequency. Experiments on honeycomb and Erdős--Rényi networks with 10^2 to 10^5 nodes test the statements on regularized plans, not Γ; over 10^3≤ n≤10^5 their transport costs are consistent with growth like n^1/2 and log n, respectively.
ER -