Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator (Q390203)

In this paper, the authors utilize techniques inspired by Riemannian geometry and the theory of stochastic processes in order to control eigenvalues of graphs. In particular, they prove the following useful estimate for the spectrum of the normalized Laplace operator \(\Delta \) on a finite graph \(G\): \(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 t \geq 1 \in \mathbb{N}\), where \( k[ t] \) is a lower bound for the Ollivier-Ricci curvature on the neighborhood graph \(G\left[ t \right]\), which was introduced by Bauer-Jost. In particular, when \(t = 1\) this is Ollivier's estimate \(k \leq \lambda _1 \leq \cdots \leq \lambda _{N - 1} \leq 2 - k\). For sufficiently large \(t\) the authors also show that, unless \(G\) is bipartite, their estimates for \(\lambda _1 \) and \(\lambda _{N - 1}\) are always nontrivial and improve Ollivier's estimate for all graphs with \(k \leq 0\). Note that by definition neighborhood graphs are weighted graphs which may have loops, and to understand the Ollivier-Ricci curvature on neighborhood graphs, the authors 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. Moreover, the authors close the gap between the geometric properties of a graph \(G\), the spectrum of its graph Laplacian, random walks on \(G\), and the generalized curvature of \(G\), drawing upon deep ideas and concepts originally developed in Riemannian geometry and the theory of stochastic processes.