Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.

MiS Preprint

25/2011

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

Frank Bauer, Jürgen Jost and Shiping Liu

Abstract

We prove the following estimate for the spectrum of the normalized Laplace operator $\Delta$ on a finite graph $G$, \begin{equation*} 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 \,\,\text{integers}\,\, t\geq 1. \end{equation*}Here $k[t]$ is a lower bound for the Ollivier-Ricci curvature on the neighborhood graph $G[t]$ (here we use the convention $G[1]=G$), which was introduced by Bauer-Jost. In particular, when $t=1$ this is Ollivier's estimate $k\leq \lambda_1$ and a new sharp upper bound $\lambda_{N-1}\leq 2-k$ for the largest eigenvalue. Furthermore, we prove that for any $G$ when $t$ is sufficiently large, $1>(1- k[t])^{\frac{1}{t}}$ which shows that our estimates for $\lambda_1$ and $\lambda_{N-1}$ are always nontrivial and the lower estimate for $\lambda_1$ improves Ollivier's estimate $k\leq \lambda_1$ for all graphs with $k\leq 0$. By definition neighborhood graphs possess many loops. To understand the Ollivier-Ricci curvature on neighborhood graphs, we generalize a sharp estimate of the curvature given by Jost-Liu to graphs which may have loops and relate it to the relative local frequency of triangles and loops.