Parabolic Harnack inequality and estimates of Markov chains on graphs (Q1283368)

Let \(\Gamma\) be a graph and let \(p_n(x,y)\) be the kernel of the standard random walk on \(\Gamma\). The author is interested in finding conditions under which one has the following Gaussian estimate: \[ {c\over V(x,\sqrt{n})}e^{-Cd(x,y)^{2}/n}\leq p_n(x,y)\leq {C\over V(x,\sqrt{n})}e^{-cd(x,y)^{2}/n} \] for some constants \(c\) and \(C\), where \(V(x,n)\) is the cardinality of the ball of center \(x\) and radius \(n\), with the assumptions that \(d(x,y)\leq n\) and that all the vertices of \(\Gamma\) are loops. The author proves that the inequalities hold for graphs of polynomial growth under an isoperimetric assumption such as Poincaré inequality. This proves a conjecture made by \textit{T. Coulhon} and \textit{L. Saloff-Coste} [Probab. Theory Relat. Fields 97, No. 3, 423-431 (1993; Zbl 0792.60063)]. The author proves in fact a characterization of the parabolic Harnack inequality. The result is a discrete counterpart of a result of \textit{L. Saloff-Coste} [Potential Anal. 4, No. 4, 429-467 (1995; Zbl 0840.31006)]. The author gives, as an application of the Harnack inequality, a new proof of the theorem of J. Nash on the Hölder regularity for solutions of the elliptic/parabolic equation.