Local geometry of graphs and random walks

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.

Back to all abstracts