A strong Harnack inequality for graphs

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.

Full Text (PDF format)

Received 19 February 2015

Published 13 September 2017