具有常数正Ricci曲率的图

Graphs with Constant Positive Ricci Curvature

摘要: 本文在Lin-Lu-Yau给出的图的Ricci曲率的定义下，刻画了一类具有常数正Ricci曲率的图。更进一步地，本文找到了图上每条边的Ricci曲率都不小于1的充分必要条件，并刻画了图上每条边的Ricci曲率都等于1的图。

Abstract: In this paper, we study the Ricci curvature given by Lin-Lu-Yau and characterize several graphs with constant positive Ricci curvature. We find the necessary and sufficient condition when every edge of the graph has Ricci curvature no less than one and characterize the graphs in which the Ricci curvature of every edge is equal to one.

1. 引言

1.1. 研究背景

Ricci曲率是几何分析中的一个基本概念，Bakry和Emery [1] 首先利用热半群的概念在度量空间上定义了Ricci曲率。随后，许多学者考虑将Ricci曲率的概念推广到包括图在内的其他形式的度量空间中。1996年，Fan Chung和Yau [2] 在得到一个良好的log-Sobolev不等式的过程中首次定义了图上Ricci曲率。后来，Lin和Yau [3] 在图的框架中推广了Bakry和Emery定义下的Ricci曲率的定义。2009年，Ollivier [4] 在包括图在内的任意度量空间上引入了有效的马尔科夫链的粗糙Ricci曲率的概念。2011年Lin，Lu和Yau [5] 将Ollivier提出的Ricci曲率的定义修改为一个极限的形式，与Ollivier定义下的Ricci曲率略有不同。

本文在Lin-Lu-Yau给出的Ricci曲率的定义下，对几种具有恒定正Ricci曲率的图进行刻画。

1.2. 定义

设 $G=\left(V,E\right)$ 是顶点集为V，边集为E的一个简单无向图，对于任意两个顶点 $x,y\in V$ ，符号 $x~y$ 表示顶点x和顶点y被G中的一条边连接。对于 $x,y\in V$ ，距离 $d\left(x,y\right)$ 是连接顶点x和顶点y的所有路径中最短路径的长度。在一般图 $G=\left(V,E\right)$ 中，与某个顶点x相关联的边的数目称为该顶点的度数，记作 $d_x$ 。将顶点x在图G中的所有邻点构成的集合称为顶点x的邻集，记作 $N\left(x\right)$ ，那么有 $d_x=\left|N\left(x\right)\right|$ 。本文定义集合 $P_x\left(y\right):=\left|N\left(x\right)\backslash N\left(y\right)\right|$ ，即 $P_x\left(y\right)$ 是顶点x的邻点中不与顶点y相邻的顶点个数。

图 $G=\left(V,E\right)$ 的顶点集合V上的概率分布是一个映射 $m:V\to \left[0,1\right]$ ，其中 ${\displaystyle {\sum }_{x\in V}m\left(x\right)}=1$ 。对任意 $x\in V$ ， $\alpha \in \left[0,1\right]$ ，我们考虑以下形式的概率分布：

$m_x^{\alpha }\left(v\right)=\{\begin{array}{l}\alpha ,当v=x时,\\ \frac{1-\alpha }{d_x},当v\in N\left(x\right)时,\\ 0,其他.\end{array}$

假设 $xy\in E$ ， $m_x^{\alpha }$ 和 $m_y^{\alpha }$ 是V上的两个概率分布，定义运输计划为一个将概率分布 $m_x^{\alpha }$ 转移至概率分布 $m_y^{\alpha }$ 的映射 $A:V\times V\to \left[0,1\right]$ ，并满足以下约束条件：

$\{\begin{array}{l}\underset{v\in V}{{\displaystyle \sum }}A\left(u,v\right)=m_x^{\alpha }\left(u\right),u\in V,\\ \underset{u\in V}{{\displaystyle \sum }}A\left(u,v\right)=m_y^{\alpha }\left(v\right),v\in V,\\ A\left(u,v\right)\ge 0.\end{array}$

其中 $A\left(u,v\right)$ 表示从顶点u到顶点v的运输量。从 $m_x^{\alpha }$ 到 $m_y^{\alpha }$ 的所有运输方案的集合定义为 $\Pi \left(m_x^{\alpha },m_y^{\alpha }\right)$ 。

两个概率分布 $m_x^{\alpha }$ 和 $m_y^{\alpha }$ 之间的最优运输距离(即沃森斯坦距离)定义 $W\left(m_x^{\alpha },m_y^{\alpha }\right)$ 为：

$W\left(m_x^{\alpha },m_y^{\alpha }\right)={\min }_{A\in \Pi \left(m_x^{\alpha },m_y^{\alpha }\right)}{\displaystyle {\sum }_{u,v\in V}d}\left(u,v\right)A\left(u,v\right).$

其中最小值取遍所有运输方案 $A\in \Pi \left(m_x^{\alpha },m_y^{\alpha }\right)$ 。

边 $xy\in E$ 上的Lin-Lu-Yau Ricci曲率 $\kappa \left(x,y\right)$ 定义为

$\kappa \left(x,y\right)={\lim }_{\alpha \to 1}\frac{1-W\left(m_x^{\alpha },m_y^{\alpha }\right)}{1-\alpha }$ .

如果对于所有 $xy\in G$ 都有 $\kappa \left(x,y\right)=0$ ，我们称该图为Ricci平坦图。

本节没有给出的定义可在 [6] 中找到。

2. 主要结论

Cushing等人 [7] 为围长至少为5的Ricci平坦图进行了分类，He等人 [8] 对围长为4且边不交，即任意两个4-圈没有公共边的Ricci平坦图进行了分类。

我们很容易能够得到完全图 $K_n$ 具有常数正Ricci曲率 $\frac{n}{n-1}$ 。目前现有的对于Ricci曲率恒为0的图的研究较多，较少有研究Ricci曲率有下界的图以及具有常正Ricci曲率的图，因此本文对n个顶点上Ricci曲率至少为1的图，以及具有常正Ricci曲率1的图进行研究并得到相关结论。

引理1 设G是阶数 $n\ge 3$ 的简单图，且对于 $xy\in E\left(G\right)$ 有 $\kappa \left(x,y\right)\ge 1$ ，则 $P_x\left(y\right)\le 1$ 。

证明：假设对于边 $xy\in E\left(G\right)$ ，有 $P_x\left(y\right)\ge 2$ ，

$W\left(m_x^{\alpha },m_y^{\alpha }\right)\ge \left(\alpha -\frac{1-\alpha }{d_x}\right)+P_x\left(y\right)\cdot \frac{1-\alpha }{d_x}=\alpha +\left(P_x\left(y\right)-1\right)\frac{1-\alpha }{d_x}.$

$\kappa \left(x,y\right)={\lim }_{\alpha \to 1}\frac{1-W\left(m_x^{\alpha },m_y^{\alpha }\right)}{1-\alpha }\le \frac{1-\alpha -\left(P_x\left(y\right)-1\right)\frac{1-\alpha }{d_x}}{1-\alpha }=1-\frac{P_x\left(y\right)-1}{d_x}<1.$

与 $\kappa \left(x,y\right)\ge 1$ 对任意 $xy\in E\left(G\right)$ 成立矛盾。 □

引理2 设G是阶数 $n\ge 3$ 的简单图，且对于 $xy\in E\left(G\right)$ 有 $\kappa \left(x,y\right)\ge 1$ ，则G的任一个顶点至少与x和y之一相邻。

证明：假设存在一个顶点 $z\in V\left(G\right)$ ，顶点z既不与顶点x相邻也不与顶点y相邻。在不失一般性的前提下，假设 $d_G\left(x,z\right)=2$ (否则若 $d_G\left(x,z\right)\ge 3$ ，则在 $\left(x,z\right)$ 最短路径中我们可以找到另一个具有此性质的顶点)。则存在一个顶点 $w\in V$ 使得 $x~w~z$ 。我们有以下两个断言：

断言a $wy\notin E\left(G\right)$ 。

假设 $wy\in E\left(G\right)$ 。因为 $x~w~z$ ，但顶点z即不与顶点x相邻也不与顶点y相邻，这与引理1中 $P_x\left(y\right)\le 1$ 的事实是矛盾的。

断言b $d\left(x\right)\ge 3$ 。

假设 $d\left(x\right)=2$ ，因为 $x~w~z$ ， $P_x\left(y\right)\le 1$ ， $P_y\left(x\right)\le 1$ ，我们有 $d\left(y\right)\le 2$ 。同样地，我们可以得到 $d\left(w\right)=2$ 和 $d\left(z\right)\le 2$ 。

如果y和z有一个公共邻点v，则

$W\left(m_x^{\alpha },m_y^{\alpha }\right)=\left(\alpha -\frac{1-\alpha }{2}\right)+2\cdot \frac{1-\alpha }{2}=\alpha +\frac{1-\alpha }{2}.$

$\kappa \left(x,y\right)=\underset{\alpha \to 1}{\lim }\frac{1-W\left(m_x^{\alpha },m_y^{\alpha }\right)}{1-\alpha }=\underset{\alpha \to 1}{\lim }\frac{1-\alpha -\frac{1-\alpha }{2}}{1-\alpha }=\frac{1}{2}<1.$

如果y和z没有公共邻点，则

$W\left(m_x^{\alpha },m_y^{\alpha }\right)=\left(\alpha -\frac{1-\alpha }{2}\right)+3\cdot \frac{1-\alpha }{2}=\alpha +\left(1-\alpha \right)=1.$

$\kappa \left(x,y\right)=\underset{\alpha \to 1}{\lim }\frac{1-W\left(x,y\right)}{1-\alpha }=\underset{\alpha \to 1}{\lim }\frac{1-1}{1-\alpha }=0.$

上述两种情况都与 $\kappa \left(x,y\right)\ge 1$ 矛盾，断言b得证。

根据断言b，存在一个顶点 $v\in V\left(G\right)$ 使得 $xv\in E\left(G\right)$ 。因为 $w~x~y$ ，w不与y相邻，且 $P_x\left(w\right)\le 1$ ， $P_x\left(y\right)\le 1$ ，我们有 $wv\in E\left(G\right)$ ， $yv\in E\left(G\right)$ 。因为 $x~w~z$ ，z与x不相邻，且 $P_w\left(z\right)\le 1$ ，则 $zw\in E\left(G\right)$ 。我们有 $w~v$ 和 $z~v$ ，但是w和z都与y不相邻，因此 $P_v\left(y\right)\ge 2$ 。由引理1我们有 $\kappa \left(x,y\right)<1$ ，这与 $\kappa \left(x,y\right)\ge 1$ 对任意 $xy\in E\left(G\right)$ 成立矛盾。 □

以下是我们的主要结论之一。

定理3 对于任意阶数 $n\ge 3$ 的简单图， $\kappa \left(x,y\right)\ge 1$ 对任意 $xy\in E\left(G\right)$ 成立当且仅当最小度 $\delta \left(G\right)\ge n-2$ 。

证明：首先我们假设 $\kappa \left(x,y\right)\ge 1$ 对任意 $xy\in E\left(G\right)$ 成立。对于任意 $xy\in E\left(G\right)$ ，如果其余的 $n-2$ 个顶点都与顶点x和顶点y相邻，则结论成立。如果有q个顶点与顶点x相邻， $n-2-q$ 个顶点与顶点y相邻，那么根据引理1， $N\left(x\right)$ 中至少有 $q-1$ 个顶点与顶点y相邻，故 $d\left(y\right)\ge 1+\left(n-2-q\right)+\left(q-1\right)=n-2$ 。同样地，我们有 $d\left(x\right)\ge 1+q+\left(n-3-1\right)=n-2$ 。即有 $\delta \left(G\right)\ge n-2$ ，结论成立。

现在我们假设 $\delta \left(G\right)\ge n-2$ 。G中所有顶点的度数为 $n-2$ 或 $n-1$ 。我们有以下四种情况。

情况1 $d\left(x\right)=d\left(y\right)=n-2$ ，x和y有一个公共非邻点。

$W\left(m_x^{\alpha },m_y^{\alpha }\right)=\alpha -\frac{1-\alpha }{n-2}.$

$\kappa \left(x,y\right)=\underset{\alpha \to 1}{\lim }\frac{1-W\left(m_x^{\alpha },m_y^{\alpha }\right)}{1-\alpha }=\underset{\alpha \to 1}{\lim }\frac{1-\alpha +\frac{1-\alpha }{2}}{1-\alpha }=\frac{n-1}{n-2}>1.$

情况2 $d\left(x\right)=d\left(y\right)=n-2$ ，x和y有不同的不相邻顶点。假设顶点a是x的邻点但不与y相邻，b是y的邻点但不与x相邻。因为 $d\left(a\right)\ge n-2$ 且a不与y相邻，所以有 $d\left(a\right)=n-2$ 及 $a~b$ 。

$W\left(m_x^{\alpha },m_y^{\alpha }\right)=\left(\alpha -\frac{1-\alpha }{n-2}\right)+\frac{1-\alpha }{n-2}=\alpha .$

$\kappa \left(x,y\right)=\underset{\alpha \to 1}{\lim }\frac{1-W\left(m_x^{\alpha },m_y^{\alpha }\right)}{1-\alpha }=\underset{\alpha \to 1}{\lim }\frac{1-\alpha }{1-\alpha }=1.$

情况3 $d\left(x\right)=n-2$ ， $d\left(y\right)=n-1$ 。假设顶点z是y的邻点但不与x相邻。因为 $d\left(z\right)\ge n-2$ 且z不与x相邻，所以有 $d\left(z\right)=n-2$ ，z与x和y的 $n-3$ 个公共邻点公共邻点都相邻。

$W\left(m_x^{\alpha },m_y^{\alpha }\right)=\left(\alpha -\frac{1-\alpha }{n-2}\right)+2\cdot \left(\frac{1-\alpha }{n-2}-\frac{1-\alpha }{n-1}\right)+\left(n-3\right)\cdot \left(\frac{1-\alpha }{n-2}-\frac{1-\alpha }{n-1}\right)=\alpha .$

$\kappa \left(x,y\right)=\underset{\alpha \to 1}{\lim }\frac{1-W\left(m_x^{\alpha },m_y^{\alpha }\right)}{1-\alpha }=\underset{\alpha \to 1}{\lim }\frac{1-\alpha }{1-\alpha }=1.$

情况4 $d\left(x\right)=d\left(y\right)=n-1$ 。

$W\left(m_x^{\alpha },m_y^{\alpha }\right)=\alpha -\frac{1-\alpha }{n-1}.$

$\kappa \left(x,y\right)=\underset{\alpha \to 1}{\lim }\frac{1-W\left(m_x^{\alpha },m_y^{\alpha }\right)}{1-\alpha }=\underset{\alpha \to 1}{\lim }\frac{1-\alpha +\frac{1-\alpha }{n-1}}{1-\alpha }=\frac{n}{n-1}>1.$

综上所述，结论成立。

特别地，我们可以进一步刻画清楚每条边都具有常数Ricci曲率1的图。

定理4 对于任意阶数 $n\ge 3$ 的简单图， $\kappa \left(x,y\right)=1$ 对任意 $xy\in E\left(G\right)$ 成立当且仅当 $G=K_n-M$ ，其中M为 $K_n$ 中的最大匹配。

证明：首先我们假设 $\kappa \left(x,y\right)=1$ 对任意 $xy\in E\left(G\right)$ 成立。根据定理3，图G的最小度至少为 $n-2$ 。假设存在两个度为 $n-1$ 的顶点u和v。我们很容易能够计算出 $\kappa \left(x,y\right)>1$ ，与假设矛盾。因此，最多存在一个度为 $n-1$ 的顶点，即 $G=K_n-M$ ，其中M为 $K_n$ 中的最大匹配。

现在我们假设 $G=K_n-M$ ，其中M为 $K_n$ 中的最大匹配。

情况1 n是偶数。对于两个相邻的顶点x和y，假设 $u\in N\left(x\right)\backslash \left\{y\right\}$ ， $v\in N\left(y\right)\backslash \left\{x\right\}$ ，则

$A\left(x,y\right)=\alpha -\frac{1-\alpha }{n-2},d\left(x,y\right)=1.$

$A\left(u,v\right)=\frac{1-\alpha }{n-2},d\left(u,v\right)=1.$

$W\left(m_x^{\alpha },m_y^{\alpha }\right)=\left(\alpha -\frac{1-\alpha }{n-2}\right)+\frac{1-\alpha }{n-2}=\alpha$

$\kappa \left(x,y\right)=\underset{\alpha \to 1}{\lim }\frac{1-W\left(m_x^{\alpha },m_y^{\alpha }\right)}{1-\alpha }=\underset{\alpha \to 1}{\lim }\frac{1-\alpha }{1-\alpha }=1.$

情况2 n是奇数。存在一个顶点与其余 $n-1$ 个顶点相邻，记作z，则 $d\left(z\right)=n-1$ 。

(a) 假设x和y是相邻顶点， $d\left(x\right)=d\left(y\right)=n-2$ ， $u\in N\left(x\right)\backslash \left\{y\right\}$ ， $v\in N\left(y\right)\backslash \left\{x\right\}$ ，则

$A\left(x,y\right)=\alpha -\frac{1-\alpha }{n-2},d\left(x,y\right)=1.$

$A\left(u,v\right)=\frac{1-\alpha }{n-2},d\left(u,v\right)=1.$

$W\left(m_x^{\alpha },m_y^{\alpha }\right)=\left(\alpha -\frac{1-\alpha }{n-2}\right)+\frac{1-\alpha }{n-2}=\alpha$

$\kappa \left(x,y\right)=\underset{\alpha \to 1}{\lim }\frac{1-W\left(m_x^{\alpha },m_y^{\alpha }\right)}{1-\alpha }=\underset{\alpha \to 1}{\lim }\frac{1-\alpha }{1-\alpha }=1.$

(b) 对于顶点z和它的邻点之间的边，假设w是顶点z的不邻接于x的邻点，

$A\left(x,z\right)=\alpha -\frac{1-\alpha }{n-2},d\left(x,z\right)=1.$

$A\left(x,w\right)=\frac{1-\alpha }{n-2}-\frac{1-\alpha }{n-1},d\left(x,w\right)=2.$

$W\left(m_x^{\alpha },m_y^{\alpha }\right)=\left(n-3\right)\cdot \left(\frac{1-\alpha }{n-2}-\frac{1-\alpha }{n-1}\right)+\left(\alpha -\frac{1-\alpha }{n-2}\right)+2\cdot \left(\frac{1-\alpha }{n-2}-\frac{1-\alpha }{n-1}\right)=\alpha$

$\kappa \left(x,y\right)=\underset{\alpha \to 1}{\lim }\frac{1-W\left(m_x^{\alpha },m_y^{\alpha }\right)}{1-\alpha }=\underset{\alpha \to 1}{\lim }\frac{1-\alpha }{1-\alpha }=1.$

证毕。 □

3. 总结与展望

对围长为4或围长至少为5的Ricci曲率为0的Ricci平坦图已有较为详细的研究成果，而针对Ricci曲率有下界的图所具有的性质的研究较为空缺。本文通过研究顶点之间是否有连边及相邻两顶点的公共邻点个数，对每条边上的Ricci曲率都大于等于1的图进行刻画，弥补相关空缺。更进一步地，如果曲率在0到1之间，继续刻画相关图类是值得探讨的问题。

基金项目

广东省自然科学基金面上项目(2021A1515012047)。

NOTES

^*通讯作者。