Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator
Frank Bauer, Jürgen Jost, and Shiping Liu
Contact the author: Please use for correspondence this email.
Submission date: 19. May. 2011
published in: Mathematical research letters, 19 (2012) 6, p. 1185-1205
DOI number (of the published article): 10.4310/MRL.2012.v19.n6.a2
MSC-Numbers: 60J05, 51F99, 05C50
Keywords and phrases: Ollivier-Ricci curvature, normalized graph Laplace operator, largest eigenvalue, random walk, neighborhood graph
Download full preprint: PDF (326 kB)
We prove the following estimate for the spectrum of the normalized Laplace operator Δ on a finite graph G,
Here k[t] is a lower bound for the Ollivier-Ricci curvature on the neighborhood graph G[t] (here we use the convention G = 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]) 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.