Li-Yau inequality on graphs

By Frank Bauer, Paul Horn, Yong Lin, Gábor Lippner, Dan Mangoubi, Shing-Tung Yau. 2013

204 citations recorded by the source corpus.

We prove the Li-Yau gradient estimate for the heat kernel on graphs. The only assumption is a variant of the curvature-dimension inequality, which is purely local, and can be considered as a new notion of curvature for graphs. We compute this curvature for lattices and trees and conclude that it behaves more naturally than the already existing notions of curvature. Moreover, we show that if a graph has non-negative curvature then it has polynomial volume growth. We also derive Harnack inequalities and heat kernel bounds from the gradient estimate, and show how it can be used to strengthen the classical Buser inequality relating the spectral gap and the Cheeger constant of a graph.

Subfields: Applied Mathematics, Genetics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/b2ad8d5646b8f20532da8535c0edc61ddff8f1b7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Genetics

In Geometry and Topology

Citations in the corpus

Remarks on curvature dimension conditions on graphs (2015, methodology): “ﬂat graphs. 1 Introduction There is an immense interest in the heat equation on graphs. In this context, curvaturedimension conditions have attracted particular attention. In particular, recent works [2, 4, 5] have introduced a variety of such conditions. In this note, we will extend ideas of [5] to”
On quotients of spaces with Ricci curvature bounded below (2017, background): “In [11] the authors introduced a variant of this condition which gives a Li-Yau-type inequality for the heat flow.”
Bakry–Émery Curvature Functions on Graphs (2016, background): “;x;N) bethelargest Ksuchthat(1.2)holdsforallfunctions fat xforagiven N. Wecall K G;x(N) := K(G;x;N) theBakry-Émerycurvaturefunction ofx. Thereadercanﬁndvariousmodiﬁcationsofthiscurvaturenotionin,e.g.,[5,17,30,31,26,23]. It is natural to ask about the motivation for this curvature. The notion is root”
Gradient estimates for heat kernels and harmonic functions (2017, background): “In recent years, in a series of works [13, 52, 72, 73, 114, 115], Yau’s gradient estimate for harmonic functions and Li-Yau’s gradient estimate for heat kernels (and their local versions) have been further generalised to metric measure spaces and graphs satisfying suitable curvature assumptions; we ”
Bakry–Émery curvature and diameter bounds on graphs (2016, background): “For that reason, there were introduced various non-linear curvature dimension conditions (namely CDE, CDE′, CDψ) closely related to the classical linear CD condition [3, 17].”
Li–Yau inequality on finite graphs via non-linear curvature dimension conditions (2014, methodology): “On graphs, it has been studied in [5, 6, 10, 13, 15, 16].”
Discrete Curvature and Abelian Groups (2015, methodology): “A preprint of these results did circulate and a number of papers built on it [6, 24].”