Preprint 25/2011

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
Pages: 24
published in: Mathematical research letters, 19 (2012) 6, p. 1185-1205 
DOI number (of the published article): 10.4310/MRL.2012.v19.n6.a2
Bibtex
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)

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,∀integerst ≥ 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.

18.07.2014, 01:43