Mathematical Research Letters

Volume 19 (2012)

Number 6

Ollivier–Ricci curvature and the spectrum of the normalized graph Laplace operator

Pages: 1185 – 1205

DOI: http://dx.doi.org/10.4310/MRL.2012.v19.n6.a2

Authors

Frank Bauer (Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany)

Jürgen Jost (Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany; Santa Fe Institute for the Sciences of Complexity, Santa Fe, New Mexico, U.S.A.)

Shiping Liu (Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany; Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China)

Abstract

We prove the following estimate for the spectrum of the normalized Laplace operator $\Delta$ on a finite graph $G$,\[1- (1- k[t])^{\frac{1}{t}}\leq \lambda_1 \leq \cdots \leq \lambda_{N-1}\leq 1+ (1- k[t])^{\frac{1}{t}},\,\forall integers t\geq 1.\]Here $k[t]$ is a lower bound for the Ollivier–Ricci curvature on the neighborhood graph $G[t]$, which was introduced by Bauer–Jost. In particular, when $t=1$ this is Ollivier’s estimates $k\leq \lambda_1\leq \cdots \leq \lambda_{N-1}\leq 2-k$. For sufficiently large $t$, we show that, unless $G$ is bipartite, our estimates for $\lambda_1$ and $\lambda_{N-1}$ are always nontrivial and improve Ollivier’s estimates for all graphs with $k\leq 0$. By definition neighborhood graphs are weighted graphs which may have loops. To understand the Ollivier–Ricci curvature on neighborhood graphs, we generalize a sharp estimate of the Ricci curvature given by Jost–Liu to weighted graphs with loops and relate it to the relative local frequency of triangles and loops.

Full Text (PDF format)