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 ∆ on a finite graph G, 1 − (1 − k[t]) 1t ≤ λ1 ≤ · · · ≤ λN−1 ≤ 1 + (1 − k[t]) 1t, ∀ integers t ≥ 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 ≤ λ1 and a new sharp upper bound λN−1 ≤ 2 − k for the largest eigenvalue. Furthermore, we prove that for any G when t is sufficiently large, 1> (1 − k[t]) 1t which shows that our estimates for λ1 and λN−1 are always nontrivial and the lower estimate for λ1 improves Ollivier’s estimate k ≤ λ1 for all graphs with k ≤ 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. 1