On the transportation cost norm on finite metric graphs

Georges SKANDALIS, Alain VALETTE · 2026

Read On the transportation cost norm on finite metric graphs by Georges SKANDALIS, Alain VALETTE (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-16859.txt.

Introduction

Georges Skandalis and Alain Valette weigh the cost of moving mass on a graph. Their graph is a net of points joined by set-length paths. The cost norm gauges the least work to shift loads. Loads sit at points, and paths bear the moves. Their 2026 preprint sets out traits of that norm for fin graphs.

Shortest-path gaps set the space for their math. The team ties the cost norm to the graph's shape. Such ties help in chip layout and net design. They also feed pure work on normed spaces. Small graphs here stand in for big real nets.

Catalog record

CREATORGeorges SKANDALIS, Alain VALETTE
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE28 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-16859

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the transportation cost norm on finite metric graphs Georges SKANDALIS, Alain VALETTE Abstract For a finite metric graph X = ( V , E , ℓ ) X=(V,E,\ell) , where V V is endowed with the shortest path metric, we consider the transportation cost problem associated with the distance d d on V V . Namely, for f f a function with total sum 0 on V V , write f = ∑ a , b ∈ V P ⁡ ( a , b ) ​ ( δ a − δ b ) f=\sum_{a,b\in V}P(a,b)(\delta_{a}-\delta_{b}) where the transportation plan P P satisfies P ⁡ ( a , b ) ≥ 0 P(a,b)\geq 0 for ( a , b ) ∈ V × V (a,b)\in V\times V . The cost of P P is W ⁡ ( P ) := ∑ a , b ∈ V P ⁡ ( a , b ) ​ d ​ ( a , b ) W(P):=\sum_{a,b\in V}P(a,b)d(a,b) and the transportation norm of f f is ‖ f ‖ T ​ C = min P ⁡ W ⁡ ( P ) \|f\|_{TC}=\min_{P}W(P) where P P runs over all transportation plans for f f . In this semi-survey paper, we give short proofs for the following statements: • There always exists an optimal transportation plan supported in V + × V − V_{+}\times V_{-} where V + = { x ∈ V : f ⁡ ( x ) > 0 } V_{+}=\{x\in V:f(x)>0\} and V − = { x ∈ V : f ⁡ ( x ) < 0 } V_{-}=\{x\in V:f(x)<0\} . If X X is a metric tree, we may moreover assume that this plan involves at most | S ​ u ​ p ​ p ​ ( f ) | − 1 |Supp(f)|-1 transports. • There always exists an optimal transportation plan supported in the set of edges of X X . • Better, there always exists an optimal transportation plan supported in some spanning tree of X X . We use this to reprove known formulae for the transportation norm when X X is either a tree or a cycle. 1 Introduction Let (X,d) be a finite metric space. The transportation cost space of X (also known as Arens-Eells space, Kantorovich-Rubinstein space, or Lipschitz free space 1 1 1 See Definition 1.1 in [ GK03 ] , or Chapter 3 in [ We18 ] ; for historical background see the remarks in section 10.1 of [ Os13 ] and section 1.6 in [ OO19 ] . ) is the space \mathcal{F}(X) of real-valued functions f on X with total mass 0, endowed with a norm defined as follows. For such an f , set \Pi_{f}=\{P:X\times X\rightarrow\mathbb{R}_{\geq 0}:\;f=\sum_{a,b\in X}P(a,b)(\delta_{a}-\delta_{b})\}, where \delta_{x} denotes the Dirac mass at x . Equivalenty P\in\Pi_{f} if and only if f(x)=\sum_{a\in X}(P(x,a)-P(a,x)) for all x\in X . It is clear that \Pi_{f} is non-empty, and does not depend on d . Put also X_{+}=\{a\in V;\ f(a)>0\} and X_{-}=\{a\in V;\ f(a)<0\} and let also \widetilde{\Pi}_{f}=\{P\in\Pi_{f};\ \mathrm{supp}(P)\subset X_{+}\times X_{-}\}. It is clear that \widetilde{\Pi}_{f} is also non-empty. The elements of \Pi_{f} are transportation plans for f and those of \widetilde{\Pi}_{f} are simultaneous transportation plans. We take d into account by defining the cost of P\in\Pi_{f} as: W_{X}(P)=\sum_{a,b\in X}P(a,b)d(a,b). Now define the transportation cost norm of f as \|f\|_{TC(X)}=\min\{W(P):P\in\Pi_{f}\}. and the simultaneous transportation cost norm of f as \|f\|_{STC(X)}=\min\{W(P):P\in\widetilde{\Pi}_{f}\}. Let P_{0}\in\Pi_{f} . The set \{P\in\Pi_{f};\ W(P)\leq W(P_{0})\} is compact, and therefore the infimum is a minimum. When the metric space X is clear from context we drop the subscript, both in W(P) and in \|f\|_{TC} . We recall the optimal transportation interpretation of \|f\|_{TC} : suppose that a mass f(x) is available at points x\in X where f(x)>0 , and a mass -f(y) is in demand at points y\in X with f(y)<0 . An element P\in\Pi_{f} can be viewed as a transportation plan , i.e. a way of transporting the mass from points where it is in excess to the points where it is in demand, W(P) represents the physical work associated with this transportation plan, and \|f\|_{TC} represents the most economical transportation associated with f . The following result is due to Bergman (Proposition 24 in [ Be08 ] ) with a short proof in Proposition 3.16 of [ We18 ] . We will give a new proof in Section 2. Theorem 1.1 . Given any finite metric space (X,d) and any f\in TC(X) , we have \|f\|_{TC}=\|f\|_{STC} . Next we deal with X=(V,E,\ell) a finite, connected, metric graph. This means that (V,E) is a simple connected graph with no loop, \ell:E\rightarrow\mathbb{R}_{>0} is a function giving a positive length to every edge, and V becomes a finite metric space with the shortest path metric. We define two more transportation cost norms on \mathcal{F}(V) associated with the graph structure. • Let \sim denote the adjacency relation on V , so that x\sim y if and only if \{x,y\}\in E . Let \Pi_{f,E} denote the set of transportation plans supported in the graph of \sim in V\times V . This corresponds to transports supported on the edges of X . We denote by \|f\|_{TCE} the corresponding norm. • Recall that a spanning tree in X is a subtree of X passing through all vertices. We denote by \Pi_{f,T} the set of transportation plans P\in\Pi_{f} for which there exists a spanning tree T such that P is supported on the edges of T . We denote by \|f\|_{TCT} the corresponding norm. Assume that X is endowed with an orientation, i.e. every edge e\in E has an origin e_{-} end an extremity e_{+} . This allows to define the boundary operator \partial:\mathbb{R}^{E}\rightarrow\mathbb{R}^{V}:\delta_{e}\mapsto\delta_{e_{+}}-\delta_{e_{-}} ; equivalently (\partial\phi)(v)=\sum_{e:e_{+}=v}\phi(e)-\sum_{e:e_{-}=v}\phi(e) (1) ( v\in V,\phi\in\mathbb{R}^{E} ). It is classical that the image of \partial is exactly the space \mathcal{F}(V) , so that the rank of \partial is |V|-1 ; and that the kernel of \partial is the space Z(X) of cycles of X , so that \dim(Z(X))=|E|-|V|+1 (see Proposition 4.3 and Theorem 4.5 in [ Bi93 ] ). Then: Theorem 1.2 . 1. For f\in\mathcal{F}(V) we have: \|f\|_{TC}=\|f\|_{TCE}=\|f\|_{TCT}. 2. The operator \partial:\mathbb{R}^{E}\rightarrow\mathbb{R}^{V} induces an isometric isomorphism from the quotient space \ell^{1}(E,\ell)/Z(X) onto TC(V) . \blacksquare The first equality in the first part is proved after Remark 1.3 in [ OO22 ] ; the 2nd equality might be new. The latter corresponds to the intuitive idea that, if a transportation plan involves loops in the graph, it is possible to avoid the loops without increasing the cost. For the second part, see Proposition 10.10 in [ Os13 ] for usual graphs, and Theorem 3.1 in [ OO20 ] or Proposition 1.5 in [ OO22 ] for the general case; note that that the proofs in [ Os13 ] and [ OO20 ] are indirect, establishing that the transpose operator \partial^{t}:(\mathcal{F}(V))^{*}\rightarrow(\ell^{1}(E,\ell)/Z(X))^{*} , is an isometric isomorphism. A short direct proof of Theorem 1.2 will be given in Section 3. Section 4 will be devoted to 3 corollaries of Theorem 1.2 . • Due to the presence of a minimum either in the original definition of \|f\|_{TCE} , or as a quotient norm in Theorem 1.2 , for a general metric graph we don’t

Read the complete text