Ricci Curvature Formula: Applications to Bonnet-Myers Sharp Irregular Graphs

In Riemannian geometry, the renowned Bonnet–Myers theorem [Mye41] asserts that if the Ricci curvature of a complete Riemannian manifold $M$ is bounded below by $(n-1)\kappa>0$, then its diameter is at most $\frac{\pi}{\sqrt{\kappa}}$. Over the past three decades, there have been numerous efforts to extend the concept of Ricci curvature from Riemannian geometry to a discrete setting. There are different definitions of Ricci curvature defined on graphs, see references [Jos17, CY96, LY10, Oll07]. For instance, Ollivier [Oll09] introduced a notion of Ricci curvature in metric spaces equipped with a measure of a random walk. Lin-Lu-Yau [LLY11] defined a variation of Ollivier-type Ricci curvature on graphs. These notions allow for the generalization of several classical theorems associated with positive Ricci curvature, such as the Lichnerowicz theorem, the Bonnet–Myers theorem, and many others. Numerous properties and implications of the Ollivier Ricci curvature and Lin-Lu-Yau curvature have been explored, see [BCL⁺17, BL12, BM13, Liu14, Smi14], etc. These curvatures has been applied in various research areas such as network analysis[NLLG19, SJB19], quantum computation, dynamic Networks[GHJ⁺16], etc.

In this paper, we consider locally finite graphs, where each vertex has a finite degree, but the total number of vertices may be countably infinite. Let $G=(V,E)$ be a simple locally finite graph with the vertex set $V$ and edge set $E$. (Here “simple” refers to the absence of self-loops and multi-edges.) For any vertex $v\in V(G)$, let $N_{G}(v)$ denote the neighborhood of $v$ in $G$, i.e., $N_{G}(v)=\{u:vu\in E(G)\}$, and let $N_{G}[v]:=N_{G}(v)\cup\{v\}$ denote the closed neighborhood of $v$. The degree of a vertex $v$, denoted by $d_{v}$, is the number of the neighbors of $v$, i.e., $d_{v}=|N_{G}(v)|$. A graph $G$ is called $d$-regular if $d_{v}=d$ for any vertex $v$. We call $G$ irregular if it is not regular. For $S\subseteq V(G)$, $N_{G}(S)=\{u\in V(G)\setminus S:us\in E(G)\textrm{ for some }s\in S\}$. When $G$ is clear under context, we will omit the subscript $G$ in the notation.

A $uv$-walk $P$ is a sequence of vertices $u=u_{0},u_{1},\ldots,u_{k}=v$ such that $u_{i}$ and $u_{i+1}$ are adjacent for $i=0,\ldots,k-1$. Sometime we write $uPv$ to indicate the walk is from $u$ to $v$. Given two walks $uP_{1}v$ and $vP_{2}w$, the concatenation of two walk is a new walk, written by $uP_{1}vP_{2}w$, that walks from $u$ to $v$ via $P_{1}$ and then continues from $v$ to $w$ via $P_{2}$. A walk $P$ is called $uv$-path if all internal vertices are distinct. A walk is called closed if $u=v$. A cycle is a closed walk so that all internal vertices are distinct. We say $G$ is connected if for any pair of vertices $u$ and $v$, there is a path (or walk) $uPv$.

For any two vertices $u,v\in V(G)$, the distance from $u$ to $v$ in $G$, denoted by $d_{G}(u,v)$, is the number of edges of a shortest path from $u$ to $v$ in $G$. The diameter of a graph $G$ is defined to be $diam(G)=\sup\{d_{G}(u,v):u,v\in V(G)\}$.

A mass distribution $m$ (over the vertex set $V=V(G)$) is a mapping $m:V\to[0,\infty)$. The total mass of $m$ is the $L_{1}$ norm, $\|m\|_{1}=\sum_{v\in V}m(v)$. A probability distribution is a mass distribution with total mass equal to 1.

Let $m_{1}$ and $m_{2}$ be two mass distributions on $V$ with equal total masses. A coupling between $m_{1}$ and $m_{2}$ is a mapping $A:V\times V\to[0,1]$ such that

$$\displaystyle\sum_{y\in V}A(x,y)=m_{1}(x)\textrm{ and }\displaystyle\sum_{x\in V}A(x,y)=m_{2}(y).$$

(1)

The cost of $A$, denoted by $C(A)$, is given by

$$C(A)=\sum_{u,v}A(u,v)d(u,v).$$

(2)

The transportation distance between the two probability distributions $m_{1}$ and $m_{2}$ is defined as follows:

$$W(m_{1},m_{2})=\inf_{A}C(A),$$

(3)

where the infimum is taken over all coupling $A$ between $m_{1}$ and $m_{2}$. By the duality theorem of a linear optimization problem, the transportation distance can also be expressed as follows:

$$W(m_{1},m_{2})=\sup_{f}\displaystyle\sum_{x\in V}f(x)\left(m_{1}(x)-m_{2}(x)\right),$$

(4)

where the supremum is taken over all $1$-Lipschitz functions $f$.

A random walk $m$ on $G=(V,E)$ is defined as a family of probability measures $\{m_{v}(\cdot)\}_{v\in V}$ such that $m_{v}(u)=\frac{1}{d_{v}}$ for any $u\in N(v)$ and $0$ otherwise. The Ricci curvature $\kappa:\binom{V(G)}{2}\to\mathbb{R}$ of $G$ can then be defined as follows:

For $0\leq\alpha<1$, the $\alpha$-lazy random walk $m_{x}^{\alpha}$ (for any vertex $x$), is defined as

$$m_{x}^{\alpha}(v)=\begin{cases}\alpha&\textrm{ if $v=x$,}\\ (1-\alpha)/d_{x}&\textrm{ if $v\in N(x)$,}\\ 0&\textrm{ otherwise.}\end{cases}$$

In [LLY11], Lin, Lu, and Yau defined the Ricci curvature of graphs based on the $\alpha$-lazy random walk as $\alpha$ goes to $1$. More precisely, for any $x,y\in V$, they defined the $\alpha$-Ricci-curvature $\kappa_{\alpha}(x,y)$ to be

$$\kappa_{\alpha}(x,y)=1-\frac{W(m_{x}^{\alpha},m_{y}^{\alpha})}{d(x,y)}$$

and the Lin-Lu-Yau Ricci curvature $\kappa_{\textrm{LLY}}$ of $G$ to be

$$\kappa_{\textrm{LLY}}(x,y)=\displaystyle\lim_{\alpha\to 1}\frac{\kappa_{\alpha}(x,y)}{(1-\alpha)}.$$

This limit always exists since $\kappa_{\alpha}$ is concave in $\alpha\in[0,1]$ for any two vertices $x,y$ (see [LLY11]).

The parameter $\alpha$ is called the idleness of the random walk. When $\alpha=0$, $m_{x}^{\alpha}$ becomes classical random walk. The curvature $\kappa_{0}$ is Ollivier’s original definition of Ricci curvature on graphs (see [Oll09]). It has been shown in [LLY11] that

$$\kappa_{LLY}(x,y)\geq\kappa_{0}(x,y)$$

(5)

for any pair of vertices $x,y$.

In this paper, we only consider the Lin-Lu-Yau curvature and simply write $\kappa_{LLY}(x,y)$ as $\kappa(x,y)$ for the rest of the paper. Although the Ricci curvature $\kappa(x,y)$ is defined for all pairs $x,y\in V(G)$, it suffices to consider only $\kappa(x,y)$ for $xy\in E(G)$ due to the following lemma.

Bourne-Cushing-Liu-Münch-Pyerimhoff proved [BCL⁺18] the following result:

Their result implies

$$\kappa(x,y)=\frac{1}{(1-\alpha)}\kappa_{\alpha},\hskip 28.45274pt\mbox{ for }\alpha\in\left[\frac{1}{\max\{d_{x},d_{y}\}+1},1\right).$$

(6)

Münch and Wojciechowski [MW19] gave another limit-free formulation of the Lin-Lu-Yau Ricci curvature using graph Laplacian. For a graph $G=(V,E)$, the (negative) combinatorial graph Laplacian $\Delta$ is defined as:

$$\Delta f(x)=\frac{1}{d_{x}}\sum\limits_{y\in N(x)}(f(y)-f(x)).$$

It was also proved (see [MW19, BCL⁺17, CK19]) that the optimal solution $f$ in (7) can be chosen to be an integer-valued function.

Bai, Huang, Lu, and Yau prove a dual theorem for a limit-free definition for the Lin-Lu-Yau Ricci curvature. For any two vertices $x$ and $y$, a $\ast$-coupling between $m^{0}_{x}$ and $m^{0}_{y}$ is a mapping $B:V\times V\to\mathbb{R}$ with finite support such that

1. 1.

   $0<B(x,y)$, but all other values $B(u,v)\leq 0$.

2. 2.

   $\sum\limits_{u,v\in V}B(u,v)=0$.

3. 3.

   $\sum\limits_{v\in V}B(u,v)=-m^{0}_{x}(u)$ for all $u$ except $x$.

4. 4.

   $\sum\limits_{u\in V}B(u,v)=-m^{0}_{y}(v)$ for all $v$ except $y$.

In this paper, we will derive a straightforward formula to calculate $\kappa(x,y)$ for any edge $xy\in E(G)$. We use the following notation. Let ${\rm lcm}(d_{x},d_{y})$ denote the least common multiplier of $d_{x}$ and $d_{y}$. Let $c_{x}$ and $c_{y}$ are a pair of relative prime integers such that

$${\rm lcm}(d_{x},d_{y})=c_{x}d_{x}=c_{y}d_{y}.$$

Without loss of generality, we assume $d_{x}\leq d_{y}$. Equivalently, we have $c_{x}\geq c_{y}$. Let $\mu_{x}$ be a mass distribution defined as

$$\mu_{x}(u)=\begin{cases}c_{x}-c_{y}&\mbox{ if }u\in N(x)\cap N[y],\\ c_{x}&\mbox{ if }u\in N(x)\backslash N[y],\\ 0&\mbox{otherwise.}\end{cases}$$

Let $\mu_{y}$ be a mass distribution defined as

$$\mu_{y}(u)=\begin{cases}c_{y}&\mbox{ if }u\in N(y)\backslash N[x],\\ 0&\mbox{otherwise.}\end{cases}$$

For any coupling $\sigma$ between $\mu_{x}$ and $\mu_{y}$, recall the cost function $C(\sigma)$ is

$$C(\sigma)=\sum_{u,v}\sigma(u,v)d(u,v).$$

(9)

In the expression of the cost function $C(\sigma)$ above, it suffices to sum up only for $u\in N(x)$ and $v\in N(y)\setminus N[x]$ because $\sigma(u,v)=0$ if $(u,v)\not\in N(x)\times(N(y)\setminus N[x])$.

We have the following theorem.

For example, consider the following graph in Figure 1. We have $d_{x}=3$ and $d_{y}=4$. Thus, ${\rm lcm}(d_{x},d_{y})=12$, $c_{x}=4$, and $c_{y}=3$. The mass distribution $\mu_{x}$ is labelled in red color while $\mu_{y}$ is labelled in black color. Any coupling between $\mu_{x}$ and $\mu_{y}$ has a cost of at least $14$ since transferring $4$ units from $x_{1}$ to $y_{1}$ or $y_{2}$ costs at least $4\times 3=12$ and moving other two units has the cost of at least $2$. Clearly, an optimal coupling with cost $14$ exists. For example, one can transfer one unit from $z$ to $y_{1}$, one unit from $y$ to $y_{2}$, two units from $x_{1}$ to $y_{1}$, and two units from $x_{1}$ to $y_{2}$. So we have

$$\min_{\sigma}C(\sigma)=14.$$

By Theorem 4, we get

$$\kappa(x,y)=1+\frac{1}{4}-\frac{14}{12}=\frac{1}{12}.$$

The integer-valued coupling can be viewed as a bijection between the blowup of $N(x)$ and $N(y)\setminus N[x]$. More discussions will be given in Section 3. It is useful for understanding the structural meaning of Ricci curvature $\kappa(x,y)$. The special case of $d_{x}=d_{y}$ was considered by Bai and Lei [LB22]. They derived a formula using the number of (almost)-disjoint $C_{3}$, $C_{4}$, and $C_{5}$ containing both $x$ and $y$. The formula can be shown to equivalent to Equation (10).

Lin, Lu, and Yau [LLY11] and Ollivier [Oll09] proved the Bonnet-Myers type Theorem on Graphs:

Let $\kappa_{min}(G)=\min_{xy\in E(G)}\kappa(x,y)$. We say a connected graph $G$ is Bonnet-Myers sharp if $diam(G)=\frac{2}{\kappa_{min}}$. A pair of vertices $(x,y)$ in an Bonnet-Myers sharp graph is called poles if $d(x,y)=diam(G)$. In this case, we call $x$ (and $y$) is a pole.

Cushing-Kamtue-Koolen-Liu-Münch-Peyerimhoff[CKK⁺20] studied Bonnet-Myers sharp regular graphs. They called a graph $G$ is (D,L)-Bonnet-Myers sharp if $G$ is $D$-regular, $diam(G)=L$, and is Bonnet-Myers sharp. A graph $G=(V,E)$ is called self-centered if, for every vertex $x\in V$, there exists a vertex $\overline{x}\in V$ such that $d(x,\overline{x})={\rm diam}(G)$. Here is their main result.

Kamtue proved that a $(D,3)$-Bonnet-Myers sharp graph is automatically self-centered (see [Kam20]). Thus, the condition of being self-centered in Theorem 5 can be removed for graphs with diameter $3$.

Most known results assume that $G$ is $D$-regular. The smallest irregular and not-self-centered Bonnet-Myers sharp graph is $P_{3}$. We have $\kappa_{min}(P_{3})=1$ and diameter $L=2$.

In this paper, we will omit the conditions of being regular and self-centered. To the best of our knowledge, there is only one other paper that has studied Bonnet-Myers sharp irregular graphs, providing a classification for those with a diameter of $2$ and some necessary conditions for anti-trees being Bonnet-Myers sharp (see [CS24]). They showed that a graph $G$ is a diameter $2$ Bonnet-Myers sharp graph if and only if $G$ is a complete graph with a matching removed.

The case for diameter 3 (of irregular Bonnet-Myers sharp graphs) remains entirely unexplored. In this paper, we establish the following structural theorem.

We have constructed an infinite number of Bonnet-Myers sharp irregular graphs with a diameter of 3. Specifically, there exists a Bonnet-Myers sharp graph of diameter $3$ for $t=1,2$ and all $r\geq 1$. (We suspect that $t$ is limited to a few specific values. Determining all possible pairs of $(r,t)$ appears to be a challenging problem). On the contrast, there are only four Bonnet-Myers sharp regular graphs of diameter $3$: the hypercube $Q_{3}$, the Johnson graph $J(6,3)$, the demi-cubes $Q_{6}^{(2)}$, and the Gosset graph.

We additionally prove the following result concerning $C_{3}$-free Bonnet-Myers sharp graphs.

When $d_{x}\leq\frac{2}{3}L$, Bonnet-Myers sharp irregular graphs may exist. See examples in Table 6.

The remainder of the paper is organized as follows: In Section 2, we establish a theorem on the existence of integer-valued optimal couplings and a lemma on complementary slackness. In Section 3, we present the proof of Theorem 4. Section 4 is dedicated to proving several lemmas for Bonnet-Myers sharp graphs. In Section 5, we prove Theorem 6 and also construct many diameter 3 Bonnet-Myers-sharp irregular graphs. Finally, in the last section, we examine the $C_{3}$-free Bonnet-Myers-sharp graphs.

A mass distribution (over the vertex set $V=V(G)$) is a mapping $m:V\to[0,\infty)$. The total mass of $m$ is $\|m\|_{1}=\sum_{v\in V}m(v)$. A probability distribution can be viewed as a mass distribution with a total mass of 1. The concepts of coupling (Equation (1)) and transportation distance (Equations (3) and (4)) can be easily extended to two mass distributions with equal total mass.

For any positive constant $c$, let $cm$ (or $cA$) be the distribution (or coupling) scaled by a factor of $c$. It is straightforward to verify

$$W(cm_{1},cm_{2})=cW(m_{1},m_{2})$$

(12)

We first prove a lemma on the existence of integer-valued optimal coupling.

Note that Equations (7) and (8) are dual to each other. We have the following lemma, which is the special case of the complementary slackness theorem in the linear programming.