MiS Preprint Repository

We prove the following estimate for the spectrum of the normalized Laplace operator $\mathrm{\Delta }$ on a finite graph $G$, $$1-(1-k[t]{)}^{\frac{1}{t}}\le {\lambda }_1\le \cdots \le {\lambda }_{N-1}\le 1+(1-k[t]{)}^{\frac{1}{t}},\mathrm{\forall }\text{integers}t\ge 1.$$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\le {\lambda }_1$ and a new sharp upper bound ${\lambda }_{N-1}\le 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\le {\lambda }_1$ for all graphs with $k\le 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.