Random walks on graphs with regular volume growth (Q1270032): Difference between revisions

Let the transition probabilities of a nearest neighbour random walk on an infinite graph \(\Gamma\) be given by a Markov kernel \(p(x,y)\), \(x,y\in\Gamma\), which is reversible with respect to a positive measure \(m(x)\) on \(\Gamma\). The main goal of the paper is to describe the conditions under which the probability \(p_k(x,y)\) of reaching \(y\) from \(x\) in \(k\) steps admits the Gaussian upper bound: \( p_k(x,y)\text{vol} B(x,\sqrt k)\leq Cm(y)\exp(-cd^2(x,y)/k) \), where \(B(x,r)\) is the ball of radius \(r\) in \(\Gamma\) with respect to the usual graph distance \(d(x,y)\). A similar result in continuum is well known: the theorem by \textit{P. Li} and \textit{S. T. Yau} [Acta Math. 156, 154-201 (1986; Zbl 0611.58045)] gives such an estimate for the heat kernel of a Brownian motion on a complete non-compact Riemannian manifold of nonnegative Ricci curvature. However, the condition that the Ricci curvature be nonnegative is by no means necessary; a paper by the second author [Rev. Mat. Iberoam. 10, No. 2, 395-452 (1994; Zbl 0810.58040)] contains a criterion for such an estimate in terms of a certain isoperimetric type inequality known as the relative Faber-Krahn inequality. In the paper under review the authors show that, for a reversible nearest neighbour random walk on a locally finite graph \(\Gamma\), the relative Faber-Krahn inequality is equivalent to the existence of the Gaussian upper bound for the Markov kernel of this walk (in conjunction with some condition of regular volume growth). Moreover, these inequalities are shown to be equivalent (under the same condition of regular volume growth) to the on-diagonal upper bound \(p_k(x,x)\leq Cm(x)/\text{vol} B(x,\sqrt k)\) for any \(x\in\Gamma\) and \(k\geq 1\). These estimates are shown to be optimal in the sense that each of them implies lower bounds for the diagonal terms \(p_k(x,x)\) which differ by a constant factor from the corresponding upper bounds.