Communications in Analysis and Geometry

Volume 25 (2017)

Number 3

A strong Harnack inequality for graphs

Pages: 557 – 588

DOI: https://dx.doi.org/10.4310/CAG.2017.v25.n3.a3

Authors

Fan Chung (Department of Mathematics, University of California at San Diego)

Shing-Tung Yau (Department of Mathematics, Harvard University, Cambridge, Massachusetts, U.S.A.)

Abstract

We introduce the curvature (and the flow curvature) for graphs, which allow us to prove several Harnack inequalities for general graphs (which are not necessarily regular). We first show that for a graph with curvature $\kappa$, the combinatorial eigenfunction $f$ associated with eigenvalue $\lambda$ satisfies, for any edge $\lbrace x, y \rbrace$,\[{\lvert f(x) - f(y) \rvert}^2 \leq (8 \lambda + 4 \kappa) d_{max}\]where $\max_x \lvert f(x) \rvert = \max_x f(x) = 1$ and $d_{max}$ denotes the maximum degree. The above inequality is used to prove a a strengthened inequality which implies that the ‘stretches’ of edges determined by eigenfunctions are particularly ‘small’ (in terms of the associated eigenvalue and curvature) near the maximum point. Namely, for a graph with curvature $\kappa$, the combinatorial eigenfunction $f$ associated with eigenvalue $\lambda$ satisfies, for any edge $\lbrace x, y \rbrace$,\[{\lvert f(x) - f(y) \rvert}^2 \leq \frac{c_1 \lambda + c_2 \kappa}{\beta - 1} (\beta - f(x))^2\]where $c_5 \geq \beta \geq 1 + c_3 \lambda + c_4 \kappa$ and $c$’s are constants depending only on the maximum degree of the graph.

Received 19 February 2015

Published 13 September 2017