Volume growth and spectrum for general graph Laplacians

Abstract

We prove estimates relating exponential or sub-exponential volume growth of weighted graphs to the bottom of the essential spectrum for general graph Laplacians. The volume growth is computed with respect to a metric adapted to the Laplacian, and use of these metrics produces better results than those obtained from consideration of the graph metric only. Conditions for absence of the essential spectrum are also discussed. These estimates are shown to be optimal or near-optimal in certain settings and apply even if the Laplacian under consideration is an unbounded operator.

1 Introduction

Let $\Gamma =(G,E)$ be an unoriented, connected, countably infinite, locally finite graph. We assume that $\Gamma$ has neither loops nor multiple edges. We use $d$ to denote the graph metric on $\Gamma$; given $x,y\in G$, $d(x,y)$ is equal to the number of edges in a shortest (geodesic) path between $x$ and $y$.

We assume that $\Gamma$ is a weighted graph, so that associated with each $(x,y)\in G\times G$ is a nonnegative edge weight $\pi _{xy}$ which is symmetric ($\pi _{xy}=\pi _{yx}$ for $x,y\in G$) and satisfies $\pi _{xy}>0$ if and only if $\{x,y\}\in E$. The edge weights define a measure on $G$ by setting $\pi _x := \pi (\{x\}) := \sum _{y\in G} \pi _{xy}$ for $x\in G$, and extending to all subsets of $G$ by countable additivity. If $\pi (e)=1$ for all $e\in E$, we say that $\Gamma$ has the standard weights. We denote weighted graphs by the pair $(\Gamma , (\pi (e))_{e\in E})$; for brevity we write this as $(\Gamma ,\pi )$.

Let $(\theta _x)_{x\in G}$ be an additional set of positive vertex weights. We will assume that the weights $(\theta _x)_{x\in G}$ are such that whenever $U\subset G$ is an infinite subset which is connected in $\Gamma$,

$$\begin{aligned} \sum _{x\in U} \theta _x = \infty . \end{aligned}$$

(1.1)

This condition is a discrete analogue of the assumption in [1] that the manifold under consideration is non-compact and has infinite volume.

We will work on the (real) Hilbert space $L^2(\theta )$ with inner product

$$\begin{aligned} \langle f,g\rangle _{L^2(\theta )} := \sum _{x\in G} f(x)g(x)\theta _x. \end{aligned}$$

The central object of our analysis will be the graph Laplacian $\mathcal{L }_\theta$, which is defined pointwise for $f\in L^2(\theta )$ by

$$\begin{aligned} (\mathcal{L }_\theta f)(x) := \frac{1}{\theta _x}\sum _{y\sim x}\pi _{xy}(f(y)-f(x)), \end{aligned}$$

and which has domain of definition $\mathcal{D }(\mathcal{L }_\theta ) := \{f\in L^2(\theta ):\mathcal{L }_\theta f\in L^2(\theta )\}$. This operator is associated with the Dirichlet form $(\mathcal{E },\mathcal{D }(\mathcal{E }))$, where, for $f,g\in \mathcal{D }(\mathcal{E })$,

$$\begin{aligned} \mathcal{E }(f,g) := \frac{1}{2}\sum _{x,y\in G} \pi _{xy}(f(y)-f(x))(g(y)-g(x)). \end{aligned}$$

We define $\mathcal{E }_1(f,f) := \langle f,f\rangle _{L^2(\theta )} + \mathcal{E }(f,f)$ and let $\Vert \cdot \Vert _{\mathcal{E }}:=\mathcal{E }_1(\cdot ,\cdot )^{1/2}$ denote the induced norm. The domain $\mathcal{D }(\mathcal{E })$ is given by the closure of $C_c(G)$ in the norm $\Vert \cdot \Vert _{\mathcal{E }}$. Consequently $(\mathcal{E },\mathcal{D }(\mathcal{E }))$ is a closed, regular Dirichlet form. See [11] for more on the theory of Dirichlet forms.

Remark 1.1

The condition (1.1) together with the local finiteness of $\Gamma$ ensures that the infinitesimal generator associated with the regular Dirichlet form $(\mathcal{E },\mathcal{D }(\mathcal{E }))$ is the operator $\mathcal{L }_\theta$ with domain $\mathcal{D }(\mathcal{L }_\theta )$. Moreover the operator $\mathcal{L }_\theta$ with domain $\mathcal{D }(\mathcal{L }_\theta )$ is self-adjoint, and the restriction of $\mathcal{L }_\theta$ to $C_c(G)$ is essentially self-adjoint; these assertions follow from Theorem 5 of [16].

The generator and Dirichlet form are linked by the Gauss-Green identity; for $f\in \mathcal{D }(\mathcal{L }_\theta )$ and $g\in \mathcal{D }(\mathcal{E })$,

$$\begin{aligned} \mathcal{E }(f,g) = -\langle \mathcal{L }_\theta f,g\rangle _{L^2(\theta )}. \end{aligned}$$

(1.2)

In particular, $\langle -\mathcal{L }_\theta f,f\rangle _{L^2(\theta )} = \mathcal{E }(f,f) \ge 0$, and the operator $-\mathcal{L }_\theta$ is positive semidefinite.

In general, $\mathcal{L }_\theta$ is not a bounded operator on $L^2(\theta )$. Define

$$\begin{aligned} A(\Gamma ,\pi ,\theta ) := \sup _{x\in G} \frac{\pi _x}{\theta _x}, \end{aligned}$$

and let $\Vert \cdot \Vert$ denote the norm on $L^2(\theta )$. Then $A(\Gamma ,\pi ,\theta ) \le \Vert \mathcal{L }_\theta \Vert \le 2A(\Gamma ,\pi ,\theta )$, and $\mathcal{L }_\theta$ is bounded if and only if $A(\Gamma ,\pi ,\theta )<\infty$. See Lemma 1 of [4] for a proof. Additionally, for this quantity and subsequent quantities which depend on the edge weights $(\pi (e))_{e\in E}$, if the edge weights under consideration are the standard weights, we will simply omit reference to the edge weights and write (for example) $A(\Gamma ,\theta )$.

Each choice of $(\theta _x)_{x\in G}$ corresponds to a continuous-time simple random walk on $(\Gamma ,\pi )$ with infinitesimal generator $\mathcal{L }_\theta$. Fix $\theta$ and denote the corresponding random walk by $(X_t)_{t\ge 0}$. This process is strong Markov; started at a vertex $x\in G$, it waits an exponentially distributed time with parameter $\pi _x\!/\!\theta _x$ and then jumps to a neighbour with jump probabilities $P(x,y) := \pi _{xy}\!/\!\pi _x$. In particular, modifying the vertex weights $(\theta _x)_{x\in G}$ induces a time-change of the random walk; the jump times change but not the jump probabilities.

We single out two choices of the vertex weights $(\theta _x)_{x\in G}$. The first is the choice $(\pi _x)_{x\in G}$. The corresponding random walk is referred to as the constant-speed random walk (because it jumps at exponentially distributed times with mean 1), and has infinitesimal generator

$$\begin{aligned} (\mathcal{L }_\pi f)(x) := \frac{1}{\pi _x}\sum _{y\sim x}\pi _{xy}(f(y)-f(x)). \end{aligned}$$

This operator is sometimes called the probabilistic or normalized Laplacian; it is a bounded operator on $L^2(\pi )$ satisfying $1\le \Vert \mathcal{L }_\pi \Vert \le 2$.

The second choice are the vertex weights $({1\!\!1}_x)_{x\in G}$, where ${1\!\!1}_x := 1$ for each $x\in G$. The corresponding random walk is called the variable-speed random walk (because it jumps at exponentially distributed times with parameter $\pi _x$), and has infinitesimal generator

$$\begin{aligned} (\mathcal{L }_{1\!\!1}f)(x) := \sum _{y\sim x} \pi _{xy}(f(y)-f(x)). \end{aligned}$$

This operator is sometimes called the physical or unnormalized Laplacian, and is a bounded operator on $L^2(1\!\!1)$ if and only if the weights $(\pi _x)_{x\in G}$ are bounded above.

Associated with the process $(X_t)_{t\ge 0}$ is the semigroup $(P_t)_{t\ge 0}$, where $P_t = \exp (t\mathcal{L }_\theta )$ (or, equivalently, $P_tf(x) := \mathbb{E }^xf(X_t)$). The semigroup has a transition density $p_t(x,y)$ with respect to the measure $\theta$ given by

$$\begin{aligned} p_t(x,y) := \frac{1}{\theta _y}\mathbb{P }^x(X_t=y). \end{aligned}$$

The function $p_t(x,y)$ is also called the heat kernel of $(X_t)_{\ge 0}$.

1.1 Metrics and volume

Definition

The metric $\rho$ is adapted to the operator $\mathcal{L }_\theta$ on $(\Gamma ,\pi )$ if for all $x\in G$,

$$\begin{aligned} \frac{1}{\theta _x}\sum _{y\sim x}\pi _{xy}\rho ^2(x,y) \le 1, \end{aligned}$$

(1.3)

and there exists $c_\rho >0$ such that $\rho (x,y) \le c_\rho$ whenever $x\sim y$.

The following metrics are useful examples of adapted metrics:

• 1. On any weighted graph, the graph metric $d$ is adapted to the operator $\mathcal{L }_\pi$. More generally, if $\mathcal{L }_\theta$ is bounded (so that $A(\Gamma ,\pi ,\theta )<\infty$), then the metric $\frac{1}{\sqrt{A(\Gamma ,\pi ,\theta )}}d$ is adapted to $\mathcal{L }_\theta$. No fixed multiple of the graph metric can be adapted to $\mathcal{L }_\theta$ if $\mathcal{L }_\theta$ is an unbounded operator. In this case, since there is no uniform upper bound on $\pi _x/\theta _x$, given a metric $\rho$ adapted to $\mathcal{L }_\theta$, for any $\varepsilon >0$, one can find adjacent vertices $x$ and $y$ with $\rho (x,y)\le \varepsilon$.

• 2. On any weighted graph with vertex degrees uniformly bounded above by $D$, the metric $\frac{1}{\sqrt{D}}d_E$ is adapted to the operator $\mathcal{L }_{1\!\!1}$, where for $x,y\in G$,

  $$\begin{aligned} d_E(x,y) := \inf \left\{ \sum _{e\in \gamma } 1\wedge \pi (e)^{-1/2}: \gamma \text{ is } \text{ a } \text{ path } \text{ joining } x \text{ and } y\right\} . \end{aligned}$$

  If the graph is $k-$regular and $\pi (e) \ge 1$ for all $e\in E$, then at each $x\in G$ there is equality in (1.3).

• 3. On any weighted graph, the metric $d_V$ is adapted to the operator $\mathcal{L }_\theta$, where for $x,y\in G$,

  $$\begin{aligned} d_V(x,y) := \inf \left\{ \sum _{e\in \gamma } 1\wedge c(e):\gamma \text{ is } \text{ a } \text{ path } \text{ joining } x \text{ and } y\right\} , \end{aligned}$$

  and for $e := \{u,v\}$,

  $$\begin{aligned} c(e) := \left( \frac{\theta _u}{\pi _u}\wedge \frac{\theta _v}{\pi _v}\right) ^{1/2}. \end{aligned}$$

  This definition has appeared in several recent papers; see [6] and [7] by the author, where adapted metrics are used to obtain heat kernel estimates and criteria for stochastic completeness, [8], where a general notion of intrinsic metric for non-local symmetric Dirichlet forms is defined which coincides with the definition of adaptedness in the present setting, [12], where adapted metrics are used to obtain criteria for stochastic completeness, and [13], which deals with uniqueness of solutions to the heat equation. The condition (1.3) also is closely related to certain distance functions on graphs considered by Davies in [3]. The relationship between adapted metrics and other metrics which have appeared in the study of heat flow or random walks on graphs is discussed in Sect. 2 of [7].

Let $\rho$ be a metric adapted to the operator $\mathcal{L }_\theta$. Write

$$\begin{aligned} B_\rho (x_0,r) := \{x\in G:\rho (x_0,x)\le r\} \end{aligned}$$

for the closed ball of radius $r$ in this metric, and

$$\begin{aligned} V_\rho (x_0,r) := \sum _{x\in B_\rho (x_0,r)} \theta _x \end{aligned}$$

for the volume of this ball with respect to the measure $(\theta _x)_{x\in G}$.

We define the exponential rate of volume growth of $(\Gamma ,\pi )$ with respect to the measure $\theta$ and the adapted metric $\rho$ by

$$\begin{aligned} \mu _\rho (\Gamma ,\pi ,\theta ) := \limsup _{r\rightarrow \infty } \frac{1}{r}\log V_\rho (x_0,r). \end{aligned}$$

(1.4)

An application of the triangle inequality shows that the right hand side of (1.4) is independent of the choice of $x_0\in G$.

If $\mu _\rho (\Gamma ,\pi ,\theta )=0$ (respectively $\mu _\rho (\Gamma ,\pi ,\theta )\in (0,\infty )$, $\mu _\rho (\Gamma ,\pi ,\theta )=\infty$), we say that $\Gamma$ has subexponential (respectively exponential, superexponential) volume growth with respect to the measure $\theta$ and the metric $\rho$.

1.2 Spectra

Let $\sigma (\Gamma ,\pi ,\theta )$ denote the spectrum of $-\mathcal{L }_\theta$ on $(\Gamma ,\pi )$. As a positive semidefinite self-adjoint operator, the bottom of the spectrum of $-\mathcal{L }_\theta$ is nonnegative, and we denote it by $\lambda _0(\Gamma ,\pi ,\theta )$.

We have the following variational expression for the bottom of the spectrum:

$$\begin{aligned} \lambda _0(\Gamma ,\pi ,\theta ) := \inf \{\mathcal{E }(f,f):f\in \mathcal{D }(\mathcal{E }), \quad \Vert f\Vert ^2_{L^2(\theta )} = 1\}. \end{aligned}$$

(1.5)

For $V\subset G$, we let $\mathcal{L }^V_\theta$ denote the Dirichlet Laplacian on $V$, which is defined pointwise by

$$\begin{aligned} (\mathcal{L }^V_\theta f)(x) := \left\{ \begin{array}{l@{\quad }l} (\mathcal{L }_\theta f)(x) &{}\text{ if } x\in V, \\ 0 &{}\text{ if } x\in G{\setminus }V,\\ \end{array}\right. \end{aligned}$$

and which has domain of definition $\mathcal{D }(\mathcal{L }^V_\theta ) := \mathcal{D }(\mathcal{L }_\theta )\cap \{f\in L^2(\theta ):f|_{G{\setminus }V} = 0\}$.

Let $\lambda ^V_0(\Gamma ,\pi ,\theta )$ denote the bottom of the spectrum of the Dirichlet Laplacian on $V$. If $(G_k)_{k\in \mathbb{Z }_+}$ are finite sets which increase to $G$, then we have that as $k\rightarrow \infty$,

$$\begin{aligned} \lambda ^{G_k}_0(\Gamma ,\pi ,\theta ) \downarrow \lambda _0(\Gamma ,\pi ,\theta ); \end{aligned}$$

(1.6)

this follows from the fact that if $U\subset V$, then $\lambda ^U_0(\Gamma ,\pi ,\theta ) \ge \lambda ^V_0(\Gamma ,\pi ,\theta )$, together with (1.5) and the fact that $C_c(G)$ is dense in $\mathcal{D }(\mathcal{E })$ with respect to the $\Vert \cdot \Vert _{\mathcal{E }}$ norm.

A direct calculation, together with (1.5), shows that for $f\in L^2(\theta )$,

$$\begin{aligned} \frac{d}{dt}\Vert P_t f\Vert ^2_{L^2(\theta )} = -2\langle \mathcal{L }_\theta P_t f,P_t f\rangle _{L^2(\theta )} \le -2\lambda _0(\Gamma ,\pi ,\theta )\Vert P_t f\Vert ^2, \end{aligned}$$

and this differential inequality together with $P_0=I$ gives $\Vert P_t\Vert \le \exp (-\lambda _0(\Gamma ,\pi ,\theta )t)$. On the other hand, given $V\subset G$, let $(P^V_t)_{t\ge 0}$ denote the Dirichlet heat semigroup defined by

$$\begin{aligned} (P^V_tf)(x) = \sum _{y\in G} p^V_t(x,y)f(y)\theta _y, \end{aligned}$$

where $p^V_t(x,y)$ denotes the heat kernel of the Dirichlet Laplacian on $V$ (a construction is given in Lemma 4.5 of [22]). Since $\mathcal{L }^V_\theta$ and $P^V_t$ commute on $\mathcal{D }(\mathcal{L }^V_\theta )$ (see Lemma 4.13 of [22]), if $(G_k)_{k\in \mathbb{Z }_+}$ are finite sets which increase to $G$, and $\lambda _k := \lambda ^{G_k}_0(\Gamma ,\theta ,\pi )$ has the corresponding eigenfunction $f_k$, it follows that for all $k\in \mathbb{Z }_+$,

$$\begin{aligned} \frac{d}{dt}\Vert P_t f_k\Vert ^2_{L^2(\theta )} = -2\langle \mathcal{L }^{G_k}_\theta P^{G_k}_t f_k,P^{G_k}_t f_k\rangle _{L^2(\theta )} = -2\lambda _k \Vert P^{G_k}_t f_k\Vert ^2_{L^2(\theta )}. \end{aligned}$$

This differential equation yields $\Vert P^{G_k}_t\Vert \ge \exp (-\lambda _k t)$, and using (1.6) together with the fact that $0 \le p^{G_k}_t(x,y)\le p_t(x,y)$ for $k\in \mathbb{Z }_+$ allows us to conclude that $\Vert P_t\Vert = \exp (-\lambda _0(\Gamma ,\pi ,\theta )t)$.

In Theorem 3.1 of [19] an analogous pointwise bound for the heat kernel is proved; for all $x,y\in G$,

$$\begin{aligned} \lim _{t\rightarrow \infty }\frac{1}{t}\log p^\theta _t(x,y) \rightarrow -\lambda _0(\Gamma ,\pi ,\theta ). \end{aligned}$$

We will work primarily with the essential spectrum of $-\mathcal{L }_\theta$. The essential spectrum $\sigma _{ \text{ ess }}(\Gamma ,\pi ,\theta )$ consists of points of $\sigma (\Gamma ,\pi ,\theta )$ which are either accumulation points of $\sigma (\Gamma ,\pi ,\theta )$ or which are discrete eigenvalues of $-\mathcal{L }_\theta$ with infinite multiplicity. The discrete spectrum of $-\mathcal{L }_\theta$ is defined by $\sigma _{\text{ disc }}(\Gamma ,\pi ,\theta ) = \sigma (\Gamma ,\pi ,\theta ){\setminus }\sigma _{ \text{ ess }}(\Gamma ,\pi ,\theta )$.

We denote the bottom of the essential spectrum by $\lambda ^{ \text{ ess }}_0(\Gamma ,\pi ,\theta )$. Clearly, $\lambda _0(\Gamma ,\pi ,\theta ) \le \lambda ^{{ \text{ ess }}}_0(\Gamma ,\pi ,\theta )$. The essential spectrum is invariant under finite perturbations (see Lemma 1 of [10]), and if $(G_k)_{k\in \mathbb{Z }_+}$ is any sequence of finite subsets of $G$ which increase to $G$, then

$$\begin{aligned} \lambda ^{ \text{ ess }}_0(\Gamma ,\pi ,\theta ) = \lim _{k\rightarrow \infty } \lambda ^{G{\setminus }G_k}_0(\Gamma ,\pi ,\theta ); \end{aligned}$$

(1.7)

see Proposition 18 of [17] for a proof of (1.7).

1.3 Results

In the setting of Riemannian manifolds, Brooks proved the following result relating volume growth in the Riemannian metric with the bottom of the spectrum:

Theorem 1.1

(Brooks, [1]) Let $M$ be a smooth, complete, non-compact Riemannian manifold with Riemannian metric $\rho _M$ and Riemannian volume $V_M$. Let $\lambda ^{ \text{ ess }}_0(M)$ denote the bottom of the essential spectrum of the Laplace-Beltrami operator $-\Delta _M$ on $L^2(M)$. Define, for some $x_0\in M$,

$$\begin{aligned} \mu _M := \limsup _{r\rightarrow \infty } \frac{1}{r}\log V_M(B_{\rho _M}(x_0,r)). \end{aligned}$$

If $M$ has infinite volume, then

$$\begin{aligned} \lambda _0^{ \text{ ess }}(M) \le \frac{1}{4}\mu ^2_M. \end{aligned}$$

A similar estimate was subsequently established in the more general setting of strongly local Dirichlet spaces in [20].

In the setting of unweighted graphs (where the associated Dirichlet form is nonlocal), Fujiwara proved an analogue of these results for the spectrum of the operator $-\mathcal{L }_\pi$:

Theorem 1.2

(Fujiwara, [9]) If $\Gamma$ is an unoriented, connected, countably infinite, locally finite graph with the standard weights, and $\mu _\Gamma := \mu _d(\Gamma ,\pi )$, then

$$\begin{aligned} \lambda ^{ \text{ ess }}_0(\Gamma ,\pi ) \le 1-\frac{2\exp (\mu _\Gamma {/}2)}{1+\exp (\mu _\Gamma )}. \end{aligned}$$

While the Laplace-Beltrami operator $\Delta _M$ considered by Brooks may be unbounded, the operator $\mathcal{L }_\pi$ considered by Fujiwara is bounded. In this setting, there is no need to consider metrics besides the graph metric, and the boundedness of $\mathcal{L }_\pi$ rules out various interesting behaviors, such as absence of essential spectrum, or the possibility of stochastic incompleteness.

We have two main results for the bottom of the essential spectrum in the setting of weighted graphs. For notational simplicity, given a metric $\rho$ which is adapted to the operator $\mathcal{L }_\theta$ on $(\Gamma ,\pi )$, we denote the exponential volume growth in this metric by $\mu _\rho := \mu _\rho (\Gamma ,\pi ,\theta )$.

Our first result is an analogue of Theorem 1.1 for weighted graphs, and is valid even when $\mathcal{L }_\theta$ is unbounded.

Theorem 1.3

Let $(\Gamma ,\pi )$ be a weighted graph, and let the positive vertex weights $(\theta _x)_{x\in G}$ satisfy (1.1). If $\rho$ is a metric adapted to $\mathcal{L }_\theta$ and $\mu _\rho$ denotes the exponential rate of volume growth in this metric, then

$$\begin{aligned} \lambda ^{ \text{ ess }}_0(\Gamma ,\pi ,\theta ) \le \frac{1}{8}\mu _\rho ^2. \end{aligned}$$

The exponent $2$ cannot be reduced; see Example 4.1.

Our second result generalizes results of Fujiwara in [6] and yields better results than Theorem 1.3 when $\mathcal{L }_\theta$ is bounded and $\mu$ is large.

Theorem 1.4

Let $(\Gamma ,\pi )$ be a weighted graph, and let the positive vertex weights $(\theta _x)_{x\in G}$ satisfy (1.1). If $\rho$ is a metric adapted to $\mathcal{L }_\theta$ for which there exist positive constants $m,M$ such that $m\le \rho (x,y)\le M$ whenever $x\sim y$, and $\mu _\rho$ denotes the exponential rate of volume growth in this metric, then

$$\begin{aligned} \lambda ^{ \text{ ess }}_0(\Gamma ,\pi ,\theta ) \le \frac{1}{m^2}\frac{(1-\exp (\frac{1}{2}M\mu _\rho ))^2}{1+\exp (M\mu _\rho )}. \end{aligned}$$

(1.8)

Adapted metrics satisfying the conditions in this theorem exist if and only if $\mathcal{L }_\theta$ is a bounded operator. On the $k-$regular tree with the standard weights, there is equality in (1.8) for $\mathcal{L }_\pi$ when using the graph metric $d$, or for $\mathcal{L }_{1\!\!1}$ when using the metric $\frac{1}{\sqrt{k}}d$; see Example 4.1.

Theorem 1.3 has the following two immediate corollaries:

Corollary 1.5

If there exists an adapted metric $\rho$ such that $\mu _\rho (\Gamma ,\pi ,\theta )=0$, then $\lambda ^{ \text{ ess }}_0(\Gamma ,\pi ,\theta )=0$.

The converse of this statement is false; a counterexample is provided by the operator $\mathcal{L }_\pi$ on the Cayley graph of any solvable group with exponential growth (see [5]), such as the lamplighter group.

Corollary 1.6

If there exists an adapted metric $\rho$ such that $\mu _\rho (\Gamma ,\pi ,\theta )<\infty$, the essential spectrum is nonempty.

This result cannot be improved upon in the following sense: For every $\varepsilon >0$, there exists a graph $(\Gamma ,\pi )$ for which the essential spectrum of $\mathcal{L }_{1\!\!1}$ is empty, but there exists an adapted metric $\rho$ such that

$$\begin{aligned} \limsup _{r\rightarrow \infty } \frac{1}{r^{1+\varepsilon }} \log V_{\rho }(x_0,r) < \infty . \end{aligned}$$

See Example 4.2.

The main contribution of this paper is to establish quantitative upper bounds for the bottom of the essential spectrum in terms of the adapted volume growth, which are valid for unbounded graph Laplacians, and which are sharp or asymptotically sharp in various instances. The similarities between the results of this paper and the corresponding results for manifolds (and strongly local Dirichlet spaces) provide further evidence that adapted metrics are a powerful tool for studying heat flow and random walks on graphs where the graph Laplacian is unbounded.

Shortly after this work was completed, Haeseler, Keller, and Wojciechowski proved similar results in the more general setting of regular Dirichlet forms (both local and non-local) in [14]. Their paper contains proofs of Theorems 1.3 and  1.4 using slightly different techniques. They also discuss the relationship between volume growth in the graph metric and positivity of the bottom of the spectrum or nonemptiness of the essential spectrum, and show that the threshold for these properties lies at cubic volume growth (with respect to the graph metric).

The structure of this paper is as follows. We prove Theorem 1.4 and  1.3 in Sect. 2; this is accomplished by using techniques of Brooks and Fujiwara together with the adapted metrics defined earlier. In particular, the Dirichlet forms of certain functions of these metrics can be controlled by the $L^2(\theta )$ norm. In Sect. 3, we discuss the phenomena of absence of essential spectrum and its relation to volume growth, and in Sect. 4, we provide various examples showing the sharpness of our results, as well as settings where the graph metric gives very poor results and the use of adapted metrics seems to be essential.

2 Proofs

We begin by fixing a weighted graph $(\Gamma ,\pi )$ and a set of positive vertex weights $(\theta _x)_{x\in G}$ satisfying (1.1). We also fix a metric $\rho$ which is adapted to the operator $\mathcal{L }_\theta$, and set $\rho _{x_0}(x) := \rho (x_0,x)$ for $x_0\in G$. By the triangle inequality, $|\rho _{x_0}(x)-\rho _{x_0}(y)|\le \rho (x,y)$. To simplify notation, we set $\mu := \mu _\rho (\Gamma ,\pi ,\theta )$.

We note that it suffices to assume that $\mu < \infty$. If $\mu = \infty$, then the conclusion of Theorem 1.3 is $\lambda ^{ \text{ ess }}_0(\Gamma ,\pi ,\theta )\le \infty$, which is trivial. If the hypotheses of Theorem 1.4 are satisfied (with $m \le \rho (x,y)$ whenever $x\sim y$) and $\mu =\infty$, then the conclusion of Theorem 1.4 is

$$\begin{aligned} \lambda ^{ \text{ ess }}_0(\Gamma ,\pi ,\theta )\le \frac{1}{m^2}. \end{aligned}$$

(2.1)

This estimate may be proven directly by noting that for $x\in G$, $\Vert \theta _x^{-1/2}\mathbf{1}_x\Vert _{L^2(\theta )} = 1$, and

$$\begin{aligned} \mathcal{E }(\theta _x^{-1}\mathbf{1}_x,\theta _x^{-1}\mathbf{1}_x) = \frac{\pi _x}{\theta _x} \le \frac{1}{m^2}, \end{aligned}$$

(2.2)

where the last inequality follows from adaptedness of $\rho$ and the inequality $m\le \rho (x,y)$ for $x\sim y$. The inequality (2.1) then follows from (2.2) and (1.5).

In particular, the assumption $\mu <\infty$ implies that for all $x_0\in G$ and $r\ge 0$, the balls $B_\rho (x_0,r)$ have finite volume (i.e., for all $x_0\in G$ and $r\ge 0$, $V_\rho (x_0,r)<\infty )$. Combining this with (1.1), we see that for $x_0\in G$ and $r\ge 0$, the balls $B_\rho (x_0,r)$ contain only finitely many points, as well.

The proof follows the general techniques of [1] and [6].

Lemma 2.1

If $\mu < 2\alpha$, then $\langle \exp (-\alpha \rho _{x_0}),\exp (-\alpha \rho _{x_0}) \rangle _{L^2(\theta )}<\infty$.

Proof

We estimate

$$\begin{aligned} \langle \exp (-\alpha \rho _{x_0}),\exp (-\alpha \rho _{x_0})\rangle _{L^2(\theta )}&= \sum _{x\in G}\exp (-2\alpha \rho _{x_0}(x))\theta _x \\&\le \theta _{x_0}+\sum ^\infty _{r=0}\sum _{\rho _{x_0}(x)\in (r,r+1]} \exp (-2\alpha r)\theta _x \\&= \theta _{x_0} + \sum ^\infty _{r=0} (V_\rho (x_0,r+1)-V_\rho (x_0,r))\exp (-2\alpha r) \\&= (\exp (2\alpha )-1)\sum ^\infty _{r=1} V_\rho (x_0,r)\exp (-2\alpha r). \end{aligned}$$

The last expression is finite by the definition of $\mu$ and comparison with a geometric series.

Now, we fix $\alpha > \mu /2$. For $j\in \mathbb{Z }_+$, we define a sequence of ‘tent functions’ by

$$\begin{aligned} h_j(x) := \left\{ \begin{array}{ll} \alpha \rho _{x_0}(x) &{}\text{ if } \rho _{x_0}(x) \le j, \\ 2\alpha j-\alpha \rho _{x_0}(x) &{}\text{ if } \rho _{x_0}(x) > j,\\ \end{array}\right. \end{aligned}$$

and set $f_j := \exp (h_j)$.

We also set

$$\begin{aligned} \varphi (t) := \frac{(1-e^{\alpha t})^2}{1+e^{2\alpha t}} = 1 - \frac{2e^{\alpha t}}{1+e^{2\alpha t}}. \end{aligned}$$

Note that on $[0,\infty )$, $\varphi$ is increasing, and satisfies the inequality

$$\begin{aligned} \varphi (t) \le \frac{\alpha ^2t^2}{2}. \end{aligned}$$

(2.3)

Proposition 2.2

If $x\sim y$, for all $j\in \mathbb{Z }_+$,

$$\begin{aligned} (f_j(y)-f_j(x))^2 \le \varphi (\rho (x,y))(f^2_j(x)+f^2_j(y)). \end{aligned}$$

(2.4)

Proof

Fix $j\in \mathbb{Z }_+$. We prove first that for all $x\sim y$ and all $j\in \mathbb{Z }_+$, we have

$$\begin{aligned} (f_j(y)-f_j(x))^2 \le \varphi (|\rho _{x_0}(y)-\rho _{x_0}(x)|)(f^2_j(x)+f^2_j(y)). \end{aligned}$$

(2.5)

We may assume without loss of generality that $\rho _{x_0}(y)\ge \rho _{x_0}(x)$. It suffices to check two cases.

Case 1 $j\ge \rho _{x_0}(y)\ge \rho _{x_0}(x)$ or $j\le \rho _{x_0}(x)\le \rho _{x_0}(y)$.

In this case, one verifies directly that there is equality in (2.5).

Case 2 $\rho _{x_0}(x)<j<\rho _{x_0}(y)$.

First, the inequality $2j-(\rho _{x_0}(y)+\rho _{x_0}(x)) \le \rho _{x_0}(y)-\rho _{x_0}(x)$ is equivalent to $j \le \rho _{x_0}(y)$, which is true by hypothesis. A direct computation and the fact that $\varphi$ is increasing on $[0,\infty )$ then yields the inequality

$$\begin{aligned} \frac{(f_j(y)-f_j(x))^2}{f^2_j(x)+f^2_j(y)}&= \varphi (2j-(\rho _{x_0}(x)+\rho _{x_0}(y))) \\&\le \varphi (\rho _{x_0}(y)-\rho _{x_0}(x)) \\&= \varphi (|\rho _{x_0}(y)-\rho _{x_0}(x)|). \end{aligned}$$

Finally, combining (2.5) with the inequality $|\rho _{x_0}(x)-\rho _{x_0}(y)|\le \rho (x,y)$ and the fact that $\varphi$ is increasing on $[0,\infty )$ yields that for all $x\sim y$ and all $j\in \mathbb{Z }_+$,

$$\begin{aligned} (f_j(y)-f_j(x))^2&\le \varphi (|\rho _{x_0}(y)-\rho _{x_0}(x)|)(f^2_j(x)+f^2_j(y)) \\&\le \varphi (\rho (x,y)) (f^2_j(x)+f^2_j(y)), \end{aligned}$$

which completes the proof. $\square$

We will now use (2.4) to prove two new bounds:

Corollary 2.3

Suppose there exist constants $m,M>0$ such that $m \le \rho (x,y)\le M$ whenever $x\sim y$. Then for all $x\sim y$ and $j\in \mathbb{Z }_+$,

$$\begin{aligned} (f_j(y)-f_j(x))^2 \le \frac{\rho ^2(x,y)}{m^2}\varphi (M)(f^2_j(x)+f^2_j(y)). \end{aligned}$$

Proof

The inequality $m\le \rho (x,y)$ is equivalent to $\frac{\rho ^2(x,y)}{m^2}\ge 1$, and since $\rho (x,y)\le M$ and $\varphi$ is increasing on $[0,\infty )$, $\varphi (\rho (x,y))\le \varphi (M)$. Combining these with (2.4) gives the result. $\square$

Corollary 2.4

For $x\sim y$ and any $j\in \mathbb{Z }_+$,

$$\begin{aligned} (f_j(y)-f_j(x))^2 \le \rho ^2(x,y)\frac{\alpha ^2}{2}(f^2_j(x)+f^2_j(y)). \end{aligned}$$

Proof

This follows from (2.4) together with (2.3). $\square$

These estimates give us control of $\mathcal{E }(f_j,f_j)$, as follows:

Proposition 2.5

Suppose that $f\in \mathcal{D }(\mathcal{E })$ has the property that for all $x\sim y$, $(f(y)-f(x))^2 \le C\rho ^2(x,y)(f^2(x)+f^2(y))$. Then

$$\begin{aligned} \mathcal{E }(f,f) \le C\Vert f\Vert ^2_{L^2(\theta )}. \end{aligned}$$

Proof

Using adaptedness of $\rho$, we have

$$\begin{aligned} \mathcal{E }(f,f)&:= \frac{1}{2}\sum _{x,y\in G}\pi _{xy}(f(y)-f(x))^2 \\&\le \frac{C}{2}\sum _{x\in G}\sum _{y\sim x}\pi _{xy}\rho ^2(x,y)(f^2(x)+f^2(y)) \\&= C \sum _{x\in G}\left( \frac{1}{\theta _x}\sum _{y\sim x} \pi _{xy}\rho ^2(x,y)\right) f^2(x)\theta _x \\&\le C\Vert f\Vert ^2_{L^2(\theta )}. \end{aligned}$$

$\square$

We should check that $f_j\in \mathcal{D }(\mathcal{E })$ for all $j\in \mathbb{Z }_+$. Fix $j\in \mathbb{Z }_+$. Since $h_j \le 2\alpha j - \alpha \rho _{x_0}$, $0\le f_j \le \exp (2\alpha j-\alpha \rho _{x_0})$, so Lemma 2.1 gives $f_j\in L^2(\theta )$ and the estimate in Proposition 2.5 shows that $\Vert f_j\Vert _{\mathcal{E }}<\infty$. Note that for any $\varepsilon >0$, if $R^\varepsilon _j := j \vee \left( 2j-\frac{\log \varepsilon }{\alpha }\right)$, then on $G{\setminus }B_\rho (x_0,R^\varepsilon _j)$, $0\le f_j \le \varepsilon$. Since $B_\rho (x_0,R^\varepsilon _j)$ is finite (using (1.1) and the assumption that $\mu <\infty$), $f^\varepsilon _j := (f-\varepsilon )_+\in C_c(G)$; note that $\mathcal{E }(f^\varepsilon _j,f^\varepsilon _j) \le \mathcal{E }(f_j,f_j)$. Now, since $f^\varepsilon _j \uparrow f_j$ as $\varepsilon \downarrow 0$, we conclude that $\Vert f^\varepsilon _j-f_j\Vert _{\mathcal{E }} \rightarrow 0$ as $\varepsilon \downarrow 0$, and hence $f_j \in \mathcal{D }(\mathcal{E })$.

Combining Corollary 2.3 and Corollary 2.4 with Proposition 2.5, we have the following:

Proposition 2.6

Suppose there exist constants $m,M>0$ such that $m \le \rho (x,y)\le M$ whenever $x\sim y$. For all $j\in \mathbb{Z }_+$,

$$\begin{aligned} \mathcal{E }(f_j,f_j) \le \frac{1}{m^2}\frac{(1-\exp (\alpha M))^2}{1+\exp (2\alpha M)}\Vert f_j\Vert ^2_{L^2(\theta )}. \end{aligned}$$

Proposition 2.7

For all $j\in \mathbb{Z }_+$,

$$\begin{aligned} \mathcal{E }(f_j,f_j) \le \frac{\alpha ^2}{2}\Vert f_j\Vert ^2_{L^2(\theta )}. \end{aligned}$$

Now, to combine the previous results, we assume that there exists a positive, increasing, continuous function $t \mapsto I_\rho (t)$ such that

$$\begin{aligned} \mathcal{E }(f_j,f_j) \le I_\rho (\alpha )\Vert f_j\Vert ^2_{L^2(\theta )}. \end{aligned}$$

(2.6)

Let $K$ be a finite set, and define $M_K := \max \{\rho (x_0,x):x\in K\}$ and $g_j := f_j(1-\mathbf{1}_K)$. Note that by construction, $B_\rho (x_0,M_K)\supset K$.

Lemma 2.8

For all $j\in \mathbb{Z }_+, \langle g_j,g_j\rangle _{L^2(\theta )} < \infty$, and

$$\begin{aligned} \lim _{j\rightarrow \infty } \langle g_j,g_j\rangle _{L^2(\theta )} = \infty . \end{aligned}$$

Proof

First, for $j\in \mathbb{Z }_+$,

$$\begin{aligned} \langle g_j,g_j\rangle _{L^2(\theta )}&= \sum _{x\in B_\rho (x_0,j)} g^2_j(x)\theta _x+\sum _{x\in G{\setminus }B_\rho (x_0,j)} g^2_j(x)\theta _x \\&\le \exp (2\alpha j)V_\rho (x_0,j)+\exp (4\alpha j)\langle \exp (-\alpha \rho _{x_0}),\exp (-\alpha \rho _{x_0})\rangle _{L^2(\theta )}, \end{aligned}$$

and finiteness follows from Lemma 2.1.

For the second part, if $j>M_K$, then since $g_j \ge 1$ on $B_\rho (x_0,j){\setminus }B_\rho (x_0,M_K)$, it follows that

$$\begin{aligned} \langle g_j,g_j\rangle _{L^2(\theta )} \ge V_\rho (x_0,j)-V_\rho (x_0,M_K), \end{aligned}$$

(2.7)

and (2.7) follows from $V_\rho (x_0,M_K)<\infty$ and $V_\rho (x_0,j)\uparrow \infty$ as $j\rightarrow \infty$ (using (1.1)). $\square$

Next, we estimate the Dirichlet forms $\mathcal{E }(g_j,g_j)$ as follows:

Proposition 2.9

There exists a constant $c(\rho ,\alpha ,K)$ such that for $j\in \mathbb{Z }_+$,

$$\begin{aligned} \mathcal{E }(g_j,g_j) \le c(\rho ,\alpha ,K)+I_\rho (\alpha )\langle g_j,g_j\rangle _{L^2(\theta )}. \end{aligned}$$

Additionally, $g_j\in \mathcal{D }(\mathcal{E })$ for each $j\in \mathbb{Z }_+$.

Proof

Fix $j\in \mathbb{Z }_+$. First, we note that $g_j = f_j$ on $G{\setminus }B_\rho (x_0,M_K)$, and for all $j\in \mathbb{Z }_+$ and $r>0$, since $h_j(x) \le \alpha \rho _{x_0}(x)$ for all $x\in G$, we have $0\le g_j \le f_j \le \exp (\alpha \rho _{x_0})\le \exp (\alpha r)$ on $B_\rho (x_0,r)$.

Consequently, we have the crude estimate

$$\begin{aligned} \mathcal{E }(g_j,g_j)&\le \mathcal{E }(f_j,f_j) + \pi (B_\rho (x_0,M_K+c_\rho ))\sup _{x\in B_\rho (x_0,M_K+c_\rho )} |g^2_j(x)| \nonumber \\&\le \mathcal{E }(f_j,f_j) + \pi (B_\rho (x_0,M_K+c_\rho ))\exp (2\alpha (M_K+c_\rho )). \end{aligned}$$

(2.8)

The reason for using the larger distance $M_K+c_\rho$ is that all edges with at least one end in $B_\rho (x_0,M_K)$ have both ends in $B_\rho (x_0,M_K+c_\rho )$. We also have the simple estimate

$$\begin{aligned} \langle f_j,f_j\rangle _{L^2(\theta )} \le \langle g_j,g_j\rangle _{L^2(\theta )} +\exp (2\alpha M_K)V_\rho (x_0,M_K). \end{aligned}$$

(2.9)

Combining (2.8) with (2.6) and (2.9) gives the desired result, with

$$\begin{aligned} c(\rho ,\alpha ,K) = \exp (2\alpha M_K)(\pi (B_\rho (x_0,M_K+c_\rho ))\exp (2\alpha c_\rho )+I_\rho (\alpha )V_\rho (x_0,M_K)). \end{aligned}$$

The argument that was used to show $f_j\in \mathcal{D }(\mathcal{E })$ also shows that $g_j\in \mathcal{D }(\mathcal{E })$. $\square$

Finally, we can show the following result:

Theorem 2.10

Assume that $\rho$ is such that (2.6) holds. Then

$$\begin{aligned} \lambda ^{ \text{ ess }}_0(\Gamma ,\pi ,\theta ) \le I_\rho (\mu /2). \end{aligned}$$

Proof

We argue by contradiction. Suppose that

$$\begin{aligned} I_\rho (\mu /2) \le \lambda ^{ \text{ ess }}_0(\Gamma ,\pi ,\theta ). \end{aligned}$$

By definition, there exists a finite subset $K$ such that $I_\rho (\mu /2) < \lambda ^{G{\setminus }K}_0(\Gamma ,\pi ,\theta )$. Since $t\mapsto I_\rho (t)$ is increasing and continuous, we can find a constant $\alpha$ such that $\mu <2\alpha$ and such that

$$\begin{aligned} I_\rho (\mu /2) < I_\rho (\alpha ) < \lambda ^{G{\setminus }K}_0(\Gamma ,\pi ,\theta ). \end{aligned}$$

On the other hand, from Proposition 2.9

$$\begin{aligned} \frac{\mathcal{E }(g_j,g_j)}{\langle g_j,g_j\rangle _{L^2(\theta )}} \le \frac{c(\rho ,\alpha ,K)}{\langle g_j,g_j\rangle _{L^2(\theta )}}+I_\rho (\alpha ), \end{aligned}$$

so letting $j\rightarrow \infty$ and using Lemma 2.8 shows that for any $\varepsilon >0$, we can choose $j_0 := j_0(\varepsilon )$ such that

$$\begin{aligned} \frac{\mathcal{E }(g_{j_0},g_{j_0})}{\langle g_{j_0},g_{j_0}\rangle _{L^2(\theta )}} \le I_\rho (\mu /2)+\varepsilon . \end{aligned}$$

In particular, there exists some $j_0\in \mathbb{Z }_+$ such that

$$\begin{aligned} \frac{\mathcal{E }(g_{j_0},g_{j_0})}{\langle g_{j_0},g_{j_0}\rangle _{L^2(\theta )}} < \lambda ^{G{\setminus }K}_0(\Gamma ,\pi ,\theta ). \end{aligned}$$

This is a contradiction, since $g_{j_0}\in \mathcal{D }(\mathcal{E }), g_{j_0}|_K=0$, and

$$\begin{aligned} \lambda ^{G{\setminus }K}_0(\Gamma ,\pi ,\theta ) := \inf \left\{ \frac{\mathcal{E }(f,f)}{\langle f,f\rangle _{L^2(\theta )}}:f\in \mathcal{D }(\mathcal{E }), f\not =0, f|_K=0\right\} . \end{aligned}$$

We conclude that $\lambda ^{ \text{ ess }}_0(\Gamma ,\pi ,\theta ) \le I_\rho (\mu /2)$.

Finally, combining Proposition  with Theorem 2.10 proves Theorem 1.4, and combining Proposition  with Theorem 2.10 proves Theorem 1.3.

Remark

We briefly discuss the relevance of the condition (1.1) to the proof. Assume that (1.1) does not hold. Under the assumption $\mu < \infty$, all metric balls with respect to $\rho$ have finite volume, but do not necessarily contain only finitely many points. Consequently, while one can still use $C_c(G)$ functions to approximate the functions $(g_j)_{j\in \mathbb{Z }_+}$ in the $\Vert \cdot \Vert _{L^2(\theta )}$ norm, one cannot necessarily use $C_c(G)$ functions to approximate the functions $(g_j)_{j\in \mathbb{Z }_+}$ in the $\Vert \cdot \Vert _{\mathcal{E }}$ norm, and hence $g_k$ may fail to belong to $\mathcal{D }(\mathcal{E })$ for some sufficiently large $k\in \mathbb{Z }_+$. In this case, one may then take the domain of the Dirichlet form to be the larger set $\mathcal{D }_\mathrm{max}(\mathcal{E }) := \{f\in C(G):\mathcal{E }_1(f,f)<\infty \}$, and Proposition 2.9 shows that $g_j\in \mathcal{D }_\mathrm{max}(\mathcal{E })$ for all $j\in \mathbb{Z }_+$. However, since $g_k$ cannot be approximated in the $\Vert \cdot \Vert _{\mathcal{E }}$ norm by $C_c(G)$ functions, the Dirichlet form $(\mathcal{E },\mathcal{D }_\mathrm{max}(\mathcal{E }))$ would fail to be regular.

3 Discreteness of the spectrum

If the operator $\mathcal{L }_\theta$ is bounded on $L^2(\theta )$, then the essential spectrum is nonempty. For graphs with the standard weights and the operator $\mathcal{L }_\pi$, Theorem 1 of [10] establishes necessary and sufficient conditions for the essential spectrum to consist of a single point in terms of isoperimetric quantities.

If $\mathcal{L }_\theta$ is unbounded, it is possible for the essential spectrum to be empty (or, equivalently, for the spectrum to be discrete). By Corollary 1.6, a necessary condition for absence of essential spectrum is that for any adapted metric $\rho$, $\mu _\rho (\Gamma ,\pi ,\theta ) = \infty$. Graphs with discrete spectrum (using the operator $\mathcal{L }_{1\!\!1}$) are given in Example 4.2 and  4.3 of Sect. 4. These examples also show that for any $\varepsilon >0$, it is possible to find a graph $(\Gamma ,\pi )$ and a metric $\rho$ adapted to $\mathcal{L }_{1\!\!1}$ such that $\mu _\rho (\Gamma ,\pi ,1\!\!1) = \infty$ and $\mathcal{L }_{1\!\!1}$ has empty essential spectrum, but for every $x_0\in G$,

$$\begin{aligned} \lim _{r\rightarrow \infty } \frac{1}{r^{1+\varepsilon }} \log V_\rho (x_0,r) = 0. \end{aligned}$$

In particular, in these examples the essential spectrum becomes empty precisely as the volume growth changes from exponential to superexponential.

There are connections with stochastic incompleteness of graphs. In [18], the following result is established:

Theorem 3.1

(Keller-Lenz-Wojciechowski, [18]) Let $(\Gamma ,\pi )$ be a weakly spherically symmetric weighted graph equipped with a measure $\theta$. If $(\Gamma ,\pi ,\theta )$ is stochastically incomplete (i.e., if the continuous-time random walk on $(\Gamma ,\pi )$ associated with $\mathcal{L }_\theta$ explodes with positive probability), then $\lambda _0(\Gamma ,\pi ,\theta )>0$ and $\sigma _{ \text{ ess }}(\Gamma ,\pi ,\theta ) = \varnothing$.

In fact, their bound gives a quantitative estimate on the bottom of the spectrum in terms of certain volume growth quantities different than the ones considered in this paper.

Restricting for a moment to the setting of weakly spherically symmetric graphs, there is a large gap between the minimum possible volume growth for stochastic incompleteness and the minimum possible volume growth for discreteness of the spectrum. In previous work of the author (see [7]), the following result was established:

Theorem 3.2

(F., [7]) Let $(\Gamma ,\pi )$ be a weighted graph, let $(\theta _x)_{x\in G}$ be positive vertex weights (we do not assume that (1.1) is satisfied), and let $\rho$ be a metric adapted to $\mathcal{L }_\theta$. If there exists $x_0\in G$ and $r_0>0$ such that

$$\begin{aligned} \int \limits ^\infty _{r_0} \frac{r}{\log V_\rho (x_0,r)}dr = +\infty , \end{aligned}$$

then $(\Gamma ,\pi ,\theta )$ is stochastically incomplete.

Consequently, stochastic completeness is implied by the estimate

$$\begin{aligned} V_\rho (x_0,r) \le Ce^{cr^2\log r} \end{aligned}$$

for some adapted metric $\rho$. In general $r^2$ cannot be replaced with $r^{2+\varepsilon }$ and $\log r$ cannot be replaced with $(\log r)^{1+\varepsilon }$. On the other hand, as is done in Example 4.2 and Example 4.3, for every $\varepsilon >0$ one can find a weighted graph $(\Gamma ,\pi )$ where the essential spectrum is empty and

$$\begin{aligned} V_\rho (x_0,r) \le Ce^{cr^{1+\varepsilon }}. \end{aligned}$$

Consequently, the adapted volume growth thresholds for stochastic incompleteness and absence of essential spectrum are in general very different. The relation between the properties of stochastic incompleteness, discrete spectrum, and positive bottom of spectrum are discussed in [18]. For general weighted graphs, none of these three properties imply any of the others.

4 Examples

Example 4.1

$k-$regular tree, $k\ge 3$.

We let $T_k$ denote the $k-$regular tree, which we equip with the standard weights. In [2, 21], it was proven that

$$\begin{aligned} \lambda _0(T_k,\pi ) = 1-\frac{2\sqrt{k-1}}{k}. \end{aligned}$$

(4.1)

This graph satisfies $\mu _d(T_k,\pi ) = \log (k-1)$. Consequently, Theorem 1.4 yields

$$\begin{aligned} \lambda ^{ \text{ ess }}_0(T_k,\pi ) \le \frac{(1-\exp (\frac{1}{2}\mu _d(T_k,\pi ) ))^2}{1+\exp (\mu _d(T_k,\pi ) )} = 1-\frac{2\sqrt{k-1}}{k}, \end{aligned}$$

so that there is equality in Theorem 1.4. This was observed previously in [9].

Similarly, for $\mathcal{L }_{1\!\!1}$, $k-$regularity implies $k\mathcal{L }_{\pi } = \mathcal{L }_{1\!\!1}$, and hence (4.1) implies

$$\begin{aligned} \lambda _0(T_k,1\!\!1) = k\left( 1-\frac{2\sqrt{k-1}}{k}\right) = k-2\sqrt{k-1}. \end{aligned}$$

We compute the volume growth in the adapted metric $\frac{1}{\sqrt{k}}d$. In this metric, two vertices at distance $r$ are at distance $\sqrt{k}r$ in the graph metric, and consequently $|B_{\frac{1}{\sqrt{k}}d}(x_0,R)| = \sum ^{\sqrt{k}R}_{j=0} (k-1)^j$, from which it follows immediately that

$$\begin{aligned} \mu _{\frac{1}{\sqrt{k}}d}(T_k,1\!\!1) = \sqrt{k}\log (k-1). \end{aligned}$$

Again, Theorem 1.4 yields

$$\begin{aligned} \lambda ^{ \text{ ess }}_0(T_k,1\!\!1) \le k\cdot \frac{(1-\exp (\frac{1}{2\sqrt{k}}\mu _{\frac{1}{\sqrt{k}}d}(T_k, 1\!\!1)))^2}{1+\exp (\frac{1}{\sqrt{k}}\mu _{\frac{1}{\sqrt{k}}d} (T_k,1\!\!1))}= k-2\sqrt{k-1}, \end{aligned}$$

so that Theorem 1.4 may yield sharp results for the operator $\mathcal{L }_{1\!\!1}$ also.

Note also that for large $k$, $\lambda _0(T_k,1\!\!1) \ge \frac{k}{2}$, whereas $\mu _{\frac{1}{\sqrt{k}}d}(T_k,1\!\!1) = \sqrt{k}\log (k-1)$. Consequently, for any $\varepsilon \in (0,2)$ and any $C>0$, if one takes $K=K(\varepsilon ,C)$ large enough, then

$$\begin{aligned} \lambda _0(T_K,1\!\!1) > C\left( \mu _{\frac{1}{\sqrt{k}}d}(T_k,1\!\!1)\right) ^{2-\varepsilon }, \end{aligned}$$

so that Theorem 1.3 is asymptotically sharp.

Example 4.2

Birth-death process:

Set $\Gamma := (\mathbb{Z }_+,E_{nn})$, where $E_{nn}$ denotes the set of nearest-neighbor edges, and set $\pi _\alpha (\{n,n+1\}) := (n+1)^2\log ^\alpha _+(n+1)$ for $\alpha \in (-\infty ,2)$, where $\log _+(x) := \log (x)\vee 1$.

Since $\pi _\alpha (B_d(0,r)) \le Cr^{3+\varepsilon }$ for large $r$, it follows that $\mu _d(\Gamma ,\pi _\alpha ,\pi _\alpha ) = 0$ for any $\alpha \in (-\infty ,2)$, and hence $\lambda ^{ \text{ ess }}_0(\Gamma ,\pi _\alpha ,\pi _\alpha ) = 0$ for all $\alpha \in (-\infty ,2)$.

However, the situation is quite different for the unbounded operator $\mathcal{L }_{1\!\!1}$. In this setting, we use the adapted metric $\frac{1}{\sqrt{2}}d_E$. As $R\rightarrow \infty$, we have

$$\begin{aligned} \frac{1}{\sqrt{2}}d_E(0,R) = \frac{1}{\sqrt{2}}\sum ^R_{j=1} \frac{1}{j\log _+^{\alpha /2}(j)} \sim \frac{\sqrt{2}}{2-\alpha }\log ^{1-\alpha /2}(R), \end{aligned}$$

from which it follows that

$$\begin{aligned} \log |B_{\frac{1}{\sqrt{2}}d_E}(0,r)| \asymp \left( \frac{2-\alpha }{\sqrt{2}}r\right) ^{2/(2-\alpha )}, \end{aligned}$$

and hence

$$\begin{aligned} \mu _{\frac{1}{\sqrt{2}}d_E}(\Gamma ,\pi _\alpha ,1\!\!1) = \left\{ \begin{array}{l@{\quad }l} 0 &{}\text{ if } \alpha <0, \\ \sqrt{2} &{}\text{ if } \alpha =0, \\ \infty &{}\text{ if } 0<\alpha <2. \\ \end{array}\right. \end{aligned}$$

We conclude that $\lambda ^{ \text{ ess }}_0(\Gamma ,\pi _\alpha ,1\!\!1) = 0$ for $\alpha <0$.

The case $\alpha =0$, which corresponds to exponential volume growth, is more subtle. From Theorem 1.3, we have

$$\begin{aligned} \lambda ^{ \text{ ess }}_0(\Gamma ,\pi _0,1\!\!1) \le \frac{1}{8}(\mu _{\frac{1}{\sqrt{2}}d_E} (\Gamma ,\pi _\alpha ,1\!\!1))^2 = \frac{1}{4}. \end{aligned}$$

We will show that $\lambda ^{ \text{ ess }}_0(\Gamma ,\pi _0,1\!\!1) \ge \lambda _0(\Gamma ,\pi _0,1\!\!1)\ge \frac{1}{9}$. To do this, it suffices to show that if $f\in C_c(\mathbb{Z }_+)$,

$$\begin{aligned} \sum _{n\in \mathbb{Z }_+} (n+1)^2(f(n)-f(n+1))^2 \ge \frac{1}{9}\sum _{n\in \mathbb{Z }_+} f^2(n). \end{aligned}$$

(4.2)

For $n\in \mathbb{Z }_+$, we define $g\in C_c(\mathbb{Z }_+)$ by $g(n) := (n+1)(f(n)-f(n+1))$. Since $f(n)\rightarrow 0$ as $n\rightarrow \infty$, we can reconstruct $f$ from $g$ as

$$\begin{aligned} f(n) = \sum _{j\ge n} \frac{1}{j+1}g(j); \end{aligned}$$

consequently, (4.2) is equivalent to

$$\begin{aligned} 9\sum _{n\in \mathbb{Z }_+} g^2(n) \ge \sum _{n\in \mathbb{Z }_+}\left( \sum _{j\ge n} \frac{1}{j+1}g(j)\right) ^2. \end{aligned}$$

It suffices to show that the operator $T:C_c(\mathbb{Z }_+)\rightarrow C_c(\mathbb{Z }_+)$ defined by

$$\begin{aligned} (Tf)(n) := \sum _{j\ge n}\frac{1}{j+1}f(j) \end{aligned}$$

is bounded on $L^2(1\!\!1)$, and satisfies $\Vert T\Vert \le 3$. This is accomplished through an application of Schur’s test. Let $u(n) := (n+1)^{-1/2}$. Then for $n\in \mathbb{Z }_+$, simple estimation using the integral test shows that

$$\begin{aligned} (Tu)(n)&\le 3u(n), \\ (T^*u)(n)&\le 3u(n), \end{aligned}$$

and hence Schur’s test implies that $\Vert T\Vert \le \sqrt{3\cdot 3} = 3$.

A similar calculation shows the absence of essential spectrum for $0<\alpha <2$. In this case, we consider the graphs $(\Gamma _k,\pi _{\alpha ,k})$, where $\Gamma _k$ is the subgraph of $\Gamma$ induced by the subset $\{j\in \mathbb{Z }_+:k\ge j\}$ and $\pi _{\alpha ,k}$ are the restriction of the edge weights $\pi _\alpha$ to $\Gamma _k$. Proceeding as above, we consider the operator

$$\begin{aligned} (T_\alpha f)(n) := \sum _{j\ge n}\frac{1}{(j+1)\log ^{\alpha /2}_+(j+1)}f(j), \end{aligned}$$

on $(\Gamma _k,\pi _{\alpha ,k})$. If $u_\alpha (n) := (n+1)\log ^{\alpha /2}_+(n+1)$, then

$$\begin{aligned} (T_\alpha u)(n)&\le \frac{3}{\log ^{\alpha /2}_+(k+1)}u_\alpha (n), \\ (T^*_\alpha u)(n)&\le \frac{3}{\log ^{\alpha /2}_+(k+1)} u_\alpha (n), \end{aligned}$$

so that on $(\Gamma _k,\pi _{\alpha ,k})$, $\Vert T_\alpha \Vert \le \frac{3}{\log ^{\alpha /2}_+(k+1)}$, and consequently $\lambda _0(\Gamma _k,\pi _{\alpha ,k},1\!\!1) \ge \frac{\log ^{\alpha }_+(k+1)}{9}$.

Since $\lambda ^{ \text{ ess }}_0(\Gamma ,\pi _\alpha ,1\!\!1) = \lim _{k\rightarrow \infty } \lambda _0(\Gamma _k,\pi _{\alpha ,k},1\!\!1) = \infty$, we conclude that the essential spectrum is empty for $0<\alpha <2$.

This example shows that even for graphs on which the VSRW behaves very differently from the CSRW (and, in particular, the operator $\mathcal{L }_{1\!\!1}$ is unbounded), the critical behavior of the bottom of the spectrum for the operator $\mathcal{L }_1\!\!1$ is correctly predicted by computing the volume growth in a metric adapted to $\mathcal{L }_{1\!\!1}$. Moreover, the relevant volume growth estimate for unbounded operators, Theorem 1.3, is analogous to Brooks’ result for manifolds.

In addition to the present results on the spectra of weighted graphs, other phenomena for the operators $\mathcal{L }_\theta$ are correctly predicted by estimating volume growth in adapted metrics. For example, in [7], a volume growth criterion for stochastic completeness (or non-explosiveness) of the VSRW is established. This result also employs adapted metrics, and (as with the present criteria) is analogous to volume growth criteria for manifolds. When applied to this example, the results of [7] show that on $(\Gamma _\alpha ,\pi _\alpha )$ the VSRW is non-explosive if $\alpha \le 1$, and it is not difficult to show directly that the VSRW is explosive if $\alpha >1$.

It seems that the condition of adaptedness is in many respects the correct one for analyzing continuous-time simple random walks on graphs, especially if the corresponding graph Laplacian is unbounded. Adapted metrics are capable of detecting ‘fine’ changes in geometry which are not visible to the graph metric (such as modifying the exponent on the logarithm in this example) but which may nevertheless have a major effect on analytic properties of the Laplacian or the behavior of the associated random walk. These metrics allow one to prove various sharp estimates which are not possible to obtain using only the graph metric (such as heat kernel estimates and volume growth thresholds for various phenomena), and results such as Theorem 1.3 and Theorem 3.2 are directly analogous to existing results for manifolds or for metric measure spaces.

Example 4.3

Spherically symmetric trees with increasing rate of branching:

Let $\Gamma _\alpha$ be a tree rooted at $x_0$, with all vertices at a graph distance of $r$ from $x_0$ having $k(r):= \lfloor 2r^\alpha \rfloor$ neighbors at a graph distance of $r+1$ from $x_0$ for $0\le \alpha <2$. We equip these graphs with the standard weights, and consider the operator $\mathcal{L }_{1\!\!1}$.

Using the adapted metric $d_V$, we have that if $d(x_0,x_R)=R$ and $0<\alpha <2$, then

$$\begin{aligned} d_V(x_0,x_R) \asymp \sum ^R_{j=1} \frac{1}{j^{\alpha /2}} \asymp R^{1-\alpha /2}. \end{aligned}$$

Consequently, if $d_V(x_0,y)\asymp r$, then $d(x_0,y)\asymp r^{2/(2-\alpha )}$. As well, $|B_d(x_0,r)|=\sum ^r_{j=0}\prod ^{j}_{i=0}k(i)$, so that

$$\begin{aligned} \log |B_{d_V}(x_0,r)| \asymp \sum ^{r^{2/(2-\alpha )}}_{j=1} \log j^\alpha \asymp \left\{ \begin{array}{ll} r &{}\text{ if } \alpha =0, \\ r^{2/(2-\alpha )}\log r &{}\text{ if } 0<\alpha <2.\\ \end{array}\right. \end{aligned}$$

Since we have exponential volume growth for $\alpha =0$ in the $d_V$ metric, Corollary 1.6 implies that the essential spectrum of $\mathcal{L }_{1\!\!1}$ on $\Gamma _0$ is nonempty.

For $0<\alpha <2$, since $\Gamma _\alpha$ has positive Cheeger constant at infinity, Theorem 2 of [15] implies that the essential spectrum is empty. In particular, for any $\varepsilon >0$ there exists some $\alpha _0\in (0,2)$ such that on $\Gamma _{\alpha _0}$, $\mu _{d_V}(\Gamma _{\alpha _0},1\!\!1) \le Ce^{cr^{1+\varepsilon }}$ and the essential spectrum of $\mathcal{L }_{1\!\!1}$ on $\Gamma _{\alpha _0}$ is empty.

Consequently, this example and Example 4.2 show that Corollary 1.6 is optimal in certain settings.