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

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 λ_1 \leq \cdots \leq λ_{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]$, which was introduced by Bauer-Jost. In particular, when $t=1$ this is Ollivier's estimates $k\le {\lambda }_1\le \dots \le {\lambda }_{N-1}\le 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\le 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.

20 pages, 1 figure

References in corpus (1)

• Ollivier's Ricci curvature, local clustering and curvature dimension inequalities on graphs

Cited by in corpus (3)

• Ollivier's Ricci curvature, local clustering and curvature dimension inequalities on graphs
• Volume Growth, Spectrum and Stochastic Completeness of Infinite Graphs
• An Analytical Approach for Insulin-like Growth Factor Receptor 1 and Mammalian Target of Rapamycin Blockades in Ewing Sarcoma