On the sum of Ricci-curvatures for weighted graphs

In this paper, we generalize Lin–Lu–Yau’s Ricci curvature to weighted graphs and give a simple limit-free definition. We prove two extremal results on the sum of Ricci curvatures for weighted graph. A weighted graph $G=(V,E,d)$ is an undirected graph $G=(V,E)$ associated with a distance function $d: E \to [ 0,\infty)$. By redefining the weights if possible, without loss of generality, we assume that the shortest weighted distance between $u$ and $v$ is exactly $d(u, v)$ for any edge $uv$. Now consider a random walk whose transitive probability from an vertex $u$ to its neighbor $v$ (a jump move along the edge uv) is proportional to $w_{uv} := F(d(u, v))/d(u, v)$ for some given function $F(\bullet)$. We first generalize Lin–Lu–Yau’s Ricci curvature definition to this weighted graph and give a simple limit-free representation of $\kappa(x, y)$ using a so called $\ast$-coupling functions. The total curvature $K(G)$ is defined to be the sum of Ricci curvatures over all edges of $G$. We proved the following theorems: if $F(\bullet)$ is a decreasing function, then $K(G) \geq 2 \lvert V \rvert - 2 \lvert E \rvert$; if $F(\bullet)$ is an increasing function, then $K(G) \leq 2 \lvert V \rvert - 2 \lvert E \rvert$. Both equations hold if and only if $d$ is a constant function plus the girth is at least $6$.

In particular, these imply a Gauss–Bonnet theorem for (unweighted) graphs with girth at least $6$, where the graph Ricci curvature is defined geometrically in terms of optimal transport.

Full Text (PDF format)

The fourth-named author was supported in part by NSF grant DMS-1737873.

Received 16 April 2020

Accepted 19 June 2020

Published 26 January 2022