Local geometry of graphs and random walks
Paul Horn
University of Denver
Frank Bauer
Harvard University
Yong Lin
Renmin University
Gabor Lippner
Northeastern University
Dan Mangoubi
Hebrew University
Shing-Tung Yau
Harvard University
PDF
Minisymposium: SPECTRAL GRAPH THEORY
Content: Harnack inequalities relate the maximum and minimum values of eigenfunctions or positive solutions to the heat equation. These are classical in the manifold setting, and versions are also known for functions on graphs. It is known that a graph satisfying a so-called parabolic Harnack inequality is equivalent to the graph satisfying certain (hard to check) geometric conditions. In the non-negatively curved manifold case, the Li-Yau inequality is a stronger (local) gradient estimate which implies the (global) Harnack inequality. In this talk we describe a similar gradient estimate for graphs. This has immediate applications to the evolution of continuous time random walks on graphs, and yields a graph analogue of Buser's inequality (which states that for non-negatively curved graphs, the lower bound Cheeger's inequality gives on the first eigenvalue is of the correct order). Along the way, we discuss the issue of defining curvature for graphs and some of the difficulties that arise when transferring a continuous result into a discrete setting along with some additional results on graphs.