We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.
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.
