Li-Yau inequality on graphs (Q2343970)

The aim of the article under review is to derive a generalization of the Li-Yau gradient estimate to graphs. On compact \(n\)-dimensional manifolds with non-negative Ricci curvature, this inequality states that positive solutions \(u\) of the heat equation \(\Delta u-\partial_tu=0\) satisfy \[ |\nabla\log u|^2-\partial_t(\log u)\leq\frac{n}{2t}. \] First of all, it is shown that this inequality does not hold on graphs in its original form, which is due to the fact that the chain rule fails on graphs. To overcome this problem, the authors show a way to bypass the chain rule in the discrete setting. This is achieved by the observation that the identity \[ \Delta u^p=pu^{p-1}\Delta u+\frac{p-1}{p}u^{-p}|\nabla u^p|^2 \] still holds on graphs for \(p=1/2\). Moreover, they introduce a new notion of curvature on graphs motivated from the Bochner identity on a manifold with Ricci curvature bounded from below. These tools allow the authors to prove the Li-Yau gradient estimate of the heat kernel on graphs. Applying the gradient estimate, Harnack inequalities and heat kernel bounds are derived. As a corollary a Buser-type inequality relating the spectral gap and the Cheeger constant of a graph is obtained.