%% This document created by Scientific Word (R) Version 3.0
%\usepackage{showkeys}
%\newenvironment{remark}{\smallskip\noindent{\bf Remark:}\rm}{\smallskip}
%\newenvironment{example}{\smallskip\noindent{\bf Example:}}{\smallskip}


\documentclass[11pt,a4paper]{article}
\usepackage{amssymb}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%TCIDATA{TCIstyle=Article/art4.lat,lart,article}

%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{LastRevised=Fri May 11 08:15:12 2001}
%TCIDATA{<META NAME="ViewSettings" CONTENT="1">}
%TCIDATA{<META NAME="ViewPercent" CONTENT="100">}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{Language=American English}
%TCIDATA{CSTFile=LaTeX article (bright).cst}

\setlength{\textheight}{24 cm}
\setlength{\textwidth}{16.2 cm}
\setlength{\topmargin}{-1cm}
\setlength{\oddsidemargin}{0.5 cm}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemmma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{example}{Example}[section]
\newtheorem{remark}{Remark}[section]
\newenvironment{proof}[1][Proof]{\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{solution}[1][Solution]{\textit{#1.} }{\ \rule{0.em}{0.0em}}
\renewcommand{\theequation}{\thesection.\arabic{equation}}
\input{tcirm}
\input tcilatex

\begin{document}

\title{Pointwise estimates for transition probabilities of random 
walks on infinite
graphs}
\author{Thierry Coulhon\thanks{%
Research partially supported by the European Commission (European TMR
Network ``Harmonic Analysis'' 1998-2001, Contract ERBFMRX-CT97-0159).} \\
%EndAName
Universit\'e de Cergy-Pontoise\\
95000 Cergy \\
France\\
Thierry.Coulhon@math.u-cergy.fr\\
http://www.u-cergy.fr/rech/pages/coulhon/pageTC.html \and Alexander
Grigor'yan \\
%EndAName
Imperial College\\
London SW7 2BZ \\
England\\
a.grigoryan@ic.ac.uk \\
http://www.ma.ic.ac.uk/\symbol{126}grigor}
\date{\today}
\maketitle
\tableofcontents

\section{Preliminaries}

\label{SecIntro}\setcounter{equation}{0}

Let $\Gamma $ be a countable infinite locally finite connected graph. If the
vertices $x,y\in \Gamma $ are connected by an edge then we write $x\sim y$
and denote the edge connecting $x$ and $y$ by $\overline{xy}$. Suppose that
each edge $\overline{xy}$ is assigned a positive weight $\mu _{xy}=\mu _{yx}$%
. Then define a function $\mu $ on vertices by
\[
\mu (x)=\sum_{\left\{ y:y\sim x\right\} }\mu _{xy}
\]
and extend it to a measure on finite sets $A\subset \Gamma $ by
\[
\mu (A)=\sum_{x\in A}\mu (x).
\]
On every graph $\Gamma $ one can consider the \emph{standard weight}: $\mu
_{xy}=1$ for all edges $\overline{xy}$. In this case, $\mu (x)$ is equal to
the degree of $x$, that is to the number of adjacent edges.

A graph $\Gamma $ equipped by a weight $\mu $ as above is called a\emph{\
weighted graph}. Any weighted graph $\left( \Gamma ,\mu \right) $ admits a
random walk on $\Gamma $ defined by the one-step transition probabilities
\[
P(x,y):=\frac{\mu _{xy}}{\mu (x)}\mbox{ if }y\sim x,\ 0\mbox{ if not}.
\]
Clearly, $P$ is a Markov kernel, that is
\[
\sum_{y\in \Gamma }P(x,y)=1.
\]
It is symmetric with respect to the measure $\mu $, that is $P(x,y)\mu
(x)=P(y,x)\mu (y)$. A random walk $X_{n}$ on $\Gamma $ is defined for all $%
n\in \Bbb{N}$ by the transition rule
\[
\Bbb{P}\left( X_{n+1}=y\,|\,X_{n}=x\right) =P(x,y).
\]
Denote $P_{n}(x,y)=\Bbb{P}\left( X_{n}=y\,|\,X_{0}=x\right) $. The main
subject of this note is the \emph{heat kernel }$p_{n}(x,y)$, defined as the
density of $P_{n}(x,y)$ with respect to $\mu$, that is
\[
p_{n}(x,y)=\frac{P_{n}(x,y)}{\mu (y)}.
\]
Clearly, $p_{n}(x,y)=p_{n}(y,x)$.

Denote by $d(x,y)$ the graph distance between points $x,y\in \Gamma $, that
is the minimal number of edges required to connect $x$ to $y$ by an edge
path.

We will survey some results of two kinds: about the on-diagonal behavior of
the heat kernel, that is $p_{n}(x,x)$ as a function of $n\rightarrow +\infty
$, and about the off-diagonal behavior, that is $p_{n}(x,y)$ as a function
of the distance $d(x,y)$. On the connection between $\sup_{x\in 
\Gamma}p_{n}(x,x)$ and
isoperimetric profiles see \cite{CouUltra}, \cite{CouCortona} and \cite
{CouRan}. For a general view of random walks on infinite graphs see \cite
{Woessbook}.

An important characteristic of a weighted graph is the volume growth
function $V(x,r)$ defined as follows. Denote by $B(x,r)$ the ball associated
with the distance $d(x,y)$, that is $B(x,r)=\left\{ y\in \Gamma
:d(x,y)<r\right\} $, and set $V(x,r)=\mu (B(x,r)).$

For example, for $\Bbb{Z}^{D}$ with a standard weight we have $V(x,r)\simeq
r^{D}$. A modification of the local central limit theorem implies that, for
all positive $n\geq d(x,y)$ such that $n\equiv d(x,y)\left( \func{mod}%
2\right) $,
\begin{equation}
p_{n}(x,y)\simeq n^{-D/2}\exp \left( -\frac{d^{2}(x,y)}{Cn}\right) .
\label{pnZD}
\end{equation}
A similar estimate holds for Cayley graphs of finitely generated groups with
polynomial volume growth (see \cite{HebSC}).

\textbf{\ }Note that on any infinite weighted graph $\left( \Gamma ,\mu
\right) $, the following estimate holds:
\[
p_{n}(x,y)\leq \frac{C}{\sqrt{\mu (x)\mu (y)}}\exp \left( -\frac{d^{2}(x,y)}{%
Cn}\right)
\]
(see \cite{Varlong}, \cite{Carne}). However, this estimate does not reflect
the decay of the heat kernel as $n\rightarrow \infty $.

Let us mention finally estimates of a different kind, which hold on 
bound percolation clusters in $\Bbb{Z}^{D}$:
$$\sup_{y\in\Gamma}p_n(x,y)\le C(x) n^{-D/2}$$
(see Mathieu).

\section{On-diagonal decay and volume growth}

\label{SecVol}\setcounter{equation}{0}The Markov property implies that for
all $n\in \Bbb{N}$%
\[
\sum_{y\in \Gamma }P_{n}(x,y)=1
\]
that is
\[
\sum_{y\in \Gamma }p_{n}(x,y)\mu (y)=1.
\]
Restricting the summation to $B(x,r)$, we obtain
\[
\inf_{y\in B(x,r)}p_{n}(x,y)\leq \frac{1}{V(x,r)}.
\]
This inequality suggests that the faster the function $V(x,r)$ increases the
smaller the heat kernel should be, which agrees with (\ref{pnZD}). There are
several results reflecting this heuristic idea. We first restrict ourselves
to the case of polynomial volume growth.

\begin{theorem}
\label{Tsuplow}\emph{\cite[Theorem 4.6]{CouGlower}} Let for some $x_{0}\in
\Gamma $ and all $r>0$%
\begin{equation}
V(x_{0},2r)\leq CV(x_{0},r).  \label{VD}
\end{equation}
Then for all even $n>0$,
\begin{equation}
\sup_{x\in \Gamma }p_{n}(x,x)\geq \frac{c}{V(x_{0},\sqrt{n})}.
\label{suppn>}
\end{equation}
\end{theorem}

In fact, the proof in \cite{CouGlower} uses the additional hypotheses that $%
x\sim x$ for all $x\in \Gamma $ and that $\inf_{x\sim y}P(x,y)>0$. One can
get rid of these assumptions using \cite[Proposition 4.2]{CouGPanti}.

\begin{theorem}
\label{Tlow}\emph{\cite{LuPiq}} If for some $x_{0}\in \Gamma $ and all $%
r\geq 1$%
\[
V(x_{0},r)\leq Cr^{D},
\]
then for all even $n>0$%
\begin{equation}
p_{n}(x_{0},x_{0})\geq \frac{c}{V(x_{0},\sqrt{Cn\log n})}.  \label{pnx0>}
\end{equation}
\end{theorem}

\textbf{\ [[ check exact conditions]]}

The lower bound (\ref{suppn>}) is sharp in $\Bbb{Z}^{D}$ (up to a constant
factor). It is not known whether in Theorem \ref{Tsuplow} one can replace $%
\sup_{x}p_{n}(x,x)$ by $p_{n}(x_{0},x_{0})$. Theorem \ref{Tlow} does provide
a lower bound for $p_{n}(x_{0},x_{0})$ which in comparison with (\ref{suppn>}%
) is off by a factor $\sqrt{\log n}$. An example constructed in \cite{BarPer}
indicates that one can probably not get rid of the logarithm in 
(\ref{pnx0>}). Note that the volume doubling condition
(\ref{VD}) is not satisfied in this example.

\begin{theorem}
\label{Tbig}\emph{(\cite[Theorem 2.1]{BarCGbig}, \cite[Section 5]{CouSC}) }%
Let the weighted graph $(\Gamma ,\mu )$ satisfy the hypothesis
\begin{equation}
\inf_{x\sim y}\mu _{xy}>0.  \label{mu_xy}
\end{equation}
Suppose that, for all points $x\in \Gamma $ and all $r\geq 1$,
\begin{equation}
V(x,r)\geq cr^{D}.  \label{V>rD}
\end{equation}
Then, for all $x\in \Gamma $ and for all $n\in \Bbb{N}$,
\begin{equation}
p_{n}(x,x)\leq Cn^{-\frac{D}{D+1}}.  \label{D/D+1}
\end{equation}
\end{theorem}

Note that the hypothesis (\ref{mu_xy}) is automatically satisfied for a
standard weight. It also implies that (\ref{V>rD}) holds for $D=1$. Hence,
one can assume that $D\geq 1$.

In fact, \cite[Theorem 2.1 and Remark 2.2]{BarCGbig} contains a more general
result as follows. Suppose for all $x\in \Gamma $ and $r\geq 1$,
\begin{equation}
V(x,r)\geq v(r),\label{lovol}
\end{equation}
where $v$ is a continuous positive strictly increasing convex function on $%
[1,+\infty )$. Then, for all $x\in \Gamma $ and for all $n\in \Bbb{N}$,
\begin{equation}
p_{n}(x,x)\leq \frac{C}{\gamma (cn)},  \label{p-ga}
\end{equation}
where $\gamma $ is determined by the relation
\begin{equation}
\gamma ^{-1}\left( s\right) \simeq sv^{-1}(s).  \label{ga-v}
\end{equation}

For example, if $v(r)=cr^{D}$ then $\gamma ^{-1}\left( s\right) \simeq
s^{1+1/D}$ whence $\gamma \left( t\right) \simeq t^{\frac{D}{D+1}}$.

The upper bound (\ref{D/D+1}) is by far not optimal for $\Bbb{Z}^{D}$. Of
course, the value of Theorem \ref{Tbig} largely depends on whether the
exponent $D/\left( D+1\right) $ is sharp, and it indeed is.

\begin{theorem}
\label{TVic}\emph{\cite[Theorem 4.1]{BarCGbig}} For arbitrarily large $D$
there exists a graph $\Gamma $ for which (with a standard weight)
\begin{equation}
V(x,r)\simeq r^{D}  \label{V=rD}
\end{equation}
and
\begin{equation}
p_{n}(x,x)\simeq n^{-\frac{D}{D+1}}  \label{p=D/D+1}
\end{equation}
for all $x\in \Gamma $, $r\geq 1$ and even $n>0$.
\end{theorem}

\label{SecVic}Let us describe this example, motivated by fractal studies.
Fix a positive integer $N$ and construct a graph $\Gamma $ called a \emph{%
Vicsek tree} as a subset of $\Bbb{R}^{N}$. Let $Q_{r}$ denote the cube in $%
\Bbb{R}^{N}$
\[
Q_{r}=\left\{ x\in \Bbb{R}^{N}:0\leq x_{i}\leq r,\quad i=1,2,...,N\right\} .
\]
Construct an increasing sequence $\left\{ \Gamma _{k}\right\} $ of finite
graphs as subsets of $Q_{3^{k}}$. Let $\Gamma _{1}$ be the set of $2^{N}+1$
points containing all vertices of $Q_{1}$ and the center of $Q_{1}$. Define $%
2^{N}$ edges in $\Gamma _{1}$ as segments connecting the center with the
corners. Assuming that $\Gamma _{k}$ is already constructed, define $\Gamma
_{k+1}$ as follows. The cube $Q_{3^{k+1}}$ is naturally divided into $3^{N}$
congruent copies of $Q_{3^{k}}$; select $2^{N}+1$ of the copies of $%
Q_{3^{k}} $ by taking the corner cubes and the center one. In each of the
selected copies of $Q_{3^{k}}$ construct a congruent copy of graph $\Gamma
_{k}$, and define $\Gamma _{k+1}$ as the union of all $2^{N}+1$ copies of $%
\Gamma _{k}$ (merged at the corners). Then the Vicsek tree $\Gamma $ is the
union of all $\Gamma _{k}$, $k\geq 1$ (see Fig. \ref{pic1}).

\FRAME{ftbphFU}{3.8069in}{2.4068in}{0pt}{\Qcb{Vicsek tree in the plane}}{%
\Qlb{pic1}}{fpic1.wmf}{\special{language "Scientific Word";type
"GRAPHIC";maintain-aspect-ratio TRUE;display "USEDEF";valid_file "F";width
3.8069in;height 2.4068in;depth 0pt;original-width 6.2993in;original-height
3.9652in;cropleft "0";croptop "1";cropright "1";cropbottom "0";filename
'fpic1.wmf';file-properties "XNPEU";}}It turns out that for the Vicsek tree
both conditions (\ref{V=rD}) and (\ref{p=D/D+1}) hold with
\[
D=\log _{3}\left( 2^{N}+1\right) .
\]

In  Barlow, very interesting constructions of graphs  are given, 
which yield the conclusion of Theorem  \ref{TVic}
for {\emph every} $D\ge 1$.

Concerning arbitrary types of volume growths, it is also shown in 
\cite{BarCGbig} that  there are graphs satisfying
(\ref{lovol}) for any reasonable function
$v$ and where the matching lower bound to (\ref{p-ga}) holds, up  to 
a logarithmic factor (see .

\section{Gaussian upper bound}

\label{SecRel}\setcounter{equation}{0}For any function $f$ on $\Gamma $
define its energy by
\[
\mathcal{E}\left( f\right) =\frac{1}{2}\sum_{\left\{ x,y:x\sim y\right\}
}\left( f(x)-f(y)\right) ^{2}\mu _{xy}.
\]
Define the Laplace operator on a function $f$ on $\Gamma $ by
\[
\Delta f(x)=\sum_{y\sim x}P(x,y)f(y)-f(x).
\]
One says that $f$ is \emph{harmonic }on $\Omega \subset \Gamma $ if $f$ is
defined on $\Omega $ and all neighbors of $\Omega $ and if
\[
\Delta f(x)=0~~~\forall \,x\in \Omega
\]
(in other words, $f$ has the mean value property with respect to $P$).
Similarly, $f$ is subharmonic if $\Delta f\geq 0$.

For any non-empty finite set $A\subset \Gamma $, let $c_{0}(A)$ be the set of
all functions on $\Gamma $ which vanish outside $A$; then define
\[
\lambda _{1}\left( A\right) =\inf_{f\in c_{0}(A),f\not\equiv 0}\frac{%
\mathcal{E}\left( f\right) }{\sum_{x}f^{2}(x)\mu (x)}.
\]
Alternatively, $\lambda _{1}(A)$ is the minimal eigenvalue of the Laplace
operator $\Delta $ restricted to the space $c_{0}\left( A\right) $ of all
functions on $\Gamma $ vanishing outside $A$.

For example, in $\Bbb{Z}^{D}$ the following lower bound for $\lambda _{1}$
is true:
\begin{equation}
\lambda _{1}\left( A\right) \geq c\mu \left( A\right) ^{-2/D}.  \label{FKZD}
\end{equation}

Consider the following hypotheses which in general may or may not be true:

\begin{itemize}
\item  \emph{Volume doubling property:} for some $C>0$ and all $x\in \Gamma
, $ $r>0$%
\begin{equation}
V(x,2r)\leq CV(x,r).  \tag{$VD$}
\end{equation}

\item  \emph{On-diagonal upper estimate}: for all $x\in \Gamma $ and $n>0$%
\begin{equation}
p_{n}(x,x)\leq \frac{C}{V(x,\sqrt{n})}.  \tag{$DUE$}
\end{equation}
as well as the \emph{on-diagonal lower estimate}: for all $x\in \Gamma $ and
even $n>0$%
\begin{equation}
p_{n}(x,x)\geq \frac{c}{V(x,\sqrt{n})},  \tag{$DLE$}
\end{equation}
for some $c>0$.

\item  \emph{Upper estimate}: for all $x,y\in \Gamma $ and $n>0$%
\begin{equation}
p_{n}(x,y)\leq \frac{C}{V(x,\sqrt{n})}\exp \left( -\frac{d^{2}(x,y)}{Cn}%
\right) .  \tag{$UE$}
\end{equation}

\item  \emph{Faber-Krahn type inequality:} for any ball $B\left( x,r\right) $
on $\Gamma $ and any non-empty set $A\subset B\left( x,r\right) $%
\begin{equation}
\lambda _{1}\left( A\right) \geq \frac{c}{r^{2}}\left( \frac{V(x,r)}{\mu (A)}%
\right) ^{\alpha }  \tag{$FK$}
\end{equation}
for some $\alpha ,c>0$.
\end{itemize}

For example, $(FK)$ holds in $\Bbb{Z}^{D}$ with $\alpha =2/D$ which follows
from $V(x,r)\approx r^{D}$ and (\ref{FKZD}).

\begin{theorem}
\label{TFK}\emph{\cite[Theorems 1.1, 6.1]{CouGgraph}} For any weighted graph
$\left( \Gamma ,\mu \right) $, we have
\[
\left( FK\right) \Longleftrightarrow \left( UE\right) +\left( VD\right)
\Longleftrightarrow \left( DUE\right) +\left( VD\right) \Longrightarrow
\left( DLE\right) .
\]
In particular, if $\left( \Gamma ,\mu \right) $ satisfies $(VD)$ then
\[
\left( FK\right) \Longleftrightarrow \left( UE\right) \Longleftrightarrow
\left( DUE\right) \Longrightarrow \left( DLE\right) .
\]
\end{theorem}

A continuous analogue of this theorem for the heat kernel on Riemannian
manifolds was proved in \cite{GrigHeat}.

Let $\nu $ be another weight on the graph $\Gamma $ such that $\mu (x)\simeq
\nu (x)$ for all $x\in \Gamma $. Observe that the condition $(FK)$ is
invariant under such a change of weight. More generally, it is also
invariant under quasi-isometry of weighted graphs (see for instance \cite
{CouSCisom}). By Theorem \ref{TFK}, the conditions $(UE)$ and $(DUE)$ are
preserved by quasi-isometry, which is a priori not obvious.

\section{Gaussian two-sided estimates}

\label{SecGauss}\setcounter{equation}{0}

For any subset $A\subset \Gamma $ and any function $f$ on $\Gamma $, define
the energy of $f$ on $A$ by
\[
\mathcal{E}\left( f;A\right) :=\frac{1}{2}\sum_{\left\{ x,y:x\in A,y\sim
x\right\} }\left( f(x)-f(y)\right) ^{2}\mu _{xy}.
\]
Alternatively,
\[
\mathcal{E}\left( f;A\right) =\sum_{x\in A}\left| \nabla f\right| ^{2}(x)\mu
(x)
\]
where
\[
\left| \nabla f\right| ^{2}(x):=\frac{1}{2}\sum_{y\sim x}\left(
f(y)-f(x)\right) ^{2}P(x,y).
\]
Denote also
\[
f_{A}=\frac{1}{\mu (A)}\sum_{y\in A}f(y)\mu (y).
\]

Let us introduce the following hypotheses which in general may  or 
may not be true.

\begin{itemize}
\item  \emph{Poincar\'{e} inequality}: for some $c>0$, $\delta \in (0,1]$
and for all $x\in \Gamma $, $R>0$, for any function $f$ on $\Gamma $,
\begin{equation}
\frac{c}{R^{2}}\sum_{y\in B(x,\delta R)}|f(y)-f_{B(x,R)}|^{2}\mu (y)\leq
\mathcal{E}\left( f;B\left( x,R\right) \right) .  \tag{$PI$}
\end{equation}

\item  \emph{Lower estimate} of the heat kernel: for all $x,y\in \Gamma $
and all positive $n\geq d(x,y)$,
\begin{equation}
p_{n}(x,y)\geq \frac{c}{V(x,\sqrt{n})}\exp \left( -\frac{d(x,y)^{2}}{cn}%
\right) .  \tag{$LE$}
\end{equation}

\item  \emph{Parabolic Harnack }inequality:\emph{\ } for all $x\in \Gamma $,
$R\geq 1$ and for any non-negative function $u_{n}(y)$ defined for $n\in
\lbrack 0,4T],$ $y\in B(x,2R+1)$ and satisfying the heat equation $%
u_{n+1}=Pu_{n}$ in $[0,4T)\times B(x,2R)$, the following inequality holds
\begin{equation}
\max\Sb n\in \lbrack T,2T)  \\ y\in B(x,R)  \endSb u_{n}(y)\leq C\min\Sb %
n\in \lbrack 3T,4T)  \\ y\in B(x,R)  \endSb u_{n}(y),  \tag{$PH$}
\end{equation}
provided $T$ is a positive integer such that $T\simeq R^{2}$ and $T\geq 2R$.
\end{itemize}

The relation between these hypotheses is given by the following theorem.

\begin{theorem}
\label{TD+P}\emph{\cite{DelmottePar}} Assume that $\left( \Gamma ,\mu
\right) $ satisfies the following conditions:

\begin{itemize}
\item[$(i)$]  $x\sim x$ for all $x\in \Gamma $

\item[$(ii)$]  there exists $\varepsilon >0$ such that $P(x,y)\geq
\varepsilon >0,\quad $for all $x\sim y.$
\end{itemize}

Then
\[
\left( UE\right) +\left( LE\right) \Longleftrightarrow
(PH)\Longleftrightarrow \left( VD\right) +\left( PI\right) .
\]
\end{theorem}

The continuous version of this theorem was proved in \cite{SalHar} and \cite
{GrigHar}. It is possible to show that the conditions $(VD)$ and $\left(
PI\right) $ are stable under quasi-isometry (see \cite{CouSCisom}); 
hence both $(PH)$ and $%
(UE)+(LE) $ are stable under quasi-isometry.

The role of the condition $(i)$ is to avoid the parity problem. Indeed, it
excludes in particular bipartite graphs for which $p_{n}(x,y)=0$ whenever $n$
and $d(x,y)$ have different parities. Of course, for such graphs $(LE)$
cannot hold.

The hypothesis $\left( ii\right) $ implies that the degree of each vertex $%
x\in \Gamma $ is uniformly bounded from above. If $\mu $ is a standard
weight then $(ii)$ is equivalent to this condition.

Note that $(VD)+\left( PI\right) \Longrightarrow (FK)$ (see \cite{CouGgraph}%
). Therefore, the implication $\left( VD\right) +\left( PI\right)
\Longrightarrow (UE)$ can be deduced by Theorem \ref{TFK}. By the same
theorem, one obtains the on-diagonal lower bound $\left( DLE\right) $ for
the heat kernel. Hence, the main point of Theorem \ref{TD+P} is in obtaining
the off-diagonal lower estimate, that is $\left( VD\right) +\left( PI\right)
\Longrightarrow \left( LE\right) $.

A more direct approach than the one in \cite{DelmottePar} to off-diagonal
lower bounds was given in \cite{AuCou}. The idea is to prove elliptic
regularity estimates as a consequence of $(VD)$ and $(PI)$ by coming back to
the ideas of De Giorgi, then deduce parabolic regularity from elliptic
regularity by using the method introduced in \cite{Auscher} in a continuous
context, and finally obtain the full off-diagonal lower bound. \medskip

Let us start with some definitions:

\begin{definition}
\RM
We say that $(\Gamma ,\mu )$ satisfies the \emph{De Giorgi property} if
there exist $C>0$ and $\alpha \in (0,1)$ such that for every $x\in \Gamma $,
every $r,R$ such that $1\leq r\leq R$, and every function $f$ which is
harmonic on $B(x,R)$, one has
\begin{equation}
\mathcal{E}\left( f;B(x,r)\right) \leq C\left( \frac{R}{r}\right)
^{2(1-\alpha )}\frac{V(x,r)}{V(x,R)}\mathcal{E}\left( f;B(x,R)\right) .
\tag{$DG$}
\end{equation}
\end{definition}

\begin{definition}
\RM
We say that a \emph{parabolic oscillation estimate} holds on $(\Gamma ,\mu )$
if there exist $\beta ,\delta ,C>0$, such that
\begin{equation}
|p_{n}(x,y)-p_{n}(y,y)|\leq C\left( \frac{d(x,y)}{\sqrt{n}}\right) ^{\beta }%
\frac{1}{V(y,\sqrt{n})}  \tag{$PO$}
\end{equation}
for all $x,y\in \Gamma $ and $n\in \Bbb{N}^{\ast }$ such that $d(x,y)\leq
\delta \sqrt{n}$.
\end{definition}

It is easy to check that $(PO)$ together with the on-diagonal lower bound $%
(DLE)$ (which follows from $\left( UE\right) $ and $\left( VD\right) $)
imply $\left( LE\right) $. Indeed, one can write
\[
|p_{n}(x,y)-p_{n}(y,y)|\leq C^{\prime }\left( \frac{d(x,y)}{\sqrt{n}}\right)
^{\beta }p_{n}(y,y),
\]
and if one chooses $a\leq \delta $ such that $C^{\prime }a^{\beta }\leq
\frac{1}{2}$, then
\[
p_{n}(x,y)\geq \frac{1}{2}p_{n}(y,y)\geq \frac{c^{\prime }}{V(y,\sqrt{n})}%
\geq \frac{c^{\prime \prime }}{V(x,\sqrt{n})}
\]
for all $n\in \Bbb{N}^{\ast }$ and all $x,y\in \Gamma $ such that $%
d(x,y)\leq a\sqrt{n}$. Then, a classical iteration argument of Aronson \cite
{Aron} yields $\left( LE\right) $. Therefore, the main task is to obtain $%
(PO)$.

We recall here the discrete version of a classical result, known as
Cacciopoli inequality.

\begin{proposition}
There exists $C>0$ \textbf{\ [[ is this an absolute
constant????????????????]] }such that, for all $x\in \Gamma ,\ 0<r<R$, and
for all non-negative subharmonic functions $f$ on $B(x,R)$,
\begin{equation}
\mathcal{E}\left( f;B(x,r)\right) \leq \frac{C}{(R-r)^{2}}\sum_{y\in
B(x,R)}|f(y)|^{2}\mu (y).  \tag{$C$}
\end{equation}
\end{proposition}

It was proved in \cite{DelmotteEll}, using the Moser iteration argument,
that $(VD)$ and $(PI)$ imply an elliptic regularity estimate. An alternative
approach uses the ideas of De Giorgi (see \cite{AuCou}).

\begin{proposition}
Assume that $(\Gamma ,\mu )$ satisfies $(VD)$ and $(PI)$. Then there exist $%
\alpha ,C>0$ such that for every $x_{0}\in \Gamma ,\ R\geq 1,\ f\in \Bbb{R}%
^{\Gamma }$ harmonic in $B(x_{0},R)$ and $x,y\in B(x_{0},R/4)$, one has
\begin{equation}
|f(x)-f(y)|\leq C\left( \frac{d(x,y)}{R}\right) ^{\alpha }\left( \frac{1}{%
V(x_{0},R)}\sum_{z\in B(x_{0},R)}|f(z)-f_{R}(x_{0})|^{2}\mu (z)\right) ^{%
\frac{1}{2}}.  \tag{$ER$}
\end{equation}
\end{proposition}

We now show that
\[
(ER)~~\Longrightarrow ~~(DG).
\]
Indeed, if $f$ is harmonic in $B(x_{0},R)$ and $1\leq r\leq R/8$, write, for
$x\in B(x_{0},2r)$,
\begin{eqnarray*}
|f(x)-f_{2r}(x_{0})| &\leq &\frac{1}{V(x_{0},2r)}\sum_{y\in
B(x_{0},2r)}|f(x)-f(y)|\mu (y) \\
&\leq &\frac{C}{V(x_{0},2r)}\sum_{y\in B(x_{0},2r)}\left( \frac{d(x,y)}{R}%
\right) ^{\alpha }\left( \frac{1}{V(x_{0},R)}\sum_{z\in
B(x_{0},R)}|f(z)-f_{R}(x_{0})|^{2}\mu (z)\right) ^{\frac{1}{2}}\mu (y) \\
&\leq &C\left( \frac{r}{R}\right) ^{\alpha }\left( \frac{1}{V(x_{0},R)}%
\sum_{z\in B(x_{0},R)}|f(z)-f_{R}(x_{0})|^{2}\mu (z)\right) ^{\frac{1}{2}},
\end{eqnarray*}
thus
\[
\left( \sum_{x\in B(x_{0},2r)}|f(x)-f_{2r}(x_{0})|^{2}\mu (x)\right) ^{\frac{%
1}{2}}\leq C\left( \frac{r}{R}\right) ^{\alpha }\left( \frac{V(x_{0},2r)}{%
V(x_{0},R)}\sum_{z\in B(x_{0},R)}|f(z)-f_{R}(x_{0})|^{2}\mu (z)\right) ^{%
\frac{1}{2}}.
\]
By applying $(VD)$, $(PI)$ and $(C)$, we obtain
\[
\mathcal{E}\left( f;B(x_{0},r)\right) ^{\frac{1}{2}}\leq C\left( \frac{r}{R}%
\right) ^{\alpha -1}\left( \frac{V(x_{0},r)}{V(x_{0},R)}\mathcal{E}\left(
f,B(x_{0},R\right) )\right) ^{\frac{1}{2}}
\]
whenever $1\leq r\leq R/8$. On the other hand, if $R/8<r\leq R$ then the
result is trivial, hence $(DG)$ is obtained.

Finally, from the De Giorgi property $(DG)$ one can deduce $(PO)$ by proving
first the following ``inhomogeneous'' $(DG)$
\[
\mathcal{E}\left( f;B(x_{0},r)\right) \leq 8C\left( \frac{r}{R}\right)
^{2(\alpha -1)}\frac{V(x_{0},r)}{V(x_{0},R)}\mathcal{E}\left(
f;B(x_{0},R)\right) +2C^{\prime }R^{2}\sum_{y\in B(x_{0},R)}|f(y)|^{2}\mu
(y),
\]
where $\Delta u=f$ on $\Gamma $ and $C,\alpha $ are the constants in De
Giorgi's property. This inequality is similar to Morrey's fundamental
estimate on inhomogeneous elliptic equations and can be used to derive
parabolic estimates by following the ideas of \cite{Auscher}.

\section{Sub-Gaussian estimates}

\label{SecSub}\setcounter{equation}{0}

Recent development of analysis on fractals has brought into attention a new
class of graphs which exhibit in the large scale the same phenomena as
fractal sets in the small. One of the examples of such graphs is the Vicsek
tree discussed in Section \ref{SecVic}. Another example is shown on Fig. \ref
{pic2}.

\FRAME{ftbphFU}{4.0638in}{2.0764in}{0pt}{\Qcb{Graphical Sierpinski gasket}}{%
\Qlb{pic2}}{fpic2.wmf}{\special{language "Scientific Word";type
"GRAPHIC";maintain-aspect-ratio TRUE;display "USEDEF";valid_file "F";width
4.0638in;height 2.0764in;depth 0pt;original-width 6.5527in;original-height
3.4281in;cropleft "0";croptop "1";cropright "1";cropbottom "0";filename
'fpic2.wmf';file-properties "XNPEU";}}

A common feature of fractal-like graphs is that a standard random walk on
them exhibits a subdiffusive behavior. To be precise, let us introduce the
following hypotheses, for an arbitrary weighted graph $\left( \Gamma ,\mu
\right) $:

\begin{itemize}
\item  Upper estimate with parameter $\beta $: for all $x,y\in \Gamma $ and $%
n>0$%
\begin{equation}
p_{n}\left( x,y\right) \leq \frac{C}{V(x,n^{1/\beta })}\exp \left( -\left(
\frac{d^{\beta }(x,y)}{Cn}\right) ^{\frac{1}{\beta -1}}\right) .
\tag{$UE_{\beta }$}
\end{equation}

\item  Lower estimate with parameter $\beta $: for all $x,y\in \Gamma $ and
positive $n\geq d(x,y)$%
\begin{equation}
\left( p_{n}+p_{n+1}\right) \left( x,y\right) \geq \frac{c}{V(x,n^{1/\beta })%
}\exp \left( -\left( \frac{d^{\beta }(x,y)}{cn}\right) ^{\frac{1}{\beta -1}%
}\right) .  \tag{$LE_{\beta }$}
\end{equation}
\end{itemize}

Clearly, the hypothesis $(UE)$ introduced in the previous section coincides
with $(UE_{2})$. The condition $(LE)$ seems slightly stronger than $\left(
LE_{2}\right) $ as it claims the lower bound for $p_{n}$ rather than for $%
p_{n}+p_{n+1}$. However, this has to do with the fact that $\left( LE\right)
$ was obtained under the assumption $x\sim x$ which will not be assumed in
this section. In particular, now we do not exclude bipartite graphs.

It is possible to prove that if $\left( UE_{\beta }\right) $ and $\left(
LE_{\beta }\right) $ hold on $\left( \Gamma ,\mu \right) $ then necessarily $%
\beta \geq 2$. The case $\beta =2$ is referred to as Gaussian; a more
general case $\beta \geq 2$ is referred to as sub-Gaussian. If $\beta \geq 2$
and $n\geq d(x,y)$ then clearly
\[
\left( \frac{d^{\beta }(x,y)}{n}\right) ^{\frac{1}{\beta -1}}\geq \frac{%
d^{2}(x,y)}{n},
\]
which means that $p_{n}(x,y)$ decays with $d(x,y)$ faster in the
sub-Gaussian case rather than in Gaussian. At the same time, $V(x,n^{1/\beta
})\leq V(x,n^{1/2})$ that is $p_{n}(x,x)$ decays in $n$ slower in the
sub-Gaussian case. Therefore, the propagation of the random walks in the
sub-Gaussian case is in general slower than in the Gaussian; hence the name.

One may expect that the results discussed in Sections \ref{SecRel}, \ref
{SecGauss} should be extended (with proper modification) to the sub-Gaussian
case. However, such extensions are not straightforward and are not available
at the present time. Instead, we present here alternative characterizations
of sub-Gaussian estimates obtained in \cite{GrigTelLoc}, \cite{GrigTelTran}.

For any non-empty finite set $A\subset \Gamma $, let $\tau _{A}$ be the
\emph{first exit time} from $A$, that is
\[
\tau _{A}=\min \left\{ n\geq 0:X_{n}\notin A\right\} .
\]
Denote
\[
E(x,r)=\Bbb{E}_{x}\tau _{B(x,r)},
\]
which is the \emph{mean exit time} from the ball $B(x,r)$ starting from the
center.

For any couple of finite sets $A\subset B\subset \Gamma $, define the \emph{%
capacity} $\mathrm{Cap}(A,B)$ by
\begin{equation}
\mathrm{Cap}(A,B)=\inf_{f|_{A}=1,f|_{\complement B}=0}\mathcal{E}\left(
f\right) .  \label{cap-def}
\end{equation}
Consider the following hypotheses, where $\beta $ is a positive parameter.

\begin{itemize}
\item  \emph{Mean exit time estimate}: for all $x\in \Gamma $ and $r\geq 1$,
\begin{equation}
E(x,r)\simeq r^{\beta }.  \tag{$E_{\beta }$}
\end{equation}

\item  \emph{Capacity estimate:} for all $x\in \Gamma $ and $r\geq 1$,
\begin{equation}
\mathrm{Cap}\left( B(x,r),B(x,2r)\right) \simeq \frac{V(x,r)}{r^{\beta }}.
\tag{$Cap_{\beta }$}
\end{equation}

\item  \emph{Elliptic Harnack inequality:} for any non-negative harmonic
function $u(x)$ in a ball $B(x,2r)$, the following inequality holds:
\begin{equation}
\max_{B(x,r)}u\leq C\min_{B(x,r)}u,  \tag{$H$}
\end{equation}
with a constant $C$ that is the same for all $x\in \Gamma $ and $r>0$.

\item  \emph{Parabolic Harnack inequality} with parameter $\beta $:\emph{\ }
for all $x\in \Gamma $, $R\geq 1$ and for any non-negative function $%
u_{n}(y) $ defined for $n\in \lbrack 0,4T],$ $y\in B(x,2R+1)$ and satisfying
the heat equation $u_{n+1}=Pu_{n}$ in $[0,4T)\times B(x,2R)$, the following
inequality holds
\begin{equation}
\max\Sb n\in \lbrack T,2T)  \\ y\in B(x,R)  \endSb u_{n}(y)\leq C\min\Sb %
n\in \lbrack 3T,4T)  \\ y\in B(x,R)  \endSb \left(
u_{n}(y)+u_{n+1}(y)\right) ,  \tag{$PH_{\beta }$}
\end{equation}
provided $T$ is a positive integer such that $T\simeq R^{\beta }$ and $T\geq
2R$.
\end{itemize}

The hypothesis $\left( PH\right) $ introduced in the previous section
differs from $(PH_{2})$ only by using in the right hand side $u_{n}$ rather
than $u_{n}+u_{n+1}$. Let us also observe that $(PH_{\beta })\Longrightarrow
(H)$ for any $\beta $.

\begin{theorem}
\label{Tloc}\emph{\cite[Theorem 3.1]{GrigTelLoc}} Assume that $\left( \Gamma
,\mu \right) $ satisfies the following condition:
\begin{equation}
P(x,y)\geq \varepsilon >0,\quad \text{for all }x\sim y.  \label{p0}
\end{equation}
Then
\begin{equation}
\left( UE_{\beta }\right) +\left( LE_{\beta }\right) \Longleftrightarrow
\left( PH_{\beta }\right) \Longleftrightarrow \left( VD\right) +\left(
H\right) +\left( E_{\beta }\right) \Longleftrightarrow \left( VD\right)
+\left( H\right) +\left( Cap_{\beta }\right) .  \label{all}
\end{equation}
\end{theorem}

For the case $\beta =2$, this theorem admits the following extension
\cite[Corollary 3.2]{GrigTelLoc}:
\[
\left( UE_{2}\right) +\left( LE_{2}\right) \Longleftrightarrow \left(
PH_{2}\right) \Longleftrightarrow \left( VD\right) +\left( H\right) +\left[
\lambda _{1}\left( B(x,r)\right) \geq cr^{-2}\right] .
\]
The most important point of Theorem \ref{Tloc} is that it shows the
difference between the elliptic Harnack inequality $\left( H\right) $ and
the parabolic one $\left( PH_{\beta }\right) $. Indeed, as one sees from (%
\ref{all}) the difference is $\left( VD\right) $ and one of the conditions $%
\left( E_{\beta }\right) $ or $\left( Cap_{\beta }\right) $ which determine
the parameter $\beta $. An example of Delmotte \cite{Delmottebet} shows that
$\left( H\right) $ does not imply $\left( VD\right) $; it is easy to see
that $\left( H\right) $ does not imply $\left( E_{\beta }\right) $ either.

A deep question related to the above considerations is to provide a
geometric understanding of the elliptic Harnack inequality $(H)$. This
question is still open, also in the continuous setting of manifolds.

If $(VD)$ and $(Cap_{\beta })$ are satisfied then necessarily $\beta \geq 2$%
. Indeed, the following upper estimate of capacity is always true
\[
\mathrm{Cap}(B(x,r),B(x,2r))\leq \frac{V(x,2r)}{r^{2}}
\]
(it follows by taking a standard cut-off function in definition (\ref
{cap-def}) of capacity). Combining with $(VD)$ and $(Cap_{\beta })$, we
conclude $\beta \geq 2$.

The following theorem extends further the line of equivalences (\ref{all}).

\begin{theorem}
Assume that $\left( \Gamma ,\mu \right) $ satisfies the condition (\ref{p0}%
). Then
\begin{equation}
\left( VD\right) +\left( H\right) +\left( UE_{\beta }\right) \Longrightarrow
\left( LE_{\beta }\right) .  \label{V+H+UE=>LE}
\end{equation}
In particular,
\[
\left( VD\right) +\left( H\right) +\left( UE_{\beta }\right)
\Longleftrightarrow \left( UE_{\beta }\right) +\left( LE_{\beta }\right)
\Longleftrightarrow \left( PH_{\beta }\right) .
\]
\end{theorem}

A continuous version of this result was proved in \cite{HebSChar}. A similar
approach can be used in the graph case (see \cite[Remark 15.1]{GrigTelTran}).

Examples of graphs satisfying sub-Gaussian estimates $\left( UE_{\beta
}\right) +\left( LE_{\beta }\right) $ can be found in \cite{BarBassGraph},
\cite{Jones}, \cite{GrigTelLoc}. In most of these examples, the volume
growth function satisfies a uniform estimate
\begin{equation}
V(x,r)\simeq r^{\alpha },  \tag{$V_{\alpha }$}
\end{equation}
for all $x\in \Gamma $,\ $r\geq 1$, for some parameter $\alpha $. In this
case, the sub-Gaussian estimates become as follows:
\begin{equation}
p_{n}(x,y)\leq \frac{C}{n^{\alpha /\beta }}\exp \left( -\left( \frac{%
d^{\beta }(x,y)}{Cn}\right) ^{\frac{1}{\beta -1}}\right)
\tag{$UE_{\alpha
,\beta }$}
\end{equation}
and
\begin{equation}
\left( p_{n}+p_{n+1}\right) (x,y)\geq \frac{c}{n^{\alpha /\beta }}\exp
\left( -\left( \frac{d^{\beta }(x,y)}{cn}\right) ^{\frac{1}{\beta -1}%
}\right) .  \tag{$LE_{\alpha ,\beta }$}
\end{equation}
Then Theorem \ref{Tloc} yields the equivalence
\[
\left( UE_{\alpha ,\beta }\right) +\left( LE_{\alpha ,\beta }\right)
\Longleftrightarrow \left( V_{\alpha }\right) +\left( H\right) +\left(
E_{\beta }\right) .
\]

In general, the parameters $\alpha ,\beta $ must satisfy the following
relations
\begin{equation}
2\leq \beta \leq \alpha +1  \label{ab-range}
\end{equation}
(see \cite[Section 2]{GrigTelTran}). Indeed, $\beta \geq 2$ was proved
above. To show that $\beta \leq \alpha +1$ let us recall that $(V_{\alpha })$
implies by Theorem \ref{Tbig}
\[
p_{n}(x,x)\leq Cn^{-\frac{\alpha }{\alpha +1}}.
\]
Comparing with the on-diagonal lower bound which follows from $(LE_{\alpha
,\beta })$ we obtain $\beta \leq \alpha +1.$

The Vicsek tree with parameter $D$ described in Section \ref{SecVic}
satisfies all the above conditions with $\alpha =D$ and $\beta =D+1$ (see
\cite{GrigTelLoc}). Hence, in this case $\beta =\alpha +1$ which is the
borderline case for $\alpha $ and $\beta $ in (\ref{ab-range}). The
Sierpinski gasket on Fig. \ref{pic2} satisfies $\left( UE_{\alpha ,\beta
}\right) +\left( LE_{\alpha ,\beta }\right) $ with $\alpha =\log _{2}3$ and $%
\beta =\log _{2}5$ (see \cite{Jones}).

In both these examples we have $\alpha <\beta $. If on the contrary $\alpha
>\beta $ then the sub-Gaussian estimates admit another characterization in
terms of the Green kernel $g(x,y)$ that is defined by
\[
g(x,y)=\sum_{n=0}^{\infty }p_{n}(x,y)
\]
(alternatively, $g(x,y)$ is the kernel of the operator $\left( -\Delta
\right) ^{-1}$). It is straightforward that $\left( UE_{\alpha ,\beta
}\right) $ and $\left( LE_{\alpha ,\beta }\right) $ imply
\begin{equation}
g(x,y)\simeq d(x,y)^{-\left( \alpha -\beta \right) },\quad \text{for all }%
x\neq y,  \tag{$G_{\alpha -\beta }$}
\end{equation}
provided $\alpha >\beta $.

\begin{theorem}
\emph{\cite{GrigTelTran}} Let $\left( \Gamma ,\mu \right) $ satisfy (\ref{p0}%
) and let $\alpha >\beta \geq 2$. Then
\[
\left( UE_{\alpha ,\beta }\right) +\left( LE_{\alpha ,\beta }\right)
\Longleftrightarrow \left( V_{\alpha }\right) +\left( G_{\alpha -\beta
}\right) .
\]
\end{theorem}

%TCIMACRO{
%\TeXButton{Bibliography}{{\footnotesize
%\begin{thebibliography}{9}
%\input bibstyle
%\input tcirefs
%\end{thebibliography}
%}
%}}%
%BeginExpansion
{\footnotesize
\begin{thebibliography}{9}
\input bibstyle
\input tcirefs
\end{thebibliography}
}
%
%EndExpansion

\end{document}