Search

MiS Preprint Repository

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.

Received:
19.05.11
Published:
23.05.11
MSC Codes:
60J05, 51F99, 05C50
Keywords:
Ollivier-Ricci curvature, normalized graph Laplace operator, largest eigenvalue, random walk, neighborhood graph

Related publications

inJournal
2012 Repository Open Access
Frank Bauer, Jürgen Jost and Shiping Liu

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

In: Mathematical research letters, 19 (2012) 6, pp. 1185-1205