# The convergence and uniqueness of a discrete-time nonlinear Markov chain

Ruowei Li and Florentin Münch  Ruowei Li: School of Mathematical Sciences,
Fudan University, Shanghai 200433, China; Shanghai Center for Mathematical
Sciences, Jiangwan Campus, Fudan University, No. 2005 Songhu Road, Shanghai
200438, China; Max Planck Institute for Mathematics in the Sciences, Leipzig
04103, Germany<EMAIL_ADDRESS>Florentin Münch: Max Planck Institute for
Mathematics in the Sciences, Leipzig 04103, Germany<EMAIL_ADDRESS>
###### Abstract.

In this paper, we prove the convergence and uniqueness of a general discrete-
time nonlinear Markov chain with specific conditions. The results have
important applications in discrete differential geometry. First, on a general
finite weighted graph, we prove the discrete-time Ollivier Ricci curvature
flow $d_{n+1}\coloneqq(1-\alpha\kappa_{d_{n}})d_{n}$ converges to a constant
curvature metric. Then the author in [34, Theorem 5.1] proved a Laplacian
separation principle on a locally finite graph with non-negative Ollivier
curvature. Here we prove the Laplacian separation flow converges to the
constant Laplacian solution and generalize the result to nonlinear $p$-Laplace
operators. Moreover, our results can also be applied to study the long-time
behavior in the nonlinear Dirichlet forms theory and nonlinear
Perron–Frobenius theory. At last, we define the Ollivier Ricci curvature of
nonlinear Markov chain which is consistent with the classical Ollivier Ricci
curvature, sectional curvature [5], coarse Ricci curvature on hypergraphs [17]
and the modified Ollivier Ricci curvature for $p$-Laplace. And we prove the
convergence results for the nonlinear Markov chain with nonnegative Ollivier
Ricci curvature.

###### Contents

  1. 1 Introduction
  2. 2 Convergence and uniqueness of nonlinear Markov chains
    1. 2.1 Proofs of main theorems.
    2. 2.2 An example of non-convergence.
  3. 3 Basic facts of graphs
    1. 3.1 Weighted graphs
    2. 3.2 Discrete Ricci curvature and curvature flow
    3. 3.3 Nonlinear Laplace and resolvent operators
    4. 3.4 Extremal Lipschitz extension
  4. 4 Applications
    1. 4.1 The convergence of Ollivier Ricci curvature flow.
    2. 4.2 The gradient estimate for resolvents of nonlinear Laplace.
    3. 4.3 The convergence of Laplacian separation flow.
    4. 4.4 The nonlinear Dirichlet form.
    5. 4.5 The nonlinear Perron–Frobenius theory.
  5. 5 The Ollivier Ricci curvature of nonlinear Markov chains

##  1\. Introduction

A nonlinear Markov chain, introduced by McKean [28] to tackle mechanical
transport problems, is a discrete space dynamical system generated by a
measure-valued operator with the specific feature of preserving positivity.
Compared with the linear Markov chain, its transition probability is dependent
not only on the state but also on the distribution of the process.

It is quite fundamental to understand the long-time behavior of Markov chains.
A classical result is that an irreducible lazy linear Markov chain converges
to its unique stationary distribution in the total variation distance [23,
44]. For the nonlinear case, Kolokoltsov [21] and BA Neumann [36] study the
long-term behavior of nonlinear Markov chains defined on probability simplex
whose transition probabilities are a family of stochastic matrices. Long-term
results exist for specific continuous-time Markov chains associated with
pressure and resistance games [22] and ergodicity criteria for discrete-time
Markov processes [4, 42]. This paper establishes convergence and uniqueness
results for a general discrete-time nonlinear Markov chain $P:\Omega\to\Omega$
under some of the following specific conditions:

  * •

Conditions on domain

    * –

(A) $\Omega\subseteq\mathbb{R}^{N}$ is closed.

    * –

(B) $\Omega+r\cdot(1,\ldots,1)=\Omega$ for all $r\in\mathbb{R}$.

  * •

Basic properties

    * –

Monotonicity

      * *

(1) Monotonicity: $Pf\geq Pg$ if $f\geq g$.

      * *

(2) Strict monotonicity: $Pf(x)>Pg(x)$ if $f\geq g$ and $f(x)>g(x)$ for some
$x$.

      * *

(3) Uniform strict monotonicity: $Pf\geq Pg+\epsilon_{0}(f-g)$, if $f\geq g$
for some fixed positive $\epsilon_{0}$.

    * –

Additivity

      * *

(4) Constant additivity: $P(f+C)=Pf+C$, where $C$ is a constant.

    * –

Non-expansion

      * *

(5) Non-expansion: $\left\|Pf-
Pg\right\|_{\infty}\leq\left\|f-g\right\|_{\infty}$ for all $f,g\in\Omega$.

  * •

Connectedness

    * –

(6) Connectedness: there exists $n_{0}\in\mathbb{N}_{+}$ such that for every
point $x,$ and $f,g\in\Omega$ with $f\geq g$ and $f(x)>g(x)$, we have
$P^{n_{0}}f>P^{n_{0}}g$, (i.e., strict inequality everywhere).

    * –

(7) Uniform connectedness: there exists $n_{0}\in\mathbb{N}_{+}$, positive
$\epsilon_{0}$ such that for every point $x,$ positive $\delta$ and
$f,g\in\mathbb{R}^{N}$ with $f\geq g+\delta\cdot 1_{x}$, we have
$P^{n_{0}}f\geq P^{n_{0}}g+\epsilon_{0}\delta$.

  * •

Accumulation points

    * –

(8) Accumulation point at infinity: $f_{n}\coloneqq P^{n}f-P^{n}f(x_{0})$ has
a finite accumulation point $g$, i.e. for every $n\in\mathbb{N}_{+}$ and
positive $\epsilon$, there exists $N>n$ such that
$\left\|f_{N}-g\right\|_{\infty}<\epsilon$.

    * –

(9) Finite accumulation point: $P^{n}f$ has a finite accumulation point $g$.

######  Definition 1.

A discrete-time nonlinear Markov chain $P:\Omega\to\Omega$ is a map satisfying
monotonicity (1) and non-expansion (5) where $\Omega$ satisfies (A) and (B).

In the theorems, we always reiterate the assumptions (1) and (5), even though
the conditions are implicitly given by the definition.

######  Remark 1.

(a) For a linear Markov chain, strict monotonicity (2) implies that $P$ is
lazy, which means it will remain in the same state with positive
probabilities.

(b) Uniform strict monotonicity (3) is stronger than monotonicity (1) and
strict monotonicity (2), which means that (3) implies (1) and (2).

(c) Since $f\leq g+\left\|f-g\right\|_{\infty}$ for every $f$ and $g$,
monotonicity (1) and constant additivity (4) imply the non-expansion condition
(5), which is more natural for nonlinear operators.

(d) A linear Markov chain is called irreducible if for every $x,y$ there
exists some $n$ such that its kernel $P^{n}(x,y)>0$, i.e. every state can be
reached from every other state. Saying a discrete Markov chain defined on a
graph is irreducible is the same as saying the graph is connected, which is
crucial to the uniqueness of the stationary distribution. And (6) is a
nonlinear version of the connectedness condition. Moreover, note that
$P^{n_{0}}$ also satisfies the strict monotonicity (2).

(e) The assumption of a finite accumulation point for $f_{n}$ (8) is weaker
than (9), which allows for cases that $P^{n}f$ goes to infinity at all
vertices. Moreover, the assumption (8) is necessary. In subsection 2.2, we
provide a counterexample demonstrating that $P^{n}f(y)-P^{n}f(x)$ does not
converge, even within the interval $\left[-\infty,\infty\right]$, without the
finite assumption (8).

(f) Consider a Markov chain $Q$ with absorbing states and maximal eigenvalue
$0<\lambda<1$, i.e., $Qf=\lambda f$. Defining
$Pf\coloneqq\text{log}Q\left(\text{exp}f\right)$, we have
$P(f+c)=\text{log}Q\left(\text{exp}\left(f+c\right)\right)=c+Pf$ for all
constant $c$. Then $P\text{log}f=\text{log}\lambda+\text{log}f$, that is,
nonlinear Markov chain $P$ exhibits linear growth by the constant
$\text{log}\lambda$.

We now present our main theorems. We remark that in the theorems, we can also
replace $\mathbb{R}^{N}$ by $\Omega$ satisfying (A) and (B). We mainly apply
Theorem 2 to applications.

######  Theorem 1.

If a discrete-time nonlinear Markov chain $P:\mathbb{R}^{N}\to\mathbb{R}^{N}$
satisfies

(1) monotonicity,

(2) strict monotonicity,

(5) non-expansion,

(9) $P^{n}f$ has a finite accumulation point $g$,

then $Pg=g$ and $P^{n}f\to g$ as $n\to\infty$.

Then we give the second convergence result.

######  Theorem 2.

If a discrete-time nonlinear Markov chain $P:\mathbb{R}^{N}\to\mathbb{R}^{N}$
satisfies

(1) monotonicity,

(2) strict monotonicity,

(4) constant additivity,

(8) accumulation point at infinity, i.e., $f_{n}\coloneqq
P^{n}f-P^{n}f(x_{0})$ has a finite accumulation point $g$, then $f_{n}\to g$
as $n\to\infty$. Moreover, if $P$ also satisfies

(6) connectedness,

then the convergence limit is unique, i.e., for another sequence
$\tilde{f_{n}}$ with finite accumulation point $\tilde{g}$, we have
$\underset{n\to\infty}{\text{lim}}\tilde{f}_{n}=\tilde{g}=g=\underset{n\to\infty}{\text{lim}}f_{n}$.

Next, we give another convergence result.

######  Theorem 3.

If a discrete-time nonlinear Markov chain $P:\mathbb{R}^{N}\to\mathbb{R}^{N}$
satisfies

(5) non-expansion,

(7) uniform connectedness,

(8) accumulation point at infinity, i.e., $f_{n}\coloneqq
P^{n}f-P^{n}f(x_{0})$ has a finite accumulation point $g$, then $f_{n}\to g$
as $n\to\infty$ and the limit is unique.

######  Remark 2.

Theorem 1 proves the convergence of nonlinear Markov chains under the
assumption of finite accumulation points (9). But Theorem 2 and Theorem 3
include the case of accumulation points at infinity (8), that is, $P^{n}f$
goes to infinity at all vertices. While Theorem 2 needs a stronger constant
additivity condition (4), Theorem 3 needs a stronger uniform connectedness
condition (7).

The convergence results have important applications in discrete differential
geometry which has become a hot research subject in the last decade. Since
Ricci curvature is a fundamental concept in Riemannian Geometry [18], various
different discrete analogs on graphs [10, 20, 26, 30, 39, 40, 43, 25, 11] have
attracted notable interest. Among them, the idea of discrete Ollivier Ricci
curvature $\kappa(x,y)=1-\frac{W(\mu_{x},\mu_{y})}{d(x,y)}$ is based on the
Wasserstein distance $W$ between probability measures $\mu_{x},\mu_{y}$ which
are defined on the one-step neighborhood of vertices $x,y$ [39, 40]. Lin, Lu,
and Yau [25] modified this notion to a limit version that is better suited for
graphs:

(1.1) $\kappa_{LLY}(x,y)=\underset{\alpha\to
0}{\text{lim}}\frac{\kappa^{\alpha}(x,y)}{1-\alpha}$

and
$\kappa^{\alpha}(x,y)=1-\frac{W(\mu_{x}^{\alpha},\mu_{y}^{\alpha})}{d(x,y)}$,
where $0\leq\alpha\leq\underset{x}{\text{max }}deg(x)$, the probability
distribution $\mu_{x}^{\alpha}$ assigns amount $1-\alpha\sum_{y\sim
x}\frac{w(x,y)}{m(x)}$ at vertex $x$ and amount $\alpha\frac{w(x,z)}{m(x)}$ to
all its neighbors $z$.

Ricci flow as a powerful method can also be applied to discrete geometry and
has drawn significant interest recently. Ollivier [39] suggested defining the
continuous time Ricci flow by deforming weights. Ni et al. in [38] define a
discrete-time Ricci flow. Bai et al. in [1] adopt Lin-Lu-Yau’s Ollivier Ricci
curvature [25] to define a continuous-time Ricci flow and obtain several
convergence results on path and star graphs. The authors in [13, 12] introduce
a discrete uniformization theorem for polyhedral surfaces and obtain a metric
with given curvature using a discrete Yamabe flow. The authors in [38] claim
good community detection on networks using discrete Ricci flow. The authors in
[7] establish a new algorithm to find circle packings by discrete Ricci flow.

The difficulties of studying the long-time behavior of the Ricci flow are the
nonlinearity and accumulation points are not unique. In this paper, we
consider the discrete Ricci flow in [38] and study its long-time behavior in
the following process. Consider a general finite weighted graph
$G=(V,E,w,m,d)$ with $deg(x)\leq 1$ for all $x\in V$. For an initial metric
$d_{0}$, fix some $C$ as the deletion threshold such that $C>\underset{x\sim
y\sim z}{\max}\frac{d_{0}(x,y)}{d_{0}(y,z)}$. Define a discrete time Ollivier
Ricci curvature flow by deforming the metric as

(1.2) $d_{n+1}(x,y)\coloneqq
d_{n}(x,y)-\alpha\kappa_{d_{n}}(x,y)d_{n}(x,y),\text{ if }x\sim y,$

where $\kappa_{d_{n}}$ is the Ollivier Ricci curvature corresponding to
$d_{n}$. After each Ricci flow step, we do a potential edge deletion step. If
$x\sim y\sim z$ and $d_{n+1}(x,y)>Cd_{n+1}(y,z)$, then update the graph by
deleting edges $x\sim y$ from $E$, starting with the longest edge. Let

$d_{n+1}(x,y)=\underset{}{\text{inf}}\left\\{\stackrel{{\scriptstyle[}}{{i}}=1]{k}{\sum}d_{n}(x_{i-1},x_{i}):x=x_{0}\sim
x_{1}\cdots\sim x_{k}=y\right\\},\text{ if }x\nsim y.$

Since the graph $G$ is finite and the graph of a single edge can not be
deleted, denote the new graph as $\tilde{G}$ after the last edge deletion.
Then on each connected component of $\tilde{G}$, the distance ratios are
bounded in $n$, and hence, $\text{log}d_{n}$ has an accumulation point at
infinity. Considering the Ricci flow (1.2) as a nonlinear Markov chain on each
connected component of $\tilde{G}$, by Theorem 2 we can prove that (1.2)
converges to a constant curvature metric.

######  Theorem 4.

For an initial metric $d_{0}$ of a finite weighted graph $G=(V,w,m,d)$ with
$deg(x)\leq 1$ for all $x\in V$, by the discrete Ollivier Ricci curvature flow
process defined above, then $\frac{d_{n}(e)}{\text{max }d_{n}(e^{\prime})}$
converges to a metric with constant curvature on every connected component of
the final graph $\tilde{G}$, where the max is taken over all $e^{\prime}$ in
the same connected component as $e$ on $\tilde{G}$.

######  Remark 3.

In [37], Ni, Lin, Gao and Gu presented a framework to endow a graph with a
novel metric through the notion of discrete Ricci flow with an application to
network alignment. From the experimental results, they found that the graph
Ricci curvature converges through the discrete Ricci flow and mentioned a
theoretic proof of the observation was still open. Theorem 4 solved this open
problem.

For another application, the author in [15, 34] consider a locally finite
graph $G=(V,E,w,m,d)$ with a non-negative Ollivier curvature, where $V=X\cup
K\cup Y$, $K$ is finite and $E(X,Y)=\emptyset$, that is, there are no edges
between $X$ and $Y$. They want to find a function with a constant gradient on
$X\cup Y$, minimal on $X$ and maximal on $Y$, and the Laplacian of $f$ should
be constant on $K$. By non-negative Ollivier curvature, it will follow that
the cut set $K$ separates the Laplacian $\Delta f$, i.e., $\Delta
f\mid_{X}\geq\text{const.}\geq\Delta f\mid_{Y}$, which is a Laplacian
separation principle [34, Theorem 5.1]. The result is crucial for proving an
isoperimetric concentration inequality for Markov chains with non-negative
Ollivier curvature [34], a discrete Cheeger-Gromoll splitting theorem [15],
and a discrete positive mass theorem [16]. Here we prove a natural parabolic
flow converging to the solution $f$. Now we give the details about the
Laplacian separation flow. First define an extremal 1-Lipschitz extension
operator $S:\mathbb{R}^{K}\to\mathbb{R}^{V}$,

$Sf(x)\coloneqq\begin{cases}\begin{array}[]{c}f(x):\\\ \underset{y\in
K}{\text{min}}\left(f(y)+d(x,y)\right):\\\ \underset{y\in
K}{\text{max}}\left(f(y)-d(x,y)\right):\end{array}&\begin{array}[]{c}x\in
K,\\\ x\in Y,\\\ x\in X.\end{array}\end{cases}$

Let $Lip(1,K)\coloneqq{\left\\{f\in\mathbb{R}^{K}:f(y)-f(x)\leq
d(x,y),\text{for all }x,y\in K\right\\}}$, where $d$ is the graph distance on
$G$. Then $S(Lip(1,K))$$\subseteq Lip(1,V)$. In [15], it is proven via
elliptic methods that there exists some $g$ with $\Delta Sg=\text{const}$.
Here we give the parabolic flow $(id+\epsilon\Delta)S$, and show that this
converges to the constant Laplacian solution, assuming non-negative Ollivier
Ricci curvature.

######  Theorem 5.

For a locally finite graph $G$ with non-negative Ollivier curvature, let
$x_{0}\in V$ and $P\coloneqq\left((id+\epsilon\Delta)S\right)\mid_{K}$, where
$\epsilon$ is small enough such that $\text{diag}(id+\epsilon\Delta)$ is
positive. Then for all $f\in Lip(1,K)$, there exists $g\in Lip(1,K)$ such that
$P^{n}f-P^{n}f(x_{0})$ converges to $g$ and $\Delta Sg\equiv\text{const}$ on
$K$.

Then we want to generalize the result to other nonlinear operators, such as
the $p$-Laplace operator, which can be defined as the subdifferential of the
energy functional

$\mathscr{E}_{p}(f)=\frac{1}{2}\underset{x,y\in
V}{\sum}\frac{w(x,y)}{m(x)}\mid\nabla_{xy}f\mid^{p}.$

More explicitly, the $p$-Laplace operator
$\Delta_{p}:\mathbb{R}^{V}\to\mathbb{R}^{V}$ is given by

$\Delta_{p}f(x)\coloneqq\frac{1}{m(x)}\underset{y}{\sum}w(x,y)\lvert
f(y)-f(x)\rvert^{p-2}\left(f(y)-f(x)\right),\text{if }p>1,$

and

$\Delta_{1}f(x)\coloneqq\left\\{\frac{1}{m(x)}\underset{y}{\sum}w(x,y)f_{xy}:f_{xy}=-f_{yx},f_{xy}\in\textrm{sign}(\nabla_{xy}f)\right\\}\text{,
}$

where $\text{sign}\left(t\right)=\begin{cases}\begin{array}[]{c}1,\\\
{}[-1,1]\\\ -1,\end{array},&\begin{array}[]{c}t>0,\\\ t=0,\\\
t<0.\end{array}\end{cases}$ And $p=2$ is the general discrete Laplace operator
$\Delta$.

There are two main difficulties. One is that $\Delta_{p}f$ may jump a lot when
$\nabla_{xy}f$ is near zero, for example, the derivative of $\Delta_{1}f$ near
$\nabla_{xy}f=0$ is large, which causes the operator $id+\epsilon\Delta_{p}$
to fail to maintain the strict monotonicity condition (2). Our idea is to
consider its resolvent $J_{\epsilon}=\left(id-\epsilon\Delta_{p}\right)^{-1}$
instead of the flow $id+\epsilon\Delta_{p}$. The resolvent operator
$J_{\epsilon}$ is single-valued and monotone, and we can check that
$J_{\epsilon}$ satisfies the strict monotonicity condition in Lemma 3.

Another difficulty is that we need a new curvature condition to guarantee the
Lipschitz decay property, which implies compactness, as well as the existence
of accumulation points. Define a new curvature on a graph $G=(V,w,m,d_{0})$
with combinatorial distance $d_{0}$

(1.3)
$\hat{k}_{p}(x,y)\coloneqq\underset{\pi_{p}}{\text{sup}}\underset{x^{\prime},y^{\prime}\in
B_{1}(x)\times
B_{1}(y)}{\sum}\pi_{p}(x^{\prime},y^{\prime})\left(1-\frac{d_{0}(x^{\prime},y^{\prime})}{d_{0}(x,y)}\right),$

where $\pi_{p}$ satisfies transport plan conditions and we require
$\pi_{p}(x^{\prime},y^{\prime})=0$ if $x^{\prime}=y^{\prime}$ (forbid
3-cycles) for $p>2$, and $\pi_{p}(x^{\prime},y^{\prime})=0$ if $x^{\prime}\neq
x$ and $y^{\prime}\neq y$ and $d_{0}(x^{\prime},y^{\prime})=2$ (forbid
5-cycles) for $1\leq p<2$, see detailed definition (4.1) in subsection 4.2.

Then we can prove there exists a stationary point $g$ such that
$g\in\Delta_{p}Sh$ and $g\equiv\text{const}$ on $K$.

######  Theorem 6.

For a locally finite graph $G=(V,w,m,d_{0})$ with a non-negative modified
curvature $\hat{k}$, let $x_{0}\in V$ and
$P\coloneqq\left((id+\epsilon\Delta)S\right)\mid_{K}$, where $\epsilon$ is
small enough such that $\text{diag}(id+\epsilon\Delta)$ is positive. Then for
all $f\in Lip(1,K)$, there exists $\tilde{f}\in Lip(1,K)$ such that
$P^{n}f-P^{n}f(x_{0})$ converges to $\tilde{f}$. Moreover, there exist
$h,g\in\mathbb{R}^{V}$ such that $g\in\Delta_{p}Sh$ and $g\mid_{X}\geq
g\mid_{K}\equiv\text{const}\geq g\mid_{Y}$.

Moreover, our nonlinear Markov chain settings overlap with the nonlinear
Dirichlet forms theory and nonlinear Perron–Frobenius theory, and our theorems
can be applied well to them. The theory of Dirichlet forms is conceived as an
abstract version of the variational theory of harmonic functions. For many
application fields, such as Riemannian geometry [18], it is necessary to
generalize Dirichlet forms to a nonlinear version. Since the conditions of our
theorems fit well in the nonlinear Dirichlet form theory, with additional
accumulation points at infinity assumptions we can obtain the convergence by
Theorem 2, see Theorem 8. The classical Perron–Frobenius theory concerns the
eigenvalues and eigenvectors of nonnegative coefficients matrices and
irreducible matrices. In order to apply the theory to a more general setting,
there are a lot of studies on the nonlinear Perron–Frobenius theory. After
some replacement of maps, our convergence results can also be applied to the
nonlinear Perron–Frobenius theory, see Theorem 9.

In Section 5, we introduce a definition of Ollivier Ricci curvature of
nonlinear Markov chains according to the Lipschitz decay property, that is,
for a nonlinear Markov chain $P$ with (1) monotonicity, (2) strict
monotonicity and (4) constant additivity properties, let
$d:V^{2}\to[0,+\infty)$ be the distance function. Then for $r\geq 0$, define

$Ric_{r}(P,d)\coloneqq 1-\underset{Lip(f)\leq
r}{\text{sup}}\frac{Lip(Pf)}{r},$

i.e., if $Lip(f)=r$, then $Lip(Pf)\leq(1-Ric_{r})Lip(f)$. Since the
nonnegative Ollivier Ricci curvature ensures the existence of accumulation
point at infinity (8), then as a corollary of Theorem 2, we can get the
convergence results for the nonlinear Markov chain with a nonnegative Ollivier
Ricci curvature. And we can also define the Laplacian separation flow of a
nonlinear Markov chain with $Ric_{1}(P,d)\geq 0$. Then we show that the
definition is consistent with the classical Ollivier Ricci curvature (3.1),
sectional curvature [5], coarse Ricci curvature on hypergraphs [17] and the
modified Ollivier Ricci curvature $\hat{k}_{p}$ for $p$-Laplace (1.3).

##  2\. Convergence and uniqueness of nonlinear Markov chains

###  2.1. Proofs of main theorems.

In this section, we give proof ideas and specific proofs of our main theorems.
First we summarize the proof ideas for Theorem 1. Let $Lf=Pf-f$ and prove
$\lambda(P^{n}f)\coloneqq\left\|LP^{n}f\right\|_{\infty}$ is decreasing in
$n$. Since $g$ is the accumulation point, then $\lambda(P^{k}g)=\lambda(g)$
for any $k$. As
$\eta_{+}(Pg)\subseteq\eta(g)\coloneqq\left\\{x:Lg(x)=\lambda(g)\right\\}$,
there exists some $x$ such that $P^{k}g(x)=g(x)+k\lambda(g)$. Taking a
subsequence $\left\\{k_{i}\right\\}$ such that $P^{k_{i}}g$ is also a finite
accumulation point, implying $\lambda(g)=0$. Then $g$ is a fixed point and
$P^{n}f$ converges. The proof details are as follows.

###### Proof of Theorem 1.

Define $\lambda(P^{n}f)\coloneqq\parallel P^{n+1}f-P^{n}f\parallel_{\infty}$,
which is decreasing in $n.$ Since $g$ is a finite accumulation point, then

$\lambda(g)=\underset{n\to\infty}{\text{lim}}\lambda(P^{n}f)$

and

$\lambda(P^{k}g)=\underset{n\to\infty}{\text{lim}}\lambda(P^{n+k}f).$

Hence $\lambda(g)=\lambda(P^{k}g)$ for any $k$. Then define
$\eta(f)\coloneqq\left\\{x:Lf(x)=\lambda(f)\right\\}$. W.l.o.g., suppose

$\lambda(P^{k}g)=\lambda_{+}(P^{k}g)\coloneqq\underset{x}{\text{max}}LP^{k}g(x)$

and

$x\in\eta_{+}(P^{k}g)\coloneqq\left\\{x:LP^{k}g(x)=\lambda_{+}(P^{k}g)\right\\},$

then we claim that $x\in\eta_{+}(P^{k-1}g)$. If not, we have

$LP^{k-1}g(x)<\lambda_{+}(P^{k-1}g)$

and

$P^{k}g(x)<P^{k-1}g(x)+\lambda_{+}(P^{k-1}g).$

By strict monotonicity (2) and non-expansion condition (5), we know

$P^{k+1}g(x)<P\left(P^{k-1}g+\lambda_{+}(P^{k-1}g)\right)(x)\leq
P^{k}g(x)+\lambda_{+}(P^{k-1}g).$

That implies

$LP^{k}g(x)<\lambda_{+}(P^{k-1}g)\leq\lambda(P^{k-1}g)=\lambda(P^{k}g)=\lambda_{+}(P^{k}g),$

which induces a contradiction. Hence, we have $x\in\eta_{+}(P^{k}g)$ for all
$k$. Thus,

(2.1) $P^{k}g(x)=g(x)+k\lambda(g).$

Since $g$ is a finite accumulation point, by taking a subsequence
$\left\\{k_{i}\right\\}$ such that $P^{k_{i}}g$ is still a finite accumulation
point, then $\lambda(g)=0$ by (2.1). Hence $P^{k}g=g$ and $P^{n}f\to g$ as
$n\to+\infty$. ∎

For Theorem 2, without the assumption of finite accumulation points, the
argument of $\lambda(P^{n}f)$ is not enough. The proof idea is as follows. We
define $\lambda_{+}(P^{n}f)\coloneqq\underset{x}{\text{max}}LP^{n}f(x)$ and
prove it is decreasing in $n$. Since $g$ is the accumulation point, then
$\lambda_{+}(P^{k}g)=\lambda_{+}(g)$ for any $k$. By the conclusion

$\eta_{+}(Pg)\subseteq\eta_{+}(g)\coloneqq\left\\{x:Lg(x)=\lambda_{+}(g)\right\\},$

there exists some $x$ such that $LP^{k}g(x)$ attains the maximum, i.e.
$P^{k}g(x)=g(x)+k\lambda_{+}(g)$. And there also exists some $y$ attaining its
minimum, i.e. $P^{k}g(y)=g(y)+k\lambda_{-}(g)$. Taking a subsequence
$\left\\{k_{i}\right\\}$ such that $P^{k_{i}}g$ is also a finite accumulation
point, implying $\lambda_{+}(g)=\lambda_{-}(g)$, that is, $Lg=const$. Hence
$P^{k}g=g+k\lambda_{+}$, and $g$ is the limit of $f_{n}$. For the uniqueness,
we prove that the linear growth rate $\lambda_{+}$ of different sequences
$f_{n}$ is the same by the non-expansion property. Then by the connectedness
(6) we know that all accumulation points are the same. The proof details are
as follows.

###### Proof of Theorem 2.

Define $Lf\coloneqq Pf-f$ and
$\lambda_{+}(f)\coloneqq\underset{x}{\text{max}}Lf(x)$, then

$Pf\leq f+\lambda_{+}(f).$

By monotonicity (1) and constant additivity (4), we have

$P^{2}f\leq P(f+\lambda_{+}(f))=Pf+\lambda_{+}(f).$

Hence $\lambda_{+}(Pf)\leq\lambda_{+}(f)$, that is, $\lambda_{+}(P^{n}f)$ is
decreasing in $n$. Since $g$ is a finite accumulation point for $f_{n}$,

$\lambda_{+}(g)=\underset{n\to\infty}{\text{lim}}\lambda_{+}(P^{n}f).$

For any $k$, since $P^{k}g$ is an accumulation point for $P^{k}f_{n}$, and
$LP^{k}f_{n}=LP^{n+k}f$ by constant additivity (4), we have

$\lambda_{+}(P^{k}g)=\underset{n\to\infty}{\text{lim}}\lambda_{+}(P^{n+k}f).$

Then $\lambda_{+}(g)=\lambda_{+}(P^{k}g).$

Defining the maximum points set as
$\eta_{+}(f)\coloneqq\left\\{x:Lf(x)=\lambda_{+}(f)\right\\}$, we claim that
$\eta_{+}(Pf)\subseteq\eta_{+}(f)$ if $\lambda_{+}(f)=\lambda_{+}(P^{k}f).$

If $Lf(x)<\lambda_{+}(f)$, i.e. $Pf(x)<f(x)+\lambda_{+}(f)$, since $Pf\leq
f+\lambda_{+}(f)$, then by strict monotonicity (2) and constant additivity
(4),

$P^{2}f(x)<P(f+\lambda_{+}(f))(x)=Pf(x)+\lambda_{+}(f).$

That is, we have $LPf(x)<\lambda_{+}(f)=\lambda_{+}(Pf)$. Hence,
$\eta_{+}(Pf)\subseteq\eta_{+}(f)$.

Then there exists some $x$ such that $x\in\eta_{+}(P^{k}f)$ for any $k$, that
is,

$P^{k}g(x)=g(x)+k\lambda_{+}(g)$

By the same argument, for
$\lambda_{-}(f)\coloneqq\underset{x}{\text{min}}Lf(x)$, there is $y$ such that

$P^{k}g(y)=g(y)+k\lambda_{-}(g).$

Since $g$ is a finite accumulation point, then there is a subsequence
$\left\\{n_{k}\right\\}$ such that $f_{n_{k}}\to g$. Taking a subsequence
$\left\\{k_{i}\right\\}$ with $\left\\{n_{k}+k_{i}\right\\}$ and
$\left\\{n_{k}\right\\}$ coincide, then $P^{k_{i}}g(x)-P^{k_{i}}g(y)$ must be
finite, which implies $\lambda_{+}(g)=\lambda_{-}(g)$ and
$Lg=Pg-g\equiv\lambda_{+}$. Then we get $P^{n}g=g+n\lambda_{+}$ and
$P^{n}g-P^{n}g(x_{0})=g-g(x_{0})$. Since $g$ (resp. $P^{k}g$) is an
accumulation point for $f_{n}$ (resp. $P^{k}f_{n}$), for any $\varepsilon$,
there exists some $n$ such that

$\|P^{n}f-P^{n}f(x_{0})-g\|_{\infty}<\varepsilon$

and

$\|P^{n+k}f-P^{n}f(x_{0})-P^{k}g\|_{\infty}<\varepsilon.$

Replacing $P^{k}g$ by $g+k\lambda_{+}$, we have

$\|P^{n+k}f-P^{n}f(x_{0})-g-k\lambda_{+}\|_{\infty}<\varepsilon.$

Since $g(x_{0})=0,$ we know $\mid
P^{n+k}f(x_{0})-P^{n}f(x_{0})-k\lambda_{+}\mid<\varepsilon.$ Then

$\displaystyle\|f_{n+k}-g\|_{\infty}$ $\displaystyle\leq$
$\displaystyle\|P^{n+k}f-P^{n}f(x_{0})-g-k\lambda_{+}\|_{\infty}+\mid
P^{n+k}f(x_{0})-P^{n}f(x_{0})-k\lambda_{+}\mid$ $\displaystyle<$
$\displaystyle 2\varepsilon,$

which means $f_{n}$ converges to $g$ as $n\to\infty$.

Then we want to prove the uniqueness with the connectedness assumption (6). By
the above argument, for any finite accumulation point $g$, we know
$Pg-g=\text{const}.$ We claim that the constants of any accumulation points
are the same. If not, then there exist $c_{1}\neq c_{2}$ such that
$P^{n}g^{1}=g^{1}+nc_{1}$ and $P^{n}g^{2}=g^{2}+nc_{2}$. Hence $\parallel
P^{n}g^{1}-P^{n}g^{2}\parallel_{\infty}\to\infty$, which contradicts to the
non-expansion property (5), i.e. $\parallel
Pg^{1}-Pg^{2}\parallel_{\infty}\leq\parallel g^{1}-g^{2}\parallel_{\infty}$.
Then we proved the claim.

Next if $g^{1}$ and $g^{2}$ are two different accumulation points, by adding a
constant, w.l.o.g., assume $g^{1}\geq g^{2}$ with $g^{1}(y)=g^{2}(y)$ and
$g^{1}(x)>g^{2}(x)$. By the connectedness condition (6), we get
$P^{n}g^{1}(y)>P^{n}g^{2}(y)$, that is, $g^{1}(y)+nc>g^{2}(y)+nc$ which
contradicts to $g^{1}(y)=g^{2}(y)$. Hence all accumulation points are the
same, which shows the uniqueness of limits. ∎

For Theorem 3, we remind that there is a naive but fatal idea of considering
$\tilde{P}f\coloneqq Pf-Pf(x_{0})$, which has a finite accumulation point, but
may lack the required monotonicity (1) and non-expansion (5) properties.

Our proof idea is as follows. Lemma 1 states that a sequence
${\left\\{x_{n}\right\\}}$ converges if it has exactly one accumulation point
and satisfies $d(x_{n},x_{n+1})\leq C$ for all $n$. Then we prove Theorem 3 by
proving the uniqueness of accumulation points. Let $\tilde{P}=P^{n_{0}}$,
satisfying non-expansion (5) and uniform connectedness (7) with $n_{0}=1$.
Suppose there is a subsequence $\left\\{n_{k}=m_{k}n_{0}+i\right\\}$ with
$0\leq i\leq n_{0}-1$ such that $f_{n_{k}}\to g$ and
$P^{n_{k}}f(x_{0})=\tilde{P}^{m_{k}}P^{i}f(x_{0})\to a\in[-\infty,+\infty]$ as
$k\to+\infty$. Divide it into two cases.

In the case of $\mid a\mid<+\infty$, since $\tilde{P}^{m}P^{i}f$ has a finite
accumulation point $\tilde{g}$, then $\tilde{P}\tilde{g}=\tilde{g}$ by Theorem
1. And accumulation points are the same after adding a constant by the uniform
connectedness of $\tilde{P}$, which implies the uniqueness of accumulation
points $\tilde{g}-\tilde{g}(x_{0})$ for $f_{n}=P^{n}f-P^{n}f(x_{0})$.

In the case of $\mid a\mid=+\infty$, for example, $a=+\infty$, define
$Qf\coloneqq\underset{r\to+\infty}{\text{lim}}\tilde{P}(f+r)-r$ satisfying
non-expansion (5), uniform connectedness (7) with $n_{0}=1$ and constant
additivity (4). Then $Q^{k}g$ is of constant linear growth of $k$, i.e.,
$Q^{k}g=g+kc$. Then the constant $c$ of different accumulation points are the
same by the non-expansion property. And the uniqueness of accumulation points
follows from the uniform connectedness of $Q$.

First, we give a convergence lemma by the uniqueness of accumulation points.

######  Lemma 1.

Let $(X,d)$ be a locally compact metric space, if a sequence
$\left\\{x_{n}\right\\}$ with exactly one accumulation point satisfying
$d(x_{k},x_{k+1})\leq C$ for some fixed constant $C$ and all
$k\in\mathbb{N}_{+}$, then $\left\\{x_{n}\right\\}$ converges.

###### Proof.

Let $x_{0}$ be the accumulation point. Prove by contradiction. For some
positive $\epsilon$, suppose that there is a subsequence
$\left\\{x_{n_{k}}\right\\}$ such that $d(x_{n_{k}},x_{0})\geq\epsilon$. For
$n_{k},$ let $m_{k}\geq n_{k}$ be the smallest number such that
$d(x_{m_{k}+1},x_{0})<\epsilon$, then
$d(x_{m_{k}},x_{0})\in[\epsilon,\epsilon+C]$. Hence
$\left\\{x_{m_{k}}\right\\}$ has an accumulation point different from $x_{0}$
as the local compactness, which contradicts to the uniqueness of accumulation
points. ∎

######  Remark 4.

We give a specific example to illustrate that the non-expansion

$d(x_{k},x_{k+1})\leq C$

is necessary. For $X=\mathbb{R}$, let $x_{2k}=k$, $x_{2k+1}=0$, which has
exactly one accumulation point but does not satisfy $d(x_{k},x_{k+1})\leq C$
for all $k$, and $\left\\{x_{n}\right\\}$ does not converge.

Next, we prove Theorem 3 by the uniqueness of accumulation points via the
uniform connectedness (7). Recall that if $P$ is uniformly connected, then
there exists $n_{0}\in\mathbb{N}_{+}$, positive $\epsilon_{0}$ such that for
some point $x,$ positive $\delta$ and $f,g\in\mathbb{R}^{N}$ with $f\geq
g+\delta\cdot 1_{x}$, we have $P^{n_{0}}f\geq P^{n_{0}}g+\epsilon_{0}\delta$.

###### Proof of Theorem 3.

Let $\tilde{P}=P^{n_{0}}$, then $\tilde{P}$ is uniformly connected with
$n_{0}=1$, implying strict monotonicity (2). As $g$ is an accumulation point,
then there is $0\leq i\leq n_{0}-1$ and a subsequence
$\left\\{n_{k}=m_{k}n_{0}+i\right\\}$ such that $f_{n_{k}}\to g$ and
$P^{n_{k}}f(x_{0})\to a\in[-\infty,+\infty]$ as $k\to+\infty$. Divide it into
two cases: $\mid a\mid<+\infty$ and $\mid a\mid=+\infty$.

Case 1. If $\mid a\mid<+\infty$, w.l.o.g, suppose $a>0$.

Then $P^{n_{k}}f=\tilde{P}^{m_{k}}P^{i}f\eqqcolon\tilde{P}^{m_{k}}F\to
g+a\eqqcolon\tilde{g}$ as $k\to+\infty$. By Theorem 1, we have
$\tilde{P}^{m}F\to\tilde{g}$ as $m\to+\infty$ and
$\tilde{P}^{k}\tilde{g}=\tilde{g}$ for all $k$. Then for different
accumulation points of $f_{n}$, by the non-expansion property (5), their
corresponding $a$ must be the same case.

If there are two accumulation points $\tilde{g}_{1}\neq\tilde{g}_{2}$, suppose
$\alpha\coloneqq\underset{x}{\text{max}}\left(\tilde{g}_{1}(x)-\tilde{g}_{2}(x)\right)>0$.
Then $\tilde{g}_{1}\leq\tilde{g}_{2}+\alpha$. If there exists $x$ such that
$\tilde{g}_{1}(x)<\tilde{g}_{2}(x)+\alpha$, then by the uniform connectedness
and non-expansion property of $\tilde{P}$,

$\tilde{g}_{1}=\tilde{P}\tilde{g}_{1}<\tilde{P}\left(\tilde{g}_{2}+\alpha\right)\leq\tilde{P}\tilde{g}_{2}+\alpha=\tilde{g}_{2}+\alpha,$

which implies $\tilde{g}_{1}<\tilde{g}_{2}+\alpha$ and contradicts to the
definition of $\alpha$. Hence $\tilde{g}_{1}=\tilde{g}_{2}+\alpha$, which
means $\tilde{g}_{1}-\tilde{g}_{1}(x_{0})=\tilde{g}_{2}-\tilde{g}_{2}(x_{0})$.
Then the two accumulation points $g_{i}=\tilde{g}_{i}-\tilde{g}_{i}(x_{0})$
for $i=1,2$ of $f_{n}$ are the same. By Lemma 1, we get the convergence of
$f_{n}$.

Case 2. If $\mid a\mid=+\infty$, w.l.o.g., suppose $a=+\infty$.

Since $\tilde{P}(f+r)-r$ is decreasing for positive $r$ by the non-expansion
condition (5), we define

$Qf\coloneqq\underset{r\to+\infty}{\text{lim}}\left(\tilde{P}(f+r)-r\right).$

As
$Qg-g=\underset{k\to+\infty}{\text{lim}}\left(\tilde{P}^{m_{k}+1}F-\tilde{P}^{m_{k}}F\right)$
is finite by the non-expansion property (5) of $\tilde{P}$, then for any $f$,
we know $Qf$ is also finite by the non-expansion property. Then $Q$ satisfies
the non-expansion property (5) and constant additivity $Q(f+c)=Qf+c$.

Now we show the connectedness of $Q$. For some point $x$, positive $\delta$
and $f,h\in\mathbb{R}^{N}$ with $f\geq h+\delta\cdot 1_{x}$, since $\tilde{P}$
is uniformly connected with $n_{0}=1$, we have

$\tilde{P}\left(f+r\right)-r>\tilde{P}\left(h+r\right)-r+\epsilon_{0}\delta\geq
Qh+\epsilon_{0}\delta.$

Take $r\to+\infty$, then $Qf>Qh+\epsilon_{0}\delta$ and $Q$ is uniformly
connected with $n_{0}=1$ and $\epsilon_{0}$.

Let $\lambda_{+}^{\tilde{P}}(f)\coloneqq\text{max}\left(\tilde{P}f-f\right)$
and $F=P^{i}f$, then $\lambda_{+}^{\tilde{P}}(\tilde{P}^{m}F)>0$ for all $m$
since $\tilde{P}^{m_{k}}F(x_{0})\to+\infty$. By the monotonicity and non-
expansion property,

$\tilde{P}^{m+2}F\leq\tilde{P}\left(\tilde{P}^{m}F+\lambda_{+}^{\tilde{P}}(\tilde{P}^{m}F)\right)\leq\tilde{P}^{m+1}F+\lambda_{+}^{\tilde{P}}(\tilde{P}^{m}F),$

which means $\lambda_{+}^{\tilde{P}}(\tilde{P}^{m}F)$ is decreasing in $m$.
Since $g$ is a finite accumulation point, for all $l\in\mathbb{N}_{+}$, we
have

$Qg-g=\underset{k\to+\infty}{\text{lim}}\left(\tilde{P}^{m_{k}+1}F-\tilde{P}^{m_{k}}F\right)$

and

$Q^{l+1}g-Q^{l}g=\underset{k\to+\infty}{\text{lim}}\left(\tilde{P}^{m_{k}+l+1}F-\tilde{P}^{m_{k}+l}F\right).$

Then by the monotonicity of $\lambda_{+}^{\tilde{P}}(\tilde{P}^{m}F)$, we have

$\lambda_{+}^{Q}(g)=\text{max}\left(Qg-g\right)=\underset{m\to+\infty}{\text{lim}}\lambda_{+}^{\tilde{P}}(\tilde{P}^{m}F)=\lambda_{+}^{Q}(Q^{l}g).$

Since $Qg\leq g+\lambda_{+}^{Q}(g)$, if there is $x$ such that
$Qg(x)<g(x)+\lambda_{+}^{Q}(g)$, then

$Q^{2}g<Qg+\lambda_{+}^{Q}(g)=Qg+\lambda_{+}^{Q}(Qg)$

by the uniform connectedness and constant additivity of $Q$, which contradicts
to the definition of $\lambda_{+}^{Q}$. Hence $Qg=g+\lambda_{+}^{Q}(g)$ and
$Q^{l}g=g+l\lambda_{+}^{Q}(g)$.

Let $f^{(1)},f^{(2)}\in\mathbb{R}^{N}$ and assume $g_{i}$ is an accumulation
point of $f_{n}^{(i)}=P^{n}f^{(i)}-P^{n}f^{(i)}(x_{0})$ for $i=1,2$. Then by
the non-expansion property

$\left\|g_{1}+l\lambda_{+}^{Q}(g_{1})-g_{2}-l\lambda_{+}^{Q}(g_{2})\right\|_{\infty}=\left\|Q^{l}g_{1}-Q^{l}g_{2}\right\|_{\infty}\leq\left\|g_{1}-g_{2}\right\|_{\infty},$

we know $\lambda_{+}^{Q}(g_{1})=\lambda_{+}^{Q}(g_{2})$. If $g_{1}\neq g_{2}$,
suppose
$\alpha\coloneqq\underset{x}{\text{max}}\left(g_{1}(x)-g_{2}(x)\right)>0$.
Then $g_{1}\leq g_{2}+\alpha$ and $0=g_{1}(x_{0})<g_{2}(x_{0})+\alpha=\alpha$.
By the uniform connectedness of $Q$,

$g_{1}+\lambda_{+}^{Q}(g_{1})=Qg_{1}<Qg_{2}+\alpha=g_{2}+\lambda_{+}^{Q}(g_{2})+\alpha,$

which implies $g_{1}<g_{2}+\alpha$ and contradicts to the definition of
$\alpha$. Then the two accumulation points are the same.

By Lemma 1 and letting $f^{(1)}=f^{(2)}=f$, we get the convergence of $f_{n}$.
Moreover, the case $f^{(1)}\neq f^{(2)}$ shows the uniqueness of the limit. ∎

###  2.2. An example of non-convergence.

Note that the condition of accumulation points at infinity (8) is necessary
for the convergence. Next, we give a concrete example, which shows that
without the condition of accumulation points (8), then $P^{n}f(y)-P^{n}f(x)$
does not converge even in $\left[-\infty,\infty\right]$. First we prove an
extension lemma.

######  Lemma 2.

Suppose that a closed subspace $\Omega\subseteq\mathbb{R}^{N}$ satisfies
$a+c\in\Omega$ for any $a\in\Omega$ and $c\in\mathbb{R}$. If
$P:\Omega\to\Omega$ satisfies uniform strict monotonicity (3) and constant
additivity (4), then $P$ can be extended to $\mathbb{R}^{N}$ with conditions
(3) and (4).

###### Proof.

For any $f\in\mathbb{R}^{N}$, define the extension of $P$ as

$\bar{P}f\coloneqq\text{inf}\left\\{Pg-\epsilon(g-f):g\in\Omega,g\geq
f\right\\},$

where $\epsilon$ is defined in uniform strict monotonicity (3). Then $\bar{P}$
satisfies constant additivity (4). If $f_{1}\geq f_{2},$ we know

$\displaystyle\bar{P}f_{1}$
$\displaystyle=\inf\left\\{Pg-\epsilon(g-f_{1}):g\in\Omega,g\geq
f_{1}\right\\}$
$\displaystyle\geq\inf\left\\{Pg-\epsilon(g-f_{1}):g\in\Omega,g\geq
f_{2}\right\\}$ $\displaystyle=\bar{P}f_{2}+\epsilon(f_{1}-f_{2}).$

Then $\bar{P}$ satisfies uniform strict monotonicity (3). Particularly,
$\bar{P}f>-\infty$ for all $f$. ∎

Now we give a counterexample. Let

$\Omega_{e}\coloneqq\left\\{\left(n,-n,-\varepsilon_{0},\varepsilon_{0}\right)+\vec{c}\in\mathbb{R}^{4},n\text{
is even},\vec{c}=(c,c,c,c)\in\mathbb{R}^{4},\varepsilon_{0}\ll 1\right\\},$
$\Omega_{o}\coloneqq\left\\{\left(n,-n,\varepsilon_{0},-\varepsilon_{0}\right)+\vec{c}\in\mathbb{R}^{4},n\text{
is odd},\vec{c}=(c,c,c,c)\in\mathbb{R}^{4},\varepsilon_{0}\ll 1\right\\},$

and define $P:\Omega\coloneqq\Omega_{e}\cup\Omega_{o}\to\Omega$ as

$\begin{array}[]{cc}P\left(\left(n,-n,-\varepsilon_{0},\varepsilon_{0}\right)+\vec{c}\right)=(n+1,-n-1,\varepsilon_{0},-\varepsilon_{0})+\vec{c},&\text{if
}n\text{ is even},\\\
P\left(\left(n,-n,\varepsilon_{0},-\varepsilon_{0}\right)+\vec{c}\right)=(n+1,-n-1,-\varepsilon_{0},\varepsilon_{0})+\vec{c},&\text{if
}n\text{ is odd}.\end{array}$

Then we want to show that $P$ satisfies uniform strict monotonicity (3).
Suppose

$f=(n,-n,\pm\varepsilon_{0},\mp\varepsilon_{0})+\vec{c_{1}},$
$g=(m,-m,\pm\varepsilon_{0},\mp\varepsilon_{0})+\overrightarrow{\left(c_{1}-\mid
n-m\mid\right)},$

then $f\geq g$. And

$\displaystyle Pf-Pg-\frac{f-g}{2}$
$\displaystyle\geq\frac{1}{2}\left[\left(n-m,m-n,-2\varepsilon_{0},-2\varepsilon_{0}\right)+\overrightarrow{\mid
n-m\mid}\right]$ $\displaystyle\geq\left(0,0,0,0\right),$

which means that $P$ satisfies uniform strict monotonicity (3) with
$\epsilon=\frac{1}{2}$. By Lemma 2, one can extend it to $\mathbb{R}^{N}$ with
uniform strict monotonicity (3) and constant additivity (4). But
$P^{n}f(x_{3})-P^{n}f(x_{4})$ always jumps between two values $\pm
2\varepsilon_{0}$ and does not converge.

Figure 1. This figure shows an example of non-convergence.

##  3\. Basic facts of graphs

The main applications of our theorems are parabolic equations on graphs. Now
we give a overview of weighted graphs.

###  3.1. Weighted graphs

A weighted graph $G=(V,w,m,d)$ consists of a countable set $V$, a symmetric
function $w:V\times V\to[0,+\infty)$ called edge weight with $w=0$ on the
diagonal, and a function $m:V\to\left(0,+\infty\right)$ called vertex measure
or volume. The edge weight $w$ induces a symmetric edge relation
$E=\left\\{\left(x,y\right):w(x,y)>0\right\\}$. We write $x\sim y$ if
$w(x,y)>0$. In the following, we only consider locally finite graphs, i.e.,
for every $x\in V$ there are only finitely many $y\in V$ with $w(x,y)>0$. The
degree at $x$ defined as $deg(x)=\underset{y\sim
x}{\mathop{\sum}}\frac{w(x,y)}{m(x)}$. We say a metric
$d:V^{2}\rightarrow[0,+\infty)$ is a path metric on a graph $G$ if

$d(x,y)=\inf\left\\{\stackrel{{\scriptstyle[}}{{i}}=1]{n}{\sum}d(x_{i-1},x_{i}):x=x_{0}\sim\ldots\sim
x_{n}=y\right\\}.$

By assigning each edge of length one, we get the combinatorial distance
$d_{0}$. For a function $f$ defined on vertex set $V,$ denoted as
$f\in\mathbb{R}^{V},$ define the difference operator for any $x\sim y$ as

$\nabla_{xy}f=f(y)-f(x).$

The Laplace operator is defined as

$\Delta f(x)\coloneqq\frac{1}{m(x)}\underset{y}{\sum}w(x,y)\nabla_{xy}f.$

For $f\in\mathbb{R}^{V}$, we write
$\left\|f\right\|_{\infty}\coloneqq\sup_{x\in V}\mid f(x)\mid$ and
$\left\|f\right\|_{2}\coloneqq\underset{x,y}{\sum}\frac{w(x,y)}{m(x)}f(x)^{2}$.

###  3.2. Discrete Ricci curvature and curvature flow

Let $G=(V,w,m,d)$ be a locally finite graph with path metric $d$. A
probability distribution over the vertex set $V$ is a mapping $\mu:V\to[0,1]$
satisfying $\sum_{x\in V}\mu(x)=1$. Suppose that two probability distributions
$\mu_{1}$ and $\mu_{2}$ have a finite support. A coupling between $\mu_{1}$
and $\mu_{2}$ is a mapping $\pi:V\times V\to[0,1]$ with finite support such
that

$\underset{y\in V}{\sum}\pi(x,y)=\mu_{1}(x)\text{ and }\underset{x\in
V}{\sum}\pi(x,y)=\mu_{2}(y).$

The Wasserstein distance between two probability distributions $\mu_{1}$ and
$\mu_{2}$ is defined as

$W(\mu_{1},\mu_{2})=\underset{\pi}{\inf}\underset{x,y\in
V}{\sum}\pi(x,y)d(x,y),$

where the infimum is taken over all coupling $\pi$ between $\mu_{1}$ and
$\mu_{2}$.

For every $x,y\in V$, the Ollivier Ricci curvature $\kappa(x,y)$ is defined to
be

(3.1) $\kappa(x,y)=1-\frac{W(\mu_{x},\mu_{y})}{d(x,y)}.$

where

$\mu_{x}(z)=\begin{cases}\begin{array}[]{c}\frac{w(x,z)}{m(x)}\\\
0\end{array}&\begin{array}[]{c}:z\sim x,\\\
:\text{otherwise}.\end{array}\end{cases}$

In this paper, we consider the discrete Ollivier Ricci flow and study its
long-time behavior in the following process. Consider a general finite
weighted graph $G=(V,w,m,d)$. For an initial metric $d_{0}$, fix some $C$ as
the deletion threshold such that $C>\underset{x\sim y\sim
z}{\max}\frac{d_{0}(x,y)}{d_{0}(y,z)}$. Define a discrete time Ollivier Ricci
curvature flow by deforming the metric as

$d_{n+1}(x,y)\coloneqq d_{n}(x,y)-\alpha\kappa_{d_{n}}(x,y)d_{n}(x,y),\text{
if }x\sim y,$

where $\kappa_{d_{n}}$ is the Ollivier Ricci curvature corresponding to
$d_{n}$. After each Ricci flow step, we do a potential edge deletion step. If
$x\sim y\sim z$ and $d_{n+1}(x,y)>Cd_{n+1}(y,z)$, then update the graph by
deleting edges $x\sim y$ from $E$, starting with the longest edge. Let

$d_{n+1}(x,y)=\underset{}{\text{inf}}\left\\{\stackrel{{\scriptstyle[}}{{i}}=1]{k}{\sum}d_{n}(x_{i-1},x_{i}):x=x_{0}\sim
x_{1}\cdots\sim x_{k}=y\right\\},\text{ if }x\nsim y.$

Since the graph $G$ is finite and graphs of a single edge can not be deleted,
denote the new graph as $\tilde{G}$ after the last edge deletion. Then on each
connected component of $\tilde{G}$, the distance ratios are bounded in $n$,
and hence, $\text{log}d_{n}$ has an accumulation point at infinity.
Considering Ricci flow (1.2) as a nonlinear Markov chain on each connected
component of $\tilde{G}$, by Theorem 2 we can prove that (1.2) converges to a
constant curvature metric.

###  3.3. Nonlinear Laplace and resolvent operators

On a locally finite weighted graph $G=(V,w,m,d)$, for every $p\geq 1$, define
the energy functional of $f\in\mathbb{R}^{V}$as

$\mathscr{E}_{p}(f)=\frac{1}{2}\underset{x,y\in
V}{\sum}\frac{w(x,y)}{m(x)}\mid\nabla_{xy}f\mid^{p},$

see reference [6, 27]. The $p$-Laplace operator $\Delta_{p}$ is the
subdifferential of energy functional $\mathscr{E}_{p}$, defined as
$\Delta_{p}:\mathbb{R}^{V}\to\mathbb{R}^{V}$

$\Delta_{p}f(x)\coloneqq\frac{1}{m(x)}\underset{y}{\sum}w(x,y)\lvert
f(y)-f(x)\rvert^{p-2}\left(f(y)-f(x)\right),\text{if }p>1,$

and

$\Delta_{1}f(x)\coloneqq\left\\{\frac{1}{m(x)}\underset{y}{\sum}w(x,y)f_{xy}:f_{xy}=-f_{yx},f_{xy}\in\textrm{sign}(\nabla_{xy}f)\right\\}\text{,
}$

where $sign\left(t\right)=\begin{cases}\begin{array}[]{c}1,\\\ {}[-1,1]\\\
-1,\end{array},&\begin{array}[]{c}t>0,\\\ t=0,\\\ t<0.\end{array}\end{cases}$
And $p=2$ is the general discrete Laplace operator $\Delta$.

The resolvent operator of $\Delta_{p}$ is defined as
$J_{\epsilon}=\left(id-\epsilon\Delta_{p}\right)^{-1}$ for $\epsilon>0$. Since
$-\Delta_{p}$ is a monotone operator, i.e., for every $f,g\in\mathbb{R}^{V}$,
we have

$\left\langle-\Delta_{p}f+\Delta_{p}g,f-g\right\rangle\geq 0,$

then the resolvent $J_{\epsilon}$ is single-valued, monotone, and non-
expansion, i.e.,

$\parallel J_{\epsilon}f-J_{\epsilon}g\parallel_{\infty}\leq\parallel
f-g\parallel_{\infty}.$

See details [31, Corollary 2.10] [41, Proposition 12.19]. Moreover, since
$\Delta_{p}$ is the subdifferential of convex function $\mathscr{E}_{p}$, it
follows that

$J_{\epsilon}f=\underset{g\in\mathbb{R}^{V}}{\text{argmin}}\left\\{\mathscr{E}_{p}(g)+\frac{1}{2\epsilon}\left\|g-f\right\|_{2}^{2}\right\\}.$

###  3.4. Extremal Lipschitz extension

To study the Laplacian separation flow from the introduction, we give the
definition of extremal Lipschitz extension on a specific graph structure.
Consider a locally finite graph $G=(V,w,m,d)$ with non-negative Ollivier
curvature, where $V=X\sqcup K\sqcup Y$and $K$ is finite and
$E(X,Y)=\emptyset$. Set $Lip(1,K):=\left\\{f\in\mathbb{R}^{K}:\nabla_{xy}f\leq
d(x,y)\text{ for all }x,y\in K\right\\}$ and define an extremal Lipschitz
extension operator $S:\mathbb{R}^{K}\to\mathbb{R}^{V}$ as

$Sf(x)\coloneqq\begin{cases}\begin{array}[]{c}f(x):\\\ \underset{y\in
K}{\text{min}}\left(f(y)+d(x,y)\right):\\\ \underset{y\in
K}{\text{max}}\left(f(y)-d(x,y)\right):\end{array}&\begin{array}[]{c}x\in
K,\\\ x\in Y,\\\ x\in X,\end{array}\end{cases}$

where $d$ is the graph distance on $G$. Then $S(Lip(1,K))\subseteq Lip(1,V)$.

##  4\. Applications

In this section, we prove that our convergence and uniqueness results have
important applications in the Ollivier Ricci curvature flow, the Laplacian
separation flow, the nonlinear Dirichlet form and nonlinear Perron–Frobenius
theory.

###  4.1. The convergence of Ollivier Ricci curvature flow.

Recall the convergence process of the discrete Ollivier Ricci flow. On a
general finite weighted graph $G=(V,w,m,d)$ with $deg(x)\leq 1$ for all $x\in
V$. For an initial metric $d_{0}$, fix some $C$ as the deletion threshold such
that $C>\underset{x\sim y\sim z}{\max}\frac{d_{0}(x,y)}{d_{0}(y,z)}$. For
$0<\alpha<1$, define a discrete time Ollivier Ricci curvature flow by
deforming the metric as

$d_{n+1}(x,y)\coloneqq d_{n}(x,y)-\alpha\kappa_{d_{n}}(x,y)d_{n}(x,y),\text{
if }x\sim y,$

where $\kappa_{d_{n}}$ is the Ollivier Ricci curvature corresponding to
$d_{n}$. After each Ricci flow step, we do a potential edge deletion step. If
$x\sim y\sim z$ and $d_{n+1}(x,y)>Cd_{n+1}(y,z)$, then update the graph by
deleting edges $x\sim y$ from $E$, starting with the longest edge. Let

$d_{n+1}(x,y)=\underset{}{\text{inf}}\left\\{\stackrel{{\scriptstyle[}}{{i}}=1]{k}{\sum}d_{n}(x_{i-1},x_{i}):x=x_{0}\sim
x_{1}\cdots\sim x_{k}=y\right\\},\text{ if }x\nsim y.$

Since the graph $G$ is finite and graphs of a single edge can not be deleted,
denote the new graph as $\tilde{G}$ after the last edge deletion. Then on each
connected component of $\tilde{G}$, the distance ratios are bounded in $n$,
and hence, $\text{log}d_{n}$ has an accumulation point at infinity.
Considering the Ricci flow as a nonlinear Markov chain on each connected
component of $\tilde{G}$, by Theorem 2 we can prove that (1.2) converges to a
constant curvature metric.

Theorem 4. For an initial metric $d_{0}$ of a finite weighted graph
$G=(V,w,m,d)$ with $deg(x)\leq 1$ for all $x\in V$, by the discrete Ollivier
Ricci curvature flow process defined above, then $\frac{d_{n}(e)}{\text{max
}d_{n}(e^{\prime})}$ converges to a metric with constant curvature on every
connected component of the final graph $\tilde{G}$, where the max is taken
over all $e^{\prime}$ in the same connected component as $e$ on $\tilde{G}$.

###### Proof.

For $f\in\mathbb{R}_{+}^{E}$, define $Sf\in\mathbb{R}^{V\times V}$ as

$Sf(x,y)=\underset{}{\text{inf}}\left\\{\stackrel{{\scriptstyle[}}{{i}}=1]{k}{\sum}f(x_{i-1},x_{i}):x=x_{0}\sim
x_{1}\cdots\sim x_{k}=y\right\\}.$

Note that $Sf$ is a distance on $V$. By (1.2), for $f\in\mathbb{R}^{E}$,
define

$\tilde{P}f(x,y)\coloneqq\alpha
W_{Sf}(p(x,\cdot),p(y,\cdot))+(1-\alpha)f(x,y),$

where $W_{Sf}$ is the Wasserstein distance corresponding to the distance $Sf$
and $p$ is the Markov kernel. Then $\tilde{P}$ corresponds to one step of the
Ollivier Ricci flow, that is,

$d_{n+1}\mid_{E}=\tilde{P}(d_{n}\mid_{E}).$

Clearly, $\tilde{P}$ satisfies monotonicity (1) and strict monotonicity (2).
Since

$\tilde{P}(rd)=r\tilde{P}d,\>\forall r>0,$

define $Pf\coloneqq\text{log $\tilde{P}$(exp$(f)$)}$ with $f=\text{log}\,d$.
Then for every constant $C\in\mathbb{R}$,

$P(f+C)=\text{log}(\tilde{P}\left(\text{exp}f\cdot\text{exp}C\right))=\text{log}(\text{exp}C\tilde{\,P}(\text{exp}f))=C+Pf,$

which implies that $P$ satisfies constant additivity (4). Since $P$ also
satisfies monotonicity (1) and strict monotonicity (2), and as
$\frac{d_{n}}{d_{n}(e_{0})}$ has a finite positive accumulation point $d$ on
the connected component $\tilde{G}$ containing $e_{0}$, we obtain that
$g=\text{log}\,d$ is a finite accumulation point of $P^{n}f-P^{n}f(e_{0})$.
Then by Theorem 2, we know that $P^{n}f-P^{n}f(e_{0})$ converges to $g$.
Moreover, we know $Pg=g+c$ and $\tilde{P}d=\tilde{c}d$. That is, its curvature
is a constant. ∎

###  4.2. The gradient estimate for resolvents of nonlinear Laplace.

It is shown in [35] that a lower Ollivier curvature bound is equivalent to a
gradient estimate for the continuous time heat equation. In [24, 32, 33, 9,
45, 14], the gradient estimates have been proved under Bakry-Emery curvature
bounds. In [5], the authors proved that non-negative sectional curvature
implies a logarithmic gradient estimate. Gradient estimates of the discrete
random walk $id+\varepsilon\Delta$ have been proved in [3, 25, 15]. In [17,
Theorem 5.2.], the authors show a gradient estimate for the coarse Ricci
curvature defined on hypergraphs.

Here we modify the definition of Ollivier Ricci curvature and prove the
Lipschitz decay for nonlinear parabolic equations. On a locally finite
weighted graph $G=(V,w,m,d_{0})$ with the combinatorial distance $d_{0}$,
define

$\Delta_{\phi}f(x)\coloneqq\underset{}{\underset{y}{\sum}\frac{w(x,y)}{m(x)}\phi(f(y)-f(x)),}$

where $\phi:\mathbb{R}\rightarrow\mathbb{R}$, is odd, increasing, and either
convex or concave on $\mathbb{R}_{+}$. Recall the transport plan set

$\Pi\coloneqq\left\\{\pi:B_{1}(x)\times
B_{1}(y)\to[0,\infty):\begin{array}[]{c}\underset{x^{\prime}\in
B_{1}(x)}{\sum}\pi(x^{\prime},y^{\prime})=\frac{w(y,y^{\prime})}{m(y)}\text{
for all }y^{\prime}\in S_{1}(y),\\\ \underset{y^{\prime}\in
B_{1}(y)}{\sum}\pi(x^{\prime},y^{\prime})=\frac{w(x,x^{\prime})}{m(x)}\text{
for all }x^{\prime}\in S_{1}(x).\end{array}\right\\}.$

Then modify the curvature as

(4.1)
$\hat{k}_{\phi}(x,y)\coloneqq\underset{\pi_{\phi}\in\Pi_{\phi}}{\text{sup}}\underset{x^{\prime},y^{\prime}\in
B_{1}(x)\times
B_{1}(y)}{\sum}\pi_{\phi}(x^{\prime},y^{\prime})\left(1-\frac{d_{0}(x^{\prime},y^{\prime})}{d_{0}(x,y)}\right),$

where

$\Pi_{\phi}\coloneqq\left\\{\pi_{\phi}\in\Pi:\begin{array}[]{c}\pi_{\phi}(x^{\prime},y^{\prime})=0\text{
if }x^{\prime}=y^{\prime}\text{ for convex $\phi$},\\\
\pi_{\phi}(x^{\prime},y^{\prime})=0\text{ if }x^{\prime}\neq x,y^{\prime}\neq
y\text{ and }d_{0}(x^{\prime},y^{\prime})=2\text{ for concave
$\phi$.}\end{array}\right\\}.$

Then we give the gradient estimate for resolvents of nonlinear Laplace.

######  Theorem 7.

On a locally finite weighted graph $G=(V,w,m,d_{0})$ with combinatorial
distance $d_{0}$, if the modified curvature has a lower bound
$\underset{x,y}{\text{inf}}\,\hat{k}(x,y)\geq K$, then the resolvent
$J_{\epsilon}f=\left(id-\epsilon\Delta_{\phi}\right)^{-1}f$ satisfies the
Lipschitz decay

$Lip(J_{\epsilon}f)\leq
Lip(f)\left(1+\epsilon\left(Lip(f)\right)^{-1}\phi(Lip(f))K\right)^{-1},$

where $\epsilon$ is small enough such that
$1+\epsilon\left(Lip(f)\right)^{-1}\phi(Lip(f))K$ is positive.

###### Proof.

For any $x\sim y$, suppose $Lip(f)=C$, $f(y)=C$ and $f(x)=0$, then for any
$\pi_{\phi}(x^{\prime},y^{\prime})$ satisfying the conditions in (4.1),

$\Delta_{\phi}f(x)-\Delta_{\phi}f(y)=\underset{x^{\prime},y^{\prime}}{\sum}\pi_{\phi}(x^{\prime},y^{\prime})\left[\phi(f(x^{\prime})-f(x))-\phi(f(y^{\prime})-f(y))\right].$

If $d_{0}(x^{\prime},y^{\prime})=1$, then

$f(x^{\prime})-f(x)\geq f(y^{\prime})-C-(f(y)-C)=f(y^{\prime})-f(y).$

Since $\phi$ is increasing, we know

$\phi(f(x^{\prime})-f(x))-\phi(f(y^{\prime})-f(y))\geq
0=d_{0}(x,y)-d_{0}(x^{\prime},y^{\prime}).$

If $d_{0}(x^{\prime},y^{\prime})=2$, and $x^{\prime}\neq x$ and
$y^{\prime}\neq y$, then $f(x^{\prime})-f(x)\geq-C$ and
$f(y^{\prime})-f(y)\leq C$, and $f(y^{\prime})-f(x^{\prime})\leq C$. For
convex $\phi$, such as $p$-Laplace ($p\geq 2$), we have

$\phi(f(x^{\prime})-f(x))-\phi(f(y^{\prime})-f(y))\geq-\phi(C).$

If $d_{0}(x^{\prime},y^{\prime})=2$ and either $x^{\prime}=x$ or
$y^{\prime}=y$, then

$\phi(f(x^{\prime})-f(x))-\phi(f(y^{\prime})-f(y))\geq-\phi(C).$

If $d_{0}(x^{\prime},y^{\prime})=0$, then $0\leq
f(x^{\prime})=f(y^{\prime})\leq C$. And for concave $\phi$, such as
$p$-Laplace ($1<p<2$), we have

$\phi(f(x^{\prime})-f(x))-\phi(f(y^{\prime})-f(y))=\phi(f(x^{\prime}))-\phi(f(x^{\prime})-C)\geq\phi(C).$

Hence,

$\displaystyle\Delta_{\phi}f(x)-\Delta_{\phi}f(y)$ $\displaystyle=$
$\displaystyle\underset{x^{\prime},y^{\prime}}{\sum}\pi_{\phi}(x^{\prime},y^{\prime})\left[\phi(f(x^{\prime})-f(x))-\phi(f(y^{\prime})-f(y))\right]$
$\displaystyle=$
$\displaystyle\left(\underset{d(x^{\prime},y^{\prime})=1}{\sum}+\underset{d(x^{\prime},y^{\prime})=2}{\sum}+\underset{d(x^{\prime},y^{\prime})=0}{\sum}\right)\pi_{\phi}(x^{\prime},y^{\prime})\left[\phi(f(x^{\prime})-f(x))-\phi(f(y^{\prime})-f(y))\right]$
$\displaystyle\geq$
$\displaystyle\phi(C)\underset{x^{\prime},y^{\prime}}{\sum}\pi_{\phi}(x^{\prime},y^{\prime})\left[d_{0}(x,y)-d_{0}(x^{\prime},y^{\prime})\right].$

That is,

$\Delta_{\phi}f(x)-\Delta_{\phi}f(y)\geq\phi(C)\hat{k}(x,y)d_{0}(x,y)\geq\phi(C)K.$

And

$(id-\epsilon\Delta_{\phi})f(y)-(id-\epsilon\Delta_{\phi})f(x)\geq
C+\epsilon\phi(C)K.$

For $g\in\mathbb{R}^{V}$, let $Lip(f)=\mid\nabla
f\mid_{\infty}\coloneqq\underset{x\sim y}{\text{sup}}\mid\nabla_{xy}f\mid$,
then by the definition of $J_{\epsilon}$,

$\displaystyle\underset{\mid\nabla g\mid_{\infty}\leq c}{\text{sup}}\mid\nabla
J_{\epsilon}g\mid_{\infty}$ $\displaystyle=\underset{\mid\nabla
g\mid_{\infty}\leq
c}{\text{sup}}\mid\nabla\left(id-\epsilon\Delta_{\phi}\right)^{-1}g\mid_{\infty}$
$\displaystyle=\underset{\mid\nabla\left(id-\epsilon\Delta_{\phi}\right)h\mid_{\infty}\leq
c}{\text{sup}}\mid\nabla h\mid_{\infty}$
$\displaystyle=\left(\underset{\mid\nabla h\mid_{\infty}\geq
c^{-1}}{\text{inf}}\mid\nabla(id-\epsilon\Delta_{\phi})h\mid_{\infty}\right)^{-1}.$

Thus, we know $Lip(J_{\epsilon}f)\leq
C^{2}\left(C+\epsilon\phi(C)K\right)^{-1}=C\left(1+\epsilon
C^{-1}\phi(C)K\right)^{-1}.$ ∎

######  Remark 5.

Since $\Delta_{1}$ is a set-valued function, we can not get the Lipschitz
decay property by Theorem 7 directly. Since the energy functional
$\mathscr{E}_{p}(f)$ is uniformly continuous with respect to $p$, which means
that for any $\delta>0$, there exists $p$ only depending on $\delta$ such that
for all $f_{0}\in\mathbb{R}^{V}$,

$\underset{f:\left\|f-f_{0}\right\|{}_{\infty}\leq
1}{sup}\mid\mathscr{E}_{p}(f)-\mathscr{E}_{1}(f)\mid\leq\delta.$

Then for fixed $f$ and $\epsilon$, the resolvent
$J_{\epsilon}^{p}f=\underset{g\in\mathbb{R}^{V}}{\text{argmin}}\left\\{\mathscr{E}_{p}(g)+\frac{1}{2\epsilon}\left\|g-f\right\|_{2}^{2}\right\\}$
is also continuous with respect to $p$. Hence by the Lipschitz decay property
of $J_{\epsilon}^{p}$ for $p>1$, we can get the Lipschitz decay for
$J_{\epsilon}^{1}$.

###  4.3. The convergence of Laplacian separation flow.

Recall that the extremal 1-Lipschitz extension operator $S$ is defined as
$S:\mathbb{R}^{K}\to\mathbb{R}^{V}$,

$Sf(x)\coloneqq\begin{cases}\begin{array}[]{c}f(x):\\\ \underset{y\in
K}{\text{min}}\left(f(y)+d(x,y)\right):\\\ \underset{y\in
K}{\text{max}}\left(f(y)-d(x,y)\right):\end{array}&\begin{array}[]{c}x\in
K,\\\ x\in Y,\\\ x\in X,\end{array}\end{cases}$

where $d$ is the graph distance on $G$. Then $S(Lip(1,K))\subseteq Lip(1,V)$.
In [15], it is proven via elliptic methods that there exists some $g$ with
$\Delta Sg=\text{const}$. Here we give the parabolic flow
$(id+\epsilon\Delta)S$, and show that this converges to the constant Laplacian
solution, assuming non-negative Ollivier Ricci curvature.

Theorem 5. For a locally finite graph $G$ with non-negative Ollivier
curvature, let $x_{0}\in V$ and
$P\coloneqq\left((id+\epsilon\Delta)S\right)\mid_{K}$, where $\epsilon$ is
small enough such that $\text{diag}(id+\epsilon\Delta)$ is positive. Then for
all $f\in Lip(1,K)$, there exists $g\in Lip(1,K)$ such that
$P^{n}f-P^{n}f(x_{0})$ converges to $g$ and $\Delta Sg\equiv\text{const}$ on
$K$.

###### Proof.

We can check that $P$ satisfies monotonicity (1), strict monotonicity (2), and
constant additivity (4). Since the non-negative Ollivier Ricci curvature
implies Lipschitz decay property of $P$, i.e., the range of $P$ is $Lip(1,K)$,
then there is a finite accumulation point $g$ of $f_{n}=P^{n}f-P^{n}f(x_{0})$.
By Theorem 2, we can get the convergence and $g$ is a stationary point, that
is, $\Delta Sg\equiv\text{const}$ on $K$. ∎

Next, we want to generalize the result to non-linear cases. For $p\geq 1$, the
resolvent operator of $p$-Laplace operator $\Delta_{p}$ is defined as
$J_{\epsilon}=\left(id-\epsilon\Delta_{p}\right)^{-1}$for $\epsilon>0$. Then
$J_{\epsilon}$ is monotone [41, Proposition 12.19]. And the following lemma
states that the resolvent $J_{\epsilon}$ satisfying the strict monotonicity
property (2).

######  Lemma 3.

If $f\geq g+\delta\mid V\mid 1_{x}$, where $1_{x}(x)=1$ and $1_{x}(y)=0$ for
$y\neq x$, then $J_{\epsilon}f(x)\geq J_{\epsilon}g(x)+\delta.$

###### Proof.

Since $J_{\epsilon}$ is monotone, which means $\left\langle
J_{\epsilon}f-J_{\epsilon}g,f-g\right\rangle\geq 0.$ Take
$f=g+\delta\left(\mid V\mid 1_{x}-1\right)$, then $\left\langle
f-g,1\right\rangle=0$. By the monotone property,

$\left\langle J_{\epsilon}f-J_{\epsilon}g,\delta\left(\mid V\mid
1_{x}-1\right)\right\rangle\geq 0,$

which implies $\mid
V\mid\left(J_{\epsilon}f-J_{\epsilon}g\right)(x)\geq\left\langle
J_{\epsilon}f-J_{\epsilon}g,1\right\rangle=0.$ And set
$\tilde{f}=\delta+f=g+\delta\mid V\mid 1_{x}$ which satisfies $\tilde{f}\geq
g+\delta\mid V\mid 1_{x}$, then

$J_{\epsilon}\tilde{f}(x)=\delta+J_{\epsilon}f(x)\geq\delta+J_{\epsilon}g(x).$

This finishes the proof. ∎

Recall that a new curvature $\hat{k}_{\phi}(x,y)$ is defined in (4.1), whose
transport plans forbid 3-cycles for convex $\phi$ on $\mathbb{R}_{+}$ and
forbid 5-cycles for concave $\phi$ on $\mathbb{R}_{+}$.

Then we can prove there exists a stationary point $g$ such that
$g\in\Delta_{p}Sh$ and $g\equiv\text{const}$ on $K$.

Theorem 6. For a locally finite graph $G=(V,w,m,d_{0})$ with a non-negative
modified curvature $\hat{k}_{\phi}$, let $x_{0}\in V$ and
$P\coloneqq\left((id+\epsilon\Delta)S\right)\mid_{K}$, where $\epsilon$ is
small enough such that $\text{diag}(id+\epsilon\Delta)$ is positive. Then for
all $f\in Lip(1,K)$, there exists $\tilde{f}\in Lip(1,K)$ such that
$P^{n}f-P^{n}f(x_{0})$ converges to $\tilde{f}$. Moreover, there exist
$h,g\in\mathbb{R}^{V}$ such that $g\in\Delta_{p}Sh$ and $g\mid_{X}\geq
g\mid_{K}\equiv\text{const}\geq g\mid_{Y}$.

###### Proof.

By Lemma 3 we know $J_{\epsilon}$ satisfies strict monotonicity property. It
is also constant additive by the definition of resolvent $J_{\epsilon}$, then
$P$ also satisfies the same property. For the non-negative curvature
$\hat{k}_{\phi}$ defined as (4.1), by the gradient estimate of Theorem 7, the
range of $P$ still is $Lip(1,K)$. Then there is an accumulation point at
infinity. Hence by Theorem 2, there exists $\tilde{f}\in Lip(1,K)$ such that
$P\tilde{f}=\tilde{f}+\text{const}$, which implies that

(4.2) $SJ_{\epsilon}S\tilde{f}=S\tilde{f}+\text{const}.$

Define $h_{\epsilon}\coloneqq J_{\epsilon}S\tilde{f}$ and substitute it into
the above formula (4.2), then we can get
$\Delta_{p}h_{\epsilon}=\text{const}$. Note that $h_{\epsilon}\neq
Sh_{\epsilon}$, but we claim that
$\left\|h_{\epsilon}-Sh_{\epsilon}\right\|_{\infty}\leq c\epsilon$ for some
constant $c$. Since

$\left\|h_{\epsilon}-S\tilde{f}\right\|_{\infty}=\left\|J_{\epsilon}S\tilde{f}-S\tilde{f}\right\|_{\infty}\leq\epsilon\left\|\Delta_{p}S\tilde{f}\right\|_{\infty}\leq\epsilon\underset{x}{\text{
max}}deg(x),$

and it also holds on $K$, that is,

$\left\|Sh_{\epsilon}-SS\tilde{f}\right\|_{\infty}=\left\|Sh_{\epsilon}-S\tilde{f}\right\|_{\infty}\leq\epsilon.$

So by the triangle inequality, we get
$\left\|h_{\epsilon}-Sh_{\epsilon}\right\|_{\infty}\leq c\epsilon.$ Then we
get $h_{\epsilon}\to h$ for some subsequence as $\epsilon\to 0$ by the
compactness, and $h=Sh$. Take a subsequence $\left\\{g_{\epsilon}\right\\}$
such that $g_{\epsilon}\in\Delta_{p}h_{\epsilon}$ and
$g_{\epsilon}\mid_{X}\geq g_{\epsilon}\mid_{K}\equiv\text{const}\geq
g_{\epsilon}\mid_{Y}$ and $g_{\epsilon}\to g.$ By the continuity, we know
$g\in\Delta_{p}Sh$ and $g\mid_{X}\geq g\mid_{K}\equiv\text{const}\geq
g\mid_{Y}$. ∎

###  4.4. The nonlinear Dirichlet form.

In the theory of nonlinear Dirichlet form, one has a correspondence between
such forms, semigroups, resolvents, and operators satisfying suitable
conditions. Since the assumptions of our theorems fit well in the nonlinear
Dirichlet form theory, we can apply our theorems to study the long time
behavior of associated continuous semigroups. First, we recall the definition
of the nonlinear Dirichlet form [8].

######  Definition 2.

Let $\mathscr{E}:$ $\mathbb{R}^{N}\to[0,\infty]$ be a convex and lower
semicontinuous functional with dense effective domain. Then, the subgradient
$-\partial\mathscr{E}$ generates a strongly continuous contraction semigroup
$T$, that is, $u(t)=T_{t}u_{0}$ satisfies

$\begin{cases}\begin{array}[]{c}0\in\frac{du}{dt}(t)+\partial\mathscr{E}(u(t)),\\\
u(0)=u_{0}\end{array}\end{cases}$

pointwise for almost every $t\geq 0$. We call $\mathscr{E}$ a Dirichlet form
if the associated strongly continuous contraction semigroup $T$ is sub-
Markovian, which means $T$ is order preserving and $L^{\infty}$ contractive,
that is, for every $u,v\in\mathbb{R}^{N}$ and every $t\geq 0$,

$u\leq v\Rightarrow T_{t}u\leq T_{t}v$

and

$\left\|T_{t}u-T_{t}v\right\|_{\infty}\leq\left\|u-v\right\|_{\infty}.$

For another definition of the nonlinear Dirichlet form in [19], it satisfies
the following lemma.

######  Lemma 4.

[19, Lemma 1.1] For a nonlinear Dirichlet form $\mathscr{E}$, if
$f\in\mathbb{R}^{N}$ and $a,\lambda\in\mathbb{R}$, then

(4.3) $\begin{array}[]{c}\mathscr{E}(\lambda f)=\lambda^{2}\mathscr{E}(f),\\\
\mathscr{E}(f+a)=\mathscr{E}(f).\end{array}$

Then we can apply Theorem 2 to obtain the following convergence result with
the accumulation point assumption.

######  Theorem 8.

For a nonlinear Dirichlet form $\mathscr{E}$ with property (4.3), if the
semigroup $T_{t}^{n}f$ has an accumulation point at infinity (8) and its
associated generator is bounded, then $T_{t}^{n}f$ converges.

###### Proof.

Define the Markov chain as $P\coloneqq T_{t}$. By the definition of a
Dirichlet form, we know $P$ satisfying monotonicity (1) and non-expansion (5).
And the property (4.3) induces the constant additivity (4) of $P$. Since the
associated generator is bounded, then $P$ satisfies strict monotonicity (2).
Then by the assumption of accumulation points at infinity, we can get the
convergence result by Theorem 2. ∎

######  Remark 6.

(a) In the nonlinear Dirichlet form setting of [19], if we assume the
associated semigroup satisfying sub-Markovian property, then we can also apply
Theorem 2 to obtain convergence results with the accumulation point at
infinity assumption (8).

(b) As we mentioned before, we can study the long-time behavior of the
resolvents of $p$-Laplace and hypergraph Laplace [17].

(c) Note that our nonlinear Markov chain setting is more general. Since in the
nonlinear Dirichlet form setting, the associated generator is required for a
kind of reversibility, while our Markov chain does not require it. Moreover,
our underlying space is more general than the nonlinear Dirichlet form
setting, which requires $L^{2}$ space.

###  4.5. The nonlinear Perron–Frobenius theory.

The classical Perron–Frobenius theorem shows that a nonnegative matrix has a
nonnegative eigenvector associated with its spectral radius, and if the matrix
is irreducible then this nonnegative eigenvector can be chosen strictly
positive. And there are many nonlinear generalizations.

For example, in [29], the author lets $K$ be a proper cone in
$\mathbb{R}^{N}$, that is, $\alpha K\subset K$ for all
$\alpha\in\mathbb{R}_{+}$, it is closed and convex, $K-K=\mathbb{R}^{N}$, and
$K\cap-K=\left\\{0\right\\}$. Then $K$ induces a partial ordering $x\leq y$ on
$K$ defined by $x-y\in K$. Consider maps satisfying:

(M1) $\Lambda:K\to K,K{{}^{\circ}}\to K{{}^{\circ}}.$

(M2) $\Lambda(\alpha x)=\alpha\Lambda(x)$ for all $\alpha\geq 0$ and $x\in K$
.

(M3) $x\leq y$ implies $\Lambda(x)\leq\Lambda(y)$ for all $x,y\in K$.

(M4) $\Lambda$ is locally Lipschitz continuous near $0$.

Sufficient conditions for the existence and uniqueness of eigenvectors in the
interior of a cone $K$ are developed even when eigenvectors at the boundary of
the cone exist [29, Theorem 25, Theorem 28].

######  Theorem 9.

Let $K$ be the positive function set $\mathbb{R}_{>0}^{N}$ and

$Pf\coloneqq\frac{1}{2}\text{log}\left(\text{exp}(f)\cdot\Lambda\left(\text{exp}(f)\right)\right),$

where $\Lambda$ is defined as above. If $P^{n}f$ has an accumulation point at
infinity (8), then $P^{n}f$ converges.

###### Proof.

Since $\Lambda$ satisfies (M2) and (M3), then
$\tilde{P}f\coloneqq\text{log}\left(\Lambda\left(\text{exp}(f)\right)\right)$
satisfies constant additivity (4) and monotonicity (1). And

$Pf=\frac{f+\tilde{P}f}{2}=\frac{1}{2}\text{log}\left(\text{exp}(f)\cdot\Lambda\left(\text{exp}(f)\right)\right)$

satisfies constant additivity (4) and strict monotonicity (2). Then we can
apply Theorem 2 to get the convergence result with the accumulation points
assumption. ∎

Then we introduce another nonlinear generalization that might be applied to a
specific case which is relevant to the Ollivier Ricci flow. In [2], the author
considers maps $f_{\mathcal{K}}(v)=\text{min}_{A\in\mathcal{K}}Av$, where
$\mathcal{K}$ is a finite set of nonnegative matrices and “min” means
component-wise minimum. In particular, he shows the existence of nonnegative
generalized eigenvectors of $f_{\mathcal{K}}$, gives necessary and sufficient
conditions for the existence of a strictly positive eigenvector of
$f_{\mathcal{K}}$, which is applicable to our Ollivier Ricci flow (1.2) and it
treats the non-connected case. However, it does not give the long-term
behavior.

##  5\. The Ollivier Ricci curvature of nonlinear Markov chains

In this section, we introduce a definition of Ollivier Ricci curvature of
nonlinear Markov chains according to the Lipschitz decay property. Then we can
get the convergence results for the nonlinear Markov chain with a nonnegative
Ollivier Ricci curvature. And we can also define the Laplacian separation flow
of a nonlinear Markov chain with $Ric_{1}(P,d)\geq 0$. Then several examples
show that the definition is consistent with the classical Ollivier Ricci
curvature (3.1), sectional curvature [5], coarse Ricci curvature on
hypergraphs [17] and the modified Ollivier Ricci curvature $\hat{k}_{p}$ for
$p$-Laplace (1.3).

######  Definition 3.

Let $P:\mathbb{R}^{V}\to\mathbb{R}^{V}$ be a nonlinear Markov chain with (1)
monotonicity, (2) strict monotonicity and (4) constant additivity, and let
$d:V^{2}\to[0,+\infty)$ be the distance function. For $r\geq 0$, define

$Ric_{r}(P,d)\coloneqq 1-\underset{Lip(f)\leq
r}{\text{sup}}\frac{Lip(Pf)}{r},$

i.e., if $Lip(f)=r$, then $Lip(Pf)\leq(1-Ric_{r})Lip(f)$.

By Theorem 2, we can get the following corollary.

######  Corollary 1.

Let $r\geq 0$. Assume $(P,d)$ is a nonlinear Markov chain with $Ric_{r}\geq
0$. Let $x_{0}\in V$. Then for all $f$ satisfying $Lip(f)\leq r$, there exists
$g\in\mathbb{R}^{V}$ such that $P^{n}f-P^{n}f(x_{0})\to g$ and
$P^{n}f-P^{n-1}f\to\text{const}$ as $n\to+\infty$. Particularly,
$Pg=g+\text{const.}$

###### Proof.

By the definition of $Ric_{r}\geq 0$, we can get the accumulation point at
infinity (8) as $Lip(P^{n}f)\leq r$ for all $n$, and by compactness. Then
apply Theorem 2, we can get the results. ∎

Then we want to define the Laplacian separation flow on a nonlinear Markov
chain $(P,d)$ with $Ric_{1}(P,d)\geq 0$. Assume $V=X\sqcup K\sqcup Y$ such
that $d(x,y)=\underset{z\in K}{\text{inf}}d(x,z)+d(z,y)$ for all $x\in X$ and
$y\in Y$. Intuitively that means that $K$ separates $X$ from $Y$. Recall the
extremal 1-Lipschitz extension operator defined as
$S:\mathbb{R}^{K}\to\mathbb{R}^{V}$,

$Sf(x)\coloneqq\begin{cases}\begin{array}[]{c}f(x):\\\ \underset{y\in
K}{\text{min}}\left(f(y)+d(x,y)\right):\\\ \underset{y\in
K}{\text{max}}\left(f(y)-d(x,y)\right):\end{array}&\begin{array}[]{c}x\in
K,\\\ x\in Y,\\\ x\in X.\end{array}\end{cases}$

Then $S(Lip(1,K))\subseteq Lip(1,V)$. And we can get the following lemma.

######  Lemma 5.

Assume $(P,d)$ is a nonlinear Markov chain with $Ric_{1}(P,d)\geq 0$. Define
$\tilde{P}:\mathbb{R}^{K}\to\mathbb{R}^{K}$ as
$\tilde{P}f=\left(PSf\right)\mid_{K}$. Then $Ric_{1}(\tilde{P},d\mid_{K\times
K})\geq 0$.

###### Proof.

Since $S(Lip(1,K))\subseteq Lip(1,V)$, i.e., $Sf\in Lip(1,V)$, and by the
definition of $Ric_{1}(P,d)\geq 0$, we can get
$Ric_{1}(\tilde{P},d\mid_{K\times K})\geq 0$. ∎

Combining Corollary 1, we can get the Laplacian separation result on the
nonlinear Markov chain.

######  Corollary 2.

Let $(P,d)$ is a nonlinear Markov chain with $V=X\sqcup K\sqcup Y$. Assume
$Ric_{1}(P,d)\geq 0$. Then there exists $f\in\mathbb{R}^{V}$ and
$C\in\mathbb{R}$ such that $f=Sf\coloneqq S(f\mid_{K})$ and

$\Delta f\begin{cases}\begin{array}[]{c}=C,\>\text{on }K,\\\ \leq C,\>\text{on
}Y,\\\ \geq C,\>\text{on }X,\end{array}\end{cases}$

where $\Delta\coloneqq P-id$.

###### Proof.

By Corollary 1, there exists $g\in Lip(1,K)$ such that on $K$,

$PSg=g+\text{const}.$

Let $f=Sg$. Clearly, $f=S(f\mid_{K})$, and on $K$,

$Pf=f+\text{const},$

i.e., $\Delta f=C$. Moreover,

$SPf=SPSg=Sg+\text{const}=f+\text{const}.$

Then on $X$, we have $SPf\leq Pf$ as $S$ is the minimum Lipschitz extension on
$X$. Hence, $Pf\geq f+C$, i.e., $\Delta f\geq C$ on $X$. Similarly, $\Delta
f\leq C$ on $Y$, finishing the proof. ∎

Next, the following examples show that our Ollivier Ricci curvature definition
is consistent with other settings.

######  Example 1.

(a) Let $P$ be a linear Markov chain, then $Ric_{r}$ is the classical Ollivier
Ricci curvature $\kappa$, see definition (3.1).

(b) Let $\tilde{P}$ be a linear Markov chain and define
$P(\cdot)=\text{log}\tilde{P}\text{exp}(\cdot)$, then $Ric_{r}(P,d)\geq 0$ for
all $r\geq 0$ if the sectional curvature $\kappa_{sec}\geq 0$, see [5].

(c) Let $P$ be the resolvent of hypergraph Laplace, then $Ric_{r}\geq 0$ for
all $r\geq 0$ if the coarse Ricci curvature of hypergraphs $\kappa\geq 0$, see
[17].

(d) Let $P$ be the resolvent of $p$-Laplace, then $Ric_{r}\geq 0$ for all
$r\geq 0$ if the modified Ollivier Ricci curvature of $p$-Laplace
$\hat{k}_{p}\geq 0$, see definition (1.3) in introduction.

######  Remark 7.

For the above examples (a)-(d) with $Ric_{1}(P,d)\geq 0$, by Corollary 2 the
Laplacian separation flow can be defined respectively.

$\mathbf{\boldsymbol{\mathbf{Acknowledgements}\mathbf{}\text{:}}}$ The authors
would like to thank Jürgen Jost, Bobo Hua and Tao Wang for helpful discussions
and suggestions.

## References

  * [1] Shuliang Bai, Yong Lin, Linyuan Lu, Zhiyu Wang, and Shing-Tung Yau.  Ollivier ricci-flow on weighted graphs.  arXiv: 2010.01802, 2020.
  * [2] Ievgen Bondarenko.  Dynamics of piecewise linear maps and sets of nonnegative matrices.  Linear Algebra Appl., 431(5-7):495–510, 2009.
  * [3] D. P. Bourne, D. Cushing, S. Liu, F. Münch, and N. Peyerimhoff.  Ollivier-Ricci idleness functions of graphs.  SIAM J. Discrete Math., 32(2):1408–1424, 2018.
  * [4] O. A. Butkovsky.  On ergodic properties of nonlinear Markov chains and stochastic McKean-Vlasov equations.  Theory Probab. Appl., 58(4):661–674, 2014.
  * [5] Pietro Caputo, Florentin Munch, and Justin Salez.  Entropy and curvature: beyond the peres-tetali conjecture.  arXiv: 2401.17148, 2024.
  * [6] K. C. Chang.  Spectrum of the 1-Laplacian and Cheeger’s constant on graphs.  J. Graph Theory, 81(2):167–207, 2016.
  * [7] Bennett Chow and Feng Luo.  Combinatorial Ricci flows on surfaces.  J. Differential Geom., 63(1):97–129, 2003.
  * [8] Burkhard Claus.  Nonlinear Dirichlet Forms.  Dissertation, Dresden, Technische Universität Dresden, 2021.
  * [9] Dominik Dier, Moritz Kassmann, and Rico Zacher.  Discrete versions of the li-yau gradient estimate.  Annali Scuola Normale Superiore-Classe di Scienze, pages 691–744, 2021.
  * [10] Matthias Erbar and Jan Maas.  Ricci curvature of finite Markov chains via convexity of the entropy.  Arch. Ration. Mech. Anal., 206(3):997–1038, 2012.
  * [11] Forman.  Bochner’s method for cell complexes and combinatorial ricci curvature.  Discrete & Computational Geometry, 29:323–374, 2003.
  * [12] Xianfeng Gu, Ren Guo, Feng Luo, Jian Sun, and Tianqi Wu.  A discrete uniformization theorem for polyhedral surfaces II.  J. Differential Geom., 109(3):431–466, 2018.
  * [13] Xianfeng David Gu, Feng Luo, Jian Sun, and Tianqi Wu.  A discrete uniformization theorem for polyhedral surfaces.  J. Differential Geom., 109(2):223–256, 2018.
  * [14] Paul Horn, Yong Lin, Shuang Liu, and Shing-Tung Yau.  Volume doubling, poincaré inequality and gaussian heat kernel estimate for non-negatively curved graphs.  Journal für die reine und angewandte Mathematik (Crelles Journal), 2019(757):89–130, 2019.
  * [15] Bobo Hua and Florentin Münch.  Every salami has two ends.  arXiv: 2105.11887, 2021.
  * [16] Bobo Hua, Florentin Münch, and Haohang Zhang.  Some variants of discrete positive mass theorems on graphs.  arXiv: 2307.08334, 2023.
  * [17] MasaHiro Ikeda, Yu Kitabeppu, Yuuki Takai, and Takato Uehara.  Coarse ricci curvature of hypergraphs and its generalization.  arXiv: 2102.00698, 2021.
  * [18] Jürgen Jost.  Riemannian geometry and geometric analysis.  Universitext. Springer-Verlag, Berlin, 1995.
  * [19] Jürgen Jost.  Nonlinear Dirichlet forms.  In New directions in Dirichlet forms, volume 8 of AMS/IP Stud. Adv. Math., pages 1–47. Amer. Math. Soc., Providence, RI, 1998.
  * [20] Jürgen Jost and Shiping Liu.  Ollivier’s Ricci curvature, local clustering and curvature-dimension inequalities on graphs.  Discrete Comput. Geom., 51(2):300–322, 2014.
  * [21] Vassili N Kolokoltsov.  Nonlinear Markov processes and kinetic equations, volume 182.  Cambridge University Press, 2010.
  * [22] Vassili N. Kolokoltsov and Oleg A. Malafeyev.  Many agent games in socio-economic systems: corruption, inspection, coalition building, network growth, security.  Springer Series in Operations Research and Financial Engineering. Springer, Cham, 2019.
  * [23] David A. Levin and Yuval Peres.  Markov chains and mixing times.  American Mathematical Society, Providence, RI, second edition, 2017.  With contributions by Elizabeth L. Wilmer, With a chapter on “Coupling from the past” by James G. Propp and David B. Wilson.
  * [24] Yong Lin and Shuang Liu.  Equivalent properties of CD inequalities on graphs.  Acta Math. Sinica (Chinese Ser.), 61(3):431–440, 2018.
  * [25] Yong Lin, Linyuan Lu, and Shing-Tung Yau.  Ricci curvature of graphs.  Tohoku Math. J. (2), 63(4):605–627, 2011.
  * [26] Yong Lin and Shing-Tung Yau.  Ricci curvature and eigenvalue estimate on locally finite graphs.  Math. Res. Lett., 17(2):343–356, 2010.
  * [27] Peter Lindqvist.  Notes on the $p$-Laplace equation, volume 102 of Report. University of Jyväskylä Department of Mathematics and Statistics.  University of Jyväskylä, Jyväskylä, 2006.
  * [28] H. P. McKean, Jr.  A class of Markov processes associated with nonlinear parabolic equations.  Proc. Nat. Acad. Sci. U.S.A., 56:1907–1911, 1966.
  * [29] Volker Metz.  Nonlinear Perron-Frobenius theory in finite dimensions.  Nonlinear Anal., 62(2):225–244, 2005.
  * [30] Alexander Mielke.  Geodesic convexity of the relative entropy in reversible Markov chains.  Calc. Var. Partial Differential Equations, 48(1-2):1–31, 2013.
  * [31] Isao Miyadera.  Nonlinear semigroups, volume 109.  American Mathematical Soc., 1992.
  * [32] Florentin Munch.  Li-Yau inequality on finite graphs via non-linear curvature dimension conditions.  J. Math. Pures Appl. (9), 120:130–164, 2018.
  * [33] Florentin Münch.  Li-yau inequality under $cd(0,n)$ on graphs.  arXiv preprint arXiv:1909.10242, 2019.
  * [34] Florentin Münch.  Ollivier curvature, isoperimetry, concentration, and log-sobolev inequalitiy.  arXiv: 2309.06493, 2023.
  * [35] Florentin Münch and Radosław K. Wojciechowski.  Ollivier Ricci curvature for general graph Laplacians: heat equation, Laplacian comparison, non-explosion and diameter bounds.  Adv. Math., 356:106759, 45, 2019.
  * [36] Berenice Anne Neumann.  Nonlinear Markov chains with finite state space: invariant distributions and long-term behaviour.  J. Appl. Probab., 60(1):30–44, 2023.
  * [37] Chien-Chun Ni, Yu-Yao Lin, Jie Gao, and Xianfeng Gu.  Network alignment by discrete Ollivier-Ricci flow.  In Graph drawing and network visualization, volume 11282 of Lecture Notes in Comput. Sci., pages 447–462. Springer, Cham, 2018.
  * [38] Chien-Chun Ni, Yu-Yao Lin, Feng Luo, and Jie Gao.  Community detection on networks with ricci flow.  Scientific reports, 9(1):9984, 2019.
  * [39] Yann Ollivier.  Ricci curvature of metric spaces.  C. R. Math. Acad. Sci. Paris, 345(11):643–646, 2007.
  * [40] Yann Ollivier.  Ricci curvature of Markov chains on metric spaces.  J. Funct. Anal., 256(3):810–864, 2009.
  * [41] R Tyrrell Rockafellar and Roger J-B Wets.  Variational analysis, volume 317.  Springer Science & Business Media, 2009.
  * [42] Mansoor Saburov.  Ergodicity of nonlinear Markov operators on the finite dimensional space.  Nonlinear Anal., 143:105–119, 2016.
  * [43] Michael Schmuckenschläger.  Curvature of nonlocal Markov generators.  In Convex geometric analysis (Berkeley, CA, 1996), volume 34 of Math. Sci. Res. Inst. Publ., pages 189–197. Cambridge Univ. Press, Cambridge, 1999.
  * [44] Richard Serfozo.  Basics of applied stochastic processes.  Springer Science & Business Media, 2009.
  * [45] Frederic Weber and Rico Zacher.  Li–yau inequalities for general non-local diffusion equations via reduction to the heat kernel.  Mathematische Annalen, 385(1):393–419, 2023.