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

Details Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator

2011-05-19

arxiv.org/abs/1105.3803v1

Mathematics

Combinatorics

22 pages, 7 figures

Scientific paper

We prove the following estimate for the spectrum of the normalized Laplace operator $\Delta$ on a finite graph $G$, \begin{equation*} 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 \,\,\text{integers}\,\, t\geq 1. \end{equation*} 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\leq \lambda_1$ and a new sharp upper bound $\lambda_{N-1}\leq 2-k$ for the largest eigenvalue. Furthermore, we prove that for any $G$ when $t$ is sufficiently large, $1>(1- k[t])^{\frac{1}{t}}$ which shows that our estimates for $\lambda_1$ and $\lambda_{N-1}$ are always nontrivial and the lower estimate for $\lambda_1$ improves Ollivier's estimate $k\leq \lambda_1$ for all graphs with $k\leq 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.

Affiliated with

Also associated with

No associations

Rating

Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-68868