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
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,

<center class="math-display"> <img src="/fileadmin/preprint_img/2011/tex_1650a0x.png" alt="1- (1- k[t])1t &amp;#x2264; &amp;#x03BB;1 &amp;#x2264; &amp;#x22C5;&amp;#x22C5;&amp;#x22C5; &amp;#x2264; &amp;#x03BB;N-1 &amp;#x2264; 1+ (1- k[t])1t,&amp;#x2200;integerst &amp;#x2265; 1. " class="math-display"></center>

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.10.2019, 02:14