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]$, which was introduced by Bauer-Jost. In particular, when $t=1$ this is Ollivier's estimates $k\leq \lambda_1\leq \ldots \leq \lambda_{ N-1}\leq 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\leq 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.
Categories: math.CO math.DG math.MG math.PR