text:
# Untitled Document

Asymptotic Enumeration of Spanning Trees

by Russell Lyons

Abstract. We give new general formulas for the asymptotics of the number of spanning trees of a large graph. A special case answers a question of McKay (1983) for regular graphs. The general answer involves a quantity for infinite graphs that we call “tree entropy”, which we show is a logarithm of a normalized determinant of the graph Laplacian for infinite graphs. Tree entropy is also expressed using random walks. We relate tree entropy to the metric entropy of the uniform spanning forest process on quasi-transitive amenable graphs, extending a result of Burton and Pemantle (1993).

2000 Mathematics Subject Classification. Primary 05C05, 60C05. Secondary 60K99, 05C80, 82B20, 28D05, 37A05. Key words and phrases. Asymptotic complexity, graphs, domino tilings, tree entropy, random walks, metric entropy, uniform spanning forests, determinant, Laplacian, trace.Research partially supported by NSF grants DMS-0103897 and DMS-0231224.
§1. Introduction.

Methods of enumeration of spanning trees in a finite graph $`G`$ and relations to various areas of mathematics and physics have been investigated for more than 150 years. The number of spanning trees is often called the complexity of the graph, denoted here by $`\tau (G)`$. The best known formula for the complexity, proved in every basic text on graph theory, is called “the Matrix-Tree Theorem”, which expresses it as a determinant. One is often interested in asymptotics of the complexity of a sequence of finite graphs that approach (in some sense) some infinite graph. Use of the Matrix-Tree Theorem typically involves calculating eigenvalues and their asymptotics.1

1It appears not to have been noticed before that in the case of Euclidean lattice graphs, one can dispense with eigenvalues and go directly to the limit by invoking Szegő’s limit theorem. In one dimension, this theorem appears in, e.g., \[MR88b:42031???\], p. 44. In higher dimensions, it is due to \[MR20:4155???\], but the form in which they present it does not involve determinants. See the last part of the proof of Theorem 5.11 in \[LyonsSteif:dyn???\] to see how to transform their result to give the asymptotics of determinants. In any case, use of our formula is simpler still. This often leads to a formula of the form

$$\underset{n\mathrm{}}{lim}\frac{1}{|𝖵(G_n)|}\mathrm{log}\tau (G_n)=\mathrm{log}f$$

for some function $`f`$ on the unit cube of some Euclidean space, where $`𝖵(G_n)`$ is the vertex set of $`G_n`$. One of the cases that is most well known, due to its connection with domino tilings, is that where the graphs $`G_n`$ approach the usual square lattice, i.e., the nearest-neighbor graph on $`Z^2`$. In this case, one has that

$$\underset{n\mathrm{}}{lim}|𝖵(G_n)|^1\mathrm{log}\tau (G_n)=_0^1_0^1\mathrm{log}(42\mathrm{cos}2\pi x2\mathrm{cos}2\pi y)𝑑x𝑑y=4\mathrm{G}/\pi ,$$

where $`\mathrm{G}:=_{k=0}^{\mathrm{}}(1)^k/(2k+1)^2=0.9160^{}`$ is Catalan’s constant. See, e.g., \[MR94m:60019???\] and \[MR2001b:05111???\] and the references therein for this and several other such examples. We shall reformulate the Matrix-Tree Theorem as an infinite series whose terms have a probabilistic meaning (see Proposition –?– ). In fact, the terms of the series are “local” quantities. This will permit us to find the asymptotic complexity in a very general setting (see Theorem –?– ). Other than assuming a bound on the average degree of the finite graphs of whose complexity we find the asymptotics, our results are essentially the most general possible. In the simplest case, where the finite graphs $`G_n`$ tend to a fixed transitive infinite graph $`G`$, we shall prove that

$$\underset{n\mathrm{}}{lim}|𝖵(G_n)|^1\mathrm{log}\tau (G_n)=𝐡(G):=\mathrm{log}\mathrm{deg}_G(o)\underset{k1}{}p_k(o;G)/k,$$

where $`o`$ is a fixed vertex of $`G`$ and $`p_k(o;G)`$ is the probability that simple random walk started at $`o`$ on $`G`$ is again at $`o`$ after $`k`$ steps. We term $`𝐡(G)`$ the tree entropy2

2Another possible name, “combinatorial entropy”, is already in use with a variety of meanings. of $`G`$. We have chosen this terminology to reflect both its provenance as a limit of entropies per vertex of uniform spanning trees of finite graphs as well as its agreement (up to normalization) with the metric entropy of uniform spanning forests in certain infinite graphs (see Theorem –?– ), as we shall discuss shortly.

Our result allows us to find asymptotics that were not known previously. For a simple example, in case the graphs $`G_n`$ approach the regular tree of degree 4, then

$$\underset{n\mathrm{}}{lim}|𝖵(G_n)|^1\mathrm{log}\tau (G_n)=3\mathrm{log}(3/2);$$

see Example –?– . This answers a question of \[MR85d:05194???\], who had shown such a result only under stronger conditions on the sequence of graphs $`G_n`$, and who had noted (in the case of regular graphs) that, if sufficient, our conditions would be weakest possible.

In the past, it has been observed by direct calculation that one has the same asymptotic complexity both of rectangular portions of $`Z^d`$ as well as of $`d`$-dimensional tori. Our first main result, Theorem –?– , shows that this stability phenomenon is quite general; see Corollary –?– .

Our infinite series representation of the asymptotic complexity has an additional benefit. Namely, even when an integral representation is known, it turns out that for numerical estimation, our infinite series can be much better than the integral3

3In the $`Z^d`$-transitive case, it is not hard to pass directly between our series representation and the standard integral representation.; see, e.g., \[FelkerLyons???\] for examples comparing the two approaches.

In order to state our second main result, we recall the Matrix-Tree Theorem. Given a graph $`G`$, define the following matrices indexed by the vertices of $`G`$: Let $`D_G`$ be the diagonal matrix whose $`(x,x)`$-entry equals the degree of $`x`$; this is the degree matrix. Let $`A_G`$ be the matrix whose $`(x,y)`$-entry equals the number of edges joining $`x`$ and $`y`$; this is the adjacency matrix. Finally, let $`\mathrm{\Delta }_G:=D_GA_G`$, the graph Laplacian matrix. The Matrix-Tree Theorem says that given any finite graph $`G`$, every cofactor of $`\mathrm{\Delta }_G`$ is the same, namely, $`\tau (G)`$ (see, e.g., \[MR2002f:05002???\], Lemma 13.2.3). Another version of the Matrix-Tree Theorem states that when $`G`$ is connected,

$$\tau (G)=|𝖵(G)|^1\mathrm{det}^{}\mathrm{\Delta }_G,$$
$`(1.1)`$
where $`\mathrm{det}^{}A`$ denotes the product of the non-zero eigenvalues of a matrix $`A`$ (see, e.g., \[MR2002f:05002???\], Lemma 13.2.4). Thus, the asymptotic complexity of a sequence of graphs is a limit of the logarithm of the determinant of the graph Laplacians, appropriately normalized. Our second main aim is to give meaning to and to prove the formula

$$𝐡(G)=\mathrm{log}\mathrm{Det}\mathrm{\Delta }_G$$

directly in terms of a normalized determinant of the graph Laplacian for infinite graphs. We shall also use this formula to prove inequalities for tree entropy and to calculate easily and quickly the classical tree entropy for Euclidean lattices. Indeed, this result, Theorem –?– , provides a quick way to derive virtually all the prior asymptotics of this type in the literature, while Theorem –?– gives the rest (and more).

We have alluded to the fact that tree entropy also arises as the entropy per vertex of a measure that is the weak limit of the uniform measures on spanning trees of finite graphs. To state this precisely, we must first recall the work of \[MR92g:60014???\]. He proved a conjecture of the present author, namely, that if an infinite connected graph $`G`$ is exhausted by a sequence of finite connected subgraphs $`G_n`$, then the weak limit of the uniform spanning tree measures on $`G_n`$ exists. However, it may happen that the limit measure is not supported on trees, but on forests. This limit measure is now called the free uniform spanning forest on $`G`$, denoted $`\mathrm{𝖥𝖲𝖥}`$, or $`\mathrm{𝖥𝖲𝖥}_G`$ when we want to indicate the graph $`G`$. If $`G`$ is itself a tree, then this measure is trivial, namely, it is concentrated on $`\{G\}`$. Therefore, \[MR99i:05186???\] introduced another limit that had been considered on $`Z^d`$ more implicitly by \[MR92g:60014???\] and explicitly by \[MR97b:60170???\], namely, the weak limit of the uniform spanning tree measures on $`G_n^{}`$, where $`G_n^{}`$ is the graph $`G_n`$ with its boundary identified to a single vertex. As \[MR92g:60014???\] showed, this limit also always exists on any graph and is now called the wired uniform spanning forest, denoted $`\mathrm{𝖶𝖲𝖥}`$ or $`\mathrm{𝖶𝖲𝖥}_G`$. It is clear that both $`\mathrm{𝖥𝖲𝖥}`$ and $`\mathrm{𝖶𝖲𝖥}`$ are concentrated on the set of spanning forests4

4By a “spanning forest”, we mean a subgraph without cycles that contains every vertex. of $`G`$ that are essential, meaning that all their trees are infinite. Furthermore, since the limits exist regardless of the exhaustion chosen, both $`\mathrm{𝖥𝖲𝖥}_G`$ and $`\mathrm{𝖶𝖲𝖥}_G`$ are invariant under any automorphisms that $`G`$ may have. As shown by \[MR97b:60170???\], $`\mathrm{𝖥𝖲𝖥}_G=\mathrm{𝖶𝖲𝖥}_G`$ on every amenable transitive graph $`G`$ such as $`Z^d`$. In fact, the proof of this result given by \[MR1825141???\], hereinafter referred to as BLPS (2001), is easily modified to show that the same holds for every quasi-transitive amenable graph, using the notion of natural frequency distribution recalled below in Section ?? . Both $`\mathrm{𝖥𝖲𝖥}`$ and $`\mathrm{𝖶𝖲𝖥}`$ are important in their own right; see \[MR1630412???\] for a survey and BLPS (2001) for a comprehensive treatment.

Suppose now that $`\mathrm{\Gamma }`$ is an amenable group that acts quasi-transitively on a graph $`G`$. Since $`\mathrm{𝖥𝖲𝖥}_G`$ is defined as a limit of uniform measures, it is natural to expect that it has maximum (metric) entropy in an appropriate class of $`\mathrm{\Gamma }`$-invariant measures. Since the set of essential spanning forests is closed, one generally considers the class of $`\mathrm{\Gamma }`$-invariant measures on this set. Furthermore, one might expect that the entropy of $`\mathrm{𝖥𝖲𝖥}_G`$ is related in a simple way to the exponential growth rate of the complexity of the finite subgraphs $`G_n`$ exhausting $`G`$. Finally, one might wonder whether $`\mathrm{𝖥𝖲𝖥}_G`$ is unique as a measure of maximal entropy on the essential spanning forests.

The case of $`\mathrm{\Gamma }=Z^d`$ was considered by \[MR94m:60019???\]. Their Theorem 6.1 gave a positive answer to all three questions implicit in the preceding paragraph. However, it turns out that one of the claims, the uniqueness of the measure of maximal entropy, received an incorrect proof. The correct proofs of the other claims relied to some extent on the natural tiling of $`Z^d`$ by large boxes, which is not available in general amenable quasi-transitive graphs. The third aim of this paper is to extend these two other claims to amenable quasi-transitive graphs, that is, to prove that the formula for entropy is correct and to prove that this entropy is maximal (see Theorem –?– ). We have not been able to prove uniqueness of the measure of maximal entropy. Therefore, the deduction by \[MR94m:60019???\] of the uniqueness of the measure of maximal entropy for domino tilings in $`Z^2`$ (their Theorem 7.2) remains incomplete. However, a new and more general proof for the uniqueness of the measure of maximal entropy for domino tilings has been found by \[Sheff:thesis???\]. The arguments in \[MR94m:60019???\] can then be used to deduce the uniqueness of the measure of maximal entropy for spanning trees in $`Z^2`$ (but not in higher dimensions, which remains open).

We give general background and definitions related to graphs, groups, and entropy in Section ?? . In Section ?? , we give our reformulation of the Matrix-Tree Theorem and its asymptotics, together with several examples. We give the formula for tree entropy as a determinant on infinite graphs in Section ?? , with applications. We prove the assertions on metric entropy in Section ?? .

Note added in proof: It has just been discovered that there is an error in \[AL:uni???\]. Namely, there is a gap in the proof that all unimodular random rooted graphs are random weak limits of finite graphs. This makes the proofs of certain results here incomplete. Remark –?– , Proposition –?– , and Theorem –?– will be complete when restricted to random weak limits of finite graphs, rather than claimed for all unimodular random rooted graphs.

§2. Background.

We denote a (multi-)graph $`G`$ with vertex set $`𝖵`$ and edge set $`𝖤`$ by $`G=(𝖵,𝖤)`$. When there is more than one graph under discussion, we write $`𝖵(G)`$ or $`𝖤(G)`$ to avoid ambiguity. We denote the degree of a vertex $`x`$ in a graph $`G`$ by $`\mathrm{deg}_G(x)`$. Unless stated otherwise, we assume all degrees finite. Simple random walk on $`G`$ is the Markov chain whose state space is $`𝖵`$ and whose transition probability from $`x`$ to $`y`$ equals the number of edges joining $`x`$ to $`y`$ divided by $`\mathrm{deg}_G(x)`$.

An infinite path in a tree that starts at any vertex and does not backtrack is called a ray. Two rays are equivalent if they have infinitely many vertices in common. An equivalence class of rays is called an end. More generally, an end of an infinite graph $`G`$ is an equivalence class of infinite simple paths in $`G`$, where two paths are equivalent if for every finite subgraph $`KG`$, there is a connected component of $`GK`$ that intersects both paths.

Let $`G`$ be a graph. For a subgraph $`H`$, let its (internal) vertex boundary $`_𝖵H`$ be the set of vertices of $`H`$ that are adjacent to some vertex not in $`H`$. We say that $`G`$ is amenable if there is an exhaustion $`H_1H_2\mathrm{}H_n\mathrm{}`$ with $`_nH_n=G`$ and

$$\underset{n\mathrm{}}{lim}\frac{|_𝖵H_n|}{|𝖵(H_n)|}=0.$$

Such an exhaustion (or the sequence of its vertex sets) is called a Følner sequence. A finitely generated group is amenable if its Cayley graph is amenable. For example, every finitely generated abelian group is amenable. For more on amenability of graphs and groups, see \[MR99m:60149???\], hereinafter referred to as BLPS (1999).

A homomorphism $`\phi :G_1G_2`$ from one graph $`G_1=(𝖵_1,𝖤_1)`$ to another $`G_2=(𝖵_2,𝖤_2)`$ is a pair of maps $`\phi _𝖵:𝖵_1𝖵_2`$ and $`\phi _𝖤:𝖤_1𝖤_2`$ such that $`\phi _𝖵`$ maps the endpoints of $`e`$ to the endpoints of $`\phi _𝖤(e)`$ for every edge $`e𝖤_1`$. When both maps $`\phi _𝖵:𝖵_1𝖵_2`$ and $`\phi _𝖤:𝖤_1𝖤_2`$ are bijections, then $`\phi `$ is called an isomorphism. When $`G_1=G_2`$, an isomorphism is called an automorphism. The group of all automorphisms of $`G`$ will be denoted by $`\mathrm{Aut}(G)`$. The action of a group $`\mathrm{\Gamma }`$ on a graph $`G`$ by automorphisms is said to be transitive if there is only one $`\mathrm{\Gamma }`$-orbit in $`𝖵(G)`$ and to be quasi-transitive if there are only finitely many orbits in $`𝖵(G)`$. A graph $`G`$ is transitive or quasi-transitive according as whether the corresponding action of $`\mathrm{Aut}(G)`$ is. For example, every Cayley graph is transitive.

The action of a group on a set is called free if the stabilizer of each element of the set is just the identity element of the group. For example, every group acts on itself freely by multiplication.

A locally compact group is called unimodular if its left Haar measure is also right invariant. In particular, every discrete countable group is unimodular. We call a graph $`G`$ unimodular if $`\mathrm{Aut}(G)`$ is unimodular, where $`\mathrm{Aut}(G)`$ is given the weak topology generated by its action on $`G`$. Every Cayley graph and, as \[MR91m:43002???\] and \[MR93h:60113???\] proved, every quasi-transitive amenable graph is unimodular. See BLPS (1999) for more details on unimodular graphs.

We now recall some definitions pertaining to entropy. For simplicity, we restrict our discussion to groups acting on graphs, which is enough for our purposes. Suppose first that $`\mu `$ is a probability measure on a finite or countable set, $`X`$. The entropy of $`\mu `$ is

$$𝐇(\mu ):=\underset{xX}{}\mu (x)\mathrm{log}\mu (x).$$

For example, suppose that $`\mu `$ is a probability measure on the Borel sets of $`2^𝖤:=\{0,1\}^𝖤`$ in the product topology. As usual, we identify an element of $`2^𝖤`$ with the subset (or “configuration”) of edges where the value 1 is taken. If $`H`$ is a finite subgraph of $`G`$, write $`\mu \mathrm{}H`$ for the restriction of $`\mu `$ to the $`\sigma `$-field generated by the restrictions to $`𝖤(H)`$. That is, $`\mu \mathrm{}H`$ is defined on the finite set $`2^{𝖤(H)}`$ and has an entropy as above.

We shall twice use the following well-known lemma (see, e.g., Lemma 6.2 of \[MR94m:60019???\] and p. 11 of \[MR2002j:05132???\] for the bound on the binomial coefficient sum).

Lemma 2.1. Let $`Y`$ be a finite set and $`m`$ be a positive integer. Write $`\alpha :=m/|Y|`$. Suppose that $`\mu `$ is a probability measure on $`2^Y\times 2^Y`$ that is supported on the set of pairs $`(\omega _1,\omega _2)`$ with $`|\omega _1\omega _2|m`$. Let $`\mu _1`$ and $`\mu _2`$ be the coordinate marginals of $`\mu `$. Then

$$|𝐇(\mu _1)𝐇(\mu _2)|\mathrm{log}\underset{k=0}{\overset{m}{}}\left(\genfrac{}{}{0pt}{}{|Y|}{k}\right)|Y|\left(\alpha \mathrm{log}\alpha (1\alpha )\mathrm{log}(1\alpha )\right).$$

Suppose that the finite group $`\mathrm{\Gamma }`$ acts on $`X`$ and preserves the measure $`\mu `$. Then the entropy of the pair $`(\mu ,\mathrm{\Gamma })`$ is

$$𝐇(\mu ,\mathrm{\Gamma }):=|\mathrm{\Gamma }|^1𝐇(\mu ).$$

Finally, suppose that $`\mathrm{\Gamma }`$ is a countable amenable finitely generated subgroup of $`\mathrm{Aut}(G)`$. Let $`\mu `$ be a probability measure on $`2^𝖤`$ that is preserved by $`\mathrm{\Gamma }`$. Let $`\mathrm{\Gamma }_n`$ be a Følner sequence in $`\mathrm{\Gamma }`$ and $`H`$ be a finite subgraph of $`G`$ such that $`\mathrm{\Gamma }H=G`$, provided such an $`H`$ exists. Then the (metric) entropy of the pair $`(\mu ,\mathrm{\Gamma })`$, also called the $`\mathrm{\Gamma }`$-entropy of $`\mu `$, is

$$𝐇(\mu ,\mathrm{\Gamma }):=\underset{n\mathrm{}}{lim}|\mathrm{\Gamma }_n|^1𝐇\left(\mu \mathrm{}(\mathrm{\Gamma }_nH)\right).$$

This does not depend on the choice of $`H`$. See \[MR88j:28014???\] for more details on entropy.

§3. Asymptotic Complexity.

Recall that $`\tau (G)`$ denotes the complexity of the graph $`G`$, i.e., the number of spanning trees of $`G`$. Let $`p_k(x;G)`$ denote the probability that simple random walk on $`G`$ started at $`x`$ is back at $`x`$ after $`k`$ steps.

We begin with a formula for the complexity of finite graphs.

Proposition 3.1. Suppose that $`G`$ is a finite connected graph. Then

$$\mathrm{log}\tau (G)=\mathrm{log}(2|𝖤(G)|)+\underset{x𝖵(G)}{}\mathrm{log}\mathrm{deg}_G(x)\underset{k1}{}\frac{1}{k}\left(\underset{x𝖵(G)}{}p_k(x;G)1\right).$$

Proof. Let $`P`$ be the transition matrix for simple random walk on $`G`$ and $`I`$ be the identity matrix of the same size. As shown by \[MR52:2933???\], we may rewrite (1.1) as

$$\tau (G)=\frac{\underset{x𝖵(G)}{}\mathrm{deg}_G(x)}{_{x𝖵(G)}\mathrm{deg}_G(x)}\mathrm{det}^{}(IP)$$

\[the proof follows from looking at the coefficient of $`t`$ in $`det\left(IPtI\right)=(detD_G)^1det\left(\mathrm{\Delta }_GtD_G\right)`$ and using the Matrix-Tree Theorem in its original form with cofactors\]. Since the sum of the degrees of a graph equals twice the number of its edges, we obtain

$$\mathrm{log}\tau (G)=\mathrm{log}(2|𝖤(G)|)+\underset{x𝖵(G)}{}\mathrm{log}\mathrm{deg}_G(x)+\mathrm{log}\mathrm{det}^{}(IP).$$
$`(3.1)`$
Let $`\mathrm{\Lambda }`$ be the multiset of eigenvalues of $`P`$ other than 1 (with multiplicities). Since $`\mathrm{\Lambda }[1,1)`$, we may rewrite the last term of (3.1) as

$$\begin{array}{ccc}\hfill \mathrm{log}\mathrm{det}^{}(IP)& =\underset{\lambda \mathrm{\Lambda }}{}\mathrm{log}(1\lambda )=\underset{\lambda \mathrm{\Lambda }}{}\underset{k1}{}\lambda ^k/k\hfill & \\ & =\underset{k1}{}\underset{\lambda \mathrm{\Lambda }}{}\lambda ^k/k=\underset{k1}{}\frac{1}{k}(\mathrm{tr}P^k1),\hfill & \end{array}$$

where in the last step, we have used the fact that the eigenvalue $`1`$ of $`P`$ has multiplicity 1 since $`G`$ is connected. Since $`\mathrm{tr}P^k=_{x𝖵(G)}p_k(x;G)`$, the desired formula now follows from this and (3.1).

Remark 3.2. There is an extension of Proposition 3.1 to any irreducible Markov chain with transition matrix $`P`$. In this case, a spanning tree of the associated directed graph, with all edges leading towards a single vertex, is often called a “spanning arborescence”. Let $`\tau ^{}(P)`$ be the sum over all spanning trees (with all possible roots) of the product of $`P(e)`$ over all $`e`$ in the tree. The analogue of Proposition 3.1 states that

$$\mathrm{log}\tau ^{}(P)=\underset{k1}{}\frac{1}{k}\left(\underset{x𝖵(G)}{}p_k(x;G)1\right).$$

This is reminiscent of a formula that appears in \[MR2002k:37011???\]. In fact, combining their formula with ours, one gets an expression for the derivative at $`1`$ of the reciprocal of the so-called stochastic zeta function of $`P`$.

A rooted graph $`(G,x)`$ is a graph $`G`$ with a distinguished vertex $`x`$ of $`G`$, called the root. A rooted isomorphism of rooted graphs is an isomorphism of the underlying graphs that takes the root of one to the root of the other. We shall use the following notion of random weak convergence introduced by \[MR1873300???\] and studied further by \[MR2023650???\] and \[AL:uni???\]. Given a positive integer $`R`$, a finite rooted graph $`H`$, and a probability distribution $`\rho `$ on rooted graphs, let $`p(R,H,\rho )`$ denote the probability that $`H`$ is rooted isomorphic to the ball of radius $`R`$ about the root of a graph chosen with distribution $`\rho `$. If $`(G,\rho )`$ is a graph with probability distribution $`\rho `$ on its vertices, then $`\rho `$ induces naturally a distribution on rooted graphs, which we also denote by $`\rho `$; namely, the probability of $`(G,x)`$ is $`\rho (x)`$. For a finite graph $`G`$, let $`U(G)`$ denote the distribution of rooted graphs obtained by choosing a uniform random vertex of $`G`$ as root of $`G`$. Suppose that $`G_n`$ is a sequence of finite graphs and that $`\rho `$ is a probability measure on rooted infinite graphs; in most practical cases, $`\rho `$ will be induced by a probability distribution on the vertices of a fixed infinite graph. We say the random weak limit of $`G_n`$ is $`\rho `$ if for any positive integer $`R`$ and any finite graph $`H`$, we have $`lim_n\mathrm{}p(R,H,U(G_n))=p(R,H,\rho )`$. More generally, if $`G_n`$ are random finite graphs, then we say the random weak limit of $`G_n`$ is $`\rho `$ if for any positive integer $`R`$, any finite graph $`H`$, and any $`ϵ>0`$, we have $`lim_n\mathrm{}𝐏\left[\left|p(R,H,U(G_n))p(R,H,\rho )\right|>ϵ\right]=0`$. Note that only the component of the root matters for convergence to $`\rho `$. Thus, we may and shall assume that $`\rho `$ is concentrated on connected graphs. If $`\rho `$ is induced by a distribution on the vertices of a fixed transitive graph $`G`$, then the random weak limit depends only on $`G`$ and not on the root. In this case, we say that the random weak limit of $`G_n`$ is $`G`$.

Given $`R>0`$ and a finite graph $`G`$, let $`\nu _R(G)`$ be the distribution of the number of edges in the ball of radius $`R`$ about a random vertex of $`G`$. Call a collection of finite graphs $`G`$ tight if for each $`R`$, the collection of corresponding distributions $`\nu _R(G)`$ is tight. Note that any tight collection of finite graphs has a subsequence that possesses a random weak limit.

Define the expected degree of a probability measure $`\rho `$ on rooted graphs to be

$$\overline{\mathrm{deg}}(\rho ):=\mathrm{deg}_G(x)𝑑\rho (G,x).$$

When the following integral converges, define the tree entropy of $`\rho `$ to be

$$𝐡(\rho ):=\left(\mathrm{log}\mathrm{deg}_G(x)\underset{k1}{}\frac{1}{k}p_k(x;G)\right)𝑑\rho (G,x).$$

Our terminology is justified by Theorems –?– and –?– below. The integral converges, for example, when $`\rho `$ has finite expected degree, i.e., $`\overline{\mathrm{deg}}(\rho )<\mathrm{}`$, by virtue of the inequality between the arithmetic and geometric means; see also Corollary –?– and Proposition –?– below. If $`\rho `$ is induced by a fixed transitive graph, $`G`$, of degree $`d`$, we write

$$𝐡(G):=𝐡(\rho )=\mathrm{log}d\underset{k1}{}\frac{1}{k}p_k(o;G)$$

for the tree entropy of $`G`$, where $`o`$ is any vertex of $`G`$.

Our main theorem in this section is the following. It also suggests thinking of $`𝐡(\rho )`$ as a normalized logarithm of the determinant of the Laplacian. See Theorem –?– for a more direct reason for thinking thus.

Theorem 3.3. If $`G_n`$ are finite connected graphs with bounded average degree whose random weak limit is a probability measure $`\rho `$ on infinite rooted graphs, then

$$\underset{n\mathrm{}}{lim}\frac{1}{|𝖵(G_n)|}\mathrm{log}\tau (G_n)=𝐡(\rho ).$$

The same limit holds in probability when $`G_n`$ are random with bounded expected average degree.

Remark 3.4. If there is a homomorphism that is not an isomorphism from one transitive graph $`G_1`$ onto another $`G_2`$ of the same degree, then it is clear that $`p_k(o;G_1)p_k(o;G_2)`$ for every $`k`$, with strict inequality for some $`k`$. Therefore, $`𝐡(G_1)>𝐡(G_2)`$. In particular, among all transitive graphs $`G`$ of degree $`d`$, the maximum of $`𝐡(G)`$ is achieved uniquely for $`G`$ the regular tree of degree $`d`$. This maximum value is calculated explicitly in Example –?– . The uniqueness of the maximum, Theorem 3.3, and tightness imply that if a sequence of finite regular graphs $`G_n`$ of degree $`d`$ does not tend to the $`d`$-regular tree, $`T`$, then $`lim\; inf_n|𝖵(G_n)|^1\mathrm{log}\tau (G_n)<𝐡(T)`$; this is Theorem 4.5 of \[MR85d:05194???\].

The only difficulty in deducing Theorem 3.3 from Proposition 3.1 is the interchange of limit and summation. In order to accomplish this, we shall use the following lemmas.

Lemma 3.5. Let $`P`$ be the transition matrix of a Markov chain. For $`\alpha [0,1]`$, define the transition matrix $`Q:=\alpha I+(1\alpha )P`$. For a state $`x`$, let $`p_k(x)`$ and $`q_k(x)`$ denote the return probabilities to $`x`$ after $`k`$ steps when the Markov chains start at $`x`$, where the transition matrices are $`P`$ and $`Q`$, respectively. We have

$$\underset{k}{}q_k(x)/k=\mathrm{log}(1\alpha )+\underset{k}{}p_k(x)/k.$$
$`(3.2)`$
Proof. Write $`(,)`$ for the ordinary inner product in $`\mathrm{}^2(V)`$, where $`V`$ is the state space. Given $`xV`$ and $`z(0,1)`$, we have

$$\begin{array}{ccc}\hfill \underset{k}{}q_k(x)z^k/k& =([\mathrm{log}(IzQ)]\mathrm{𝟏}_{\{x\}},\mathrm{𝟏}_{\{x\}})\hfill & \\ & =(\left[\mathrm{log}\left((1z\alpha )Iz(1\alpha )P\right)\right]\mathrm{𝟏}_{\{x\}},\mathrm{𝟏}_{\{x\}})\hfill & \\ & =(\left[\mathrm{log}\left(I\frac{z(1\alpha )}{1z\alpha }P\right)\right]\mathrm{𝟏}_{\{x\}},\mathrm{𝟏}_{\{x\}})\mathrm{log}(1z\alpha )(\mathrm{𝟏}_{\{x\}},\mathrm{𝟏}_{\{x\}})\hfill & \\ & =\mathrm{log}(1z\alpha )+\underset{k}{}p_k(x)\left(\frac{z(1\alpha )}{1z\alpha }\right)^k\frac{1}{k}.\hfill & \end{array}$$

Letting $`z1`$, we obtain the desired equation.

Next we give a universal bound for the rate of convergence of $`p_k(x;G)`$ to the stationary probability $`\mathrm{deg}_G(x)/2|𝖤(G)|`$ for finite graphs and to 0 for infinite graphs. In the case of infinite graphs, such a result is first due to \[MR88i:35066???\]. Our argument is a modification of that of \[TC:survey???\] and seems not to be written anywhere for the case of finite graphs, although there is some overlap with the treatment of the special case in Example 2.3.1 of \[MR99b:60119???\]. For sharper bounds that depend on more information about the graph, see, e.g., Theorems 3.3.11 and 2.3.1 of \[MR99b:60119???\] for the finite case and \[MR2002b:58029???\] for the infinite case. See also \[MP:evolve???\].

Lemma 3.6. Suppose that $`Q`$ is a transition matrix of a Markov chain that is reversible with respect to a positive measure $`\pi `$. If $`\pi `$ is finite, then we assume that $`\pi `$ is normalized to be a probability measure. Assume that $`c:=inf\left\{\pi (x)Q(x,y);xy\text{ and }Q(x,y)>0\right\}>0`$ and that $`a:=inf_xQ(x,x)>0`$. For all states $`x`$ and all $`k0`$, we have

$$\left|\frac{Q^k(x,x)}{\pi (x)}1\right|\mathrm{min}\{\frac{1}{ac\sqrt{k+1}},\frac{1}{2a^2c^2(k+1)}\}$$
$`(3.3)`$
if $`\pi `$ is finite and

$$\frac{Q^k(x,x)}{\pi (x)}\frac{1}{ac\sqrt{k+1}}$$
$`(3.4)`$
if $`\pi `$ is infinite.

Proof. Write $`V`$ for the state space and $`E`$ for the set of pairs $`(x,y)`$ where $`Q(x,y)>0`$ and $`xy`$. Write

$$c_2(x,y):=\pi (x)Q^2(x,y)$$

and note that for $`(x,y)E`$, we have

$$c_2(x,y)\pi (x)[Q(x,x)Q(x,y)+Q(x,y)Q(y,y)]2ac.$$

Define the inner product $`(f_1,f_2)_\pi :=_xf_1(x)f_2(x)\pi (x)`$ on $`\mathrm{}^2(V,\pi )`$.

The case where $`\pi `$ is infinite is simpler, so we treat that first. Let $`f`$ be a function on $`V`$ with finite support. Let $`x_0`$ be a vertex where $`|f|`$ achieves its maximum. Then

$$f_{\mathrm{}}=|f(x_0)|\frac{1}{2}\underset{(x,y)E}{}|f(x)f(y)|\frac{1}{2}\underset{x,yV}{}c_2(x,y)|f(x)f(y)|/(2ac),$$
$`(3.5)`$
where the factor $`1/2`$ arises from counting each pair $`(x,y)`$ in each order. Applying (3.5) to the function $`f^2`$, we obtain

$$\begin{array}{ccc}\hfill (2ac)^2f_{\mathrm{}}^4& \left(\frac{1}{2}\underset{x,yV}{}c_2(x,y)\left|f(x)f(y)\right|\left|f(x)+f(y)\right|\right)^2\hfill & \\ & \left(\frac{1}{2}\underset{x,yV}{}c_2(x,y)[f(x)f(y)]^2\right)\left(\frac{1}{2}\underset{x,yV}{}c_2(x,y)[f(x)+f(y)]^2\right)\hfill & \\ & =((IQ^2)f,f)_\pi ((I+Q^2)f,f)_\pi \hfill & \end{array}$$

by the Cauchy-Schwarz inequality and some straightforward algebra. Therefore, if $`(f,f)_\pi 1`$, we have $`2(ac)^2f_{\mathrm{}}^4((IQ^2)f,f)_\pi `$. Apply this inequality to the functions $`Q^lf`$ for $`l=0,\mathrm{},k`$ and sum the resulting inequalities to obtain

$$\begin{array}{ccc}\hfill (k+1)2(ac)^2Q^kf_{\mathrm{}}^4& 2(ac)^2\underset{l=0}{\overset{k}{}}Q^lf_{\mathrm{}}^4\underset{l=0}{\overset{k}{}}((IQ^2)Q^lf,Q^lf)_\pi \hfill & \\ & =\underset{l=0}{\overset{k}{}}((IQ^2)Q^{2l}f,f)_\pi =((IQ^{2k+2})f,f)_\pi 1\hfill & \end{array}$$

for $`(f,f)_\pi 1`$. This shows that the norm of $`Q^k:\mathrm{}^2(V,\pi )\mathrm{}^{\mathrm{}}(V)`$ is bounded by

$$\beta _k:=[(2k+2)(ac)^2]^{1/4}.$$

The same bound holds for $`Q^k:\mathrm{}^1(V,\pi )\mathrm{}^2(V,\pi )`$ by duality. Therefore, considering $`Q^{2k}=Q^kQ^k`$, we find that the norm of $`Q^{2k}:\mathrm{}^1(V,\pi )\mathrm{}^{\mathrm{}}(V)`$ is at most $`\beta _k^2`$, while the norm of $`Q^{2k+1}:\mathrm{}^1(V,\pi )\mathrm{}^{\mathrm{}}`$ is at most $`\beta _k\beta _{k+1}`$. Applying these inequalities to $`f:=\mathrm{𝟏}_{\{x\}}/\pi (x)`$ gives (3.4).

The case of finite $`\pi `$ is quite similar. The essential difference is that we work with $`\mathrm{}_0^2(V,\pi )`$, the orthogonal complement of the constants in $`\mathrm{}^2(V,\pi )`$. Note that $`\mathrm{𝟏}`$ is an eigenfunction of $`Q`$ and that $`\mathrm{}_0^2(V,\pi )`$ is invariant under $`Q`$. We may still conclude (3.5) for all $`f`$ that have at least one nonnegative value and at least one nonpositive value, such as all $`f\mathrm{}_0^2(V,\pi )`$.

Take $`f\mathrm{}_0^2(V,\pi )`$. Notice that $`_{x,yV}c_2(x,y)=_{xV}\pi (x)=1`$. Thus, we have from (3.5) that

$$(2ac)^2f_{\mathrm{}}^2\frac{1}{2}\underset{x,yV}{}c_2(x,y)[f(x)f(y)]^2=((IQ^2)f,f)_\pi .$$
$`(3.6)`$
Alternatively, we may apply (3.5) to the function $`\mathrm{sgn}(f)f^2`$. Using the trivial inequality

$$|\mathrm{sgn}(s)s^2\mathrm{sgn}(t)t^2||st|\left(|s|+|t|\right),$$

valid for any real numbers $`s`$ and $`t`$, we obtain that

$$\begin{array}{ccc}\hfill (2ac)^2f_{\mathrm{}}^4& \left(\frac{1}{2}\underset{x,yV}{}c_2(x,y)\left|f(x)f(y)\right|\left(|f(x)|+|f(y)|\right)\right)^2\hfill & \\ & ((IQ^2)f,f)_\pi ((I+Q^2)|f|,|f|)_\pi .\hfill & \end{array}$$

Putting both these estimates together, we get

$$2(ac)^2\mathrm{max}\{2f_{\mathrm{}}^2,f_{\mathrm{}}^4\}((IQ^2)f,f)_\pi $$

for $`(f,f)_\pi =1`$. As before, this implies that

$$(k+1)2(ac)^2\mathrm{max}\{2Q^kf_{\mathrm{}}^2,Q^kf_{\mathrm{}}^4\}1,$$

which shows that the norm of $`Q^k:\mathrm{}_0^2(V,\pi )\mathrm{}^{\mathrm{}}(V)`$ is bounded by

$$\alpha _k:=\mathrm{min}\{[(2ac)^2(k+1)]^{1/2},[(2k+2)(ac)^2]^{1/4}\}.$$

Let $`T:\mathrm{}^2(V,\pi )\mathrm{}_0^2(V,\pi )`$ be the orthogonal projection $`Tf:=f(f,\mathbf{\hspace{0.17em}1})_\pi \mathrm{𝟏}`$. Given what we have shown, we see that the norm of $`Q^kT:\mathrm{}^2(V,\pi )\mathrm{}^{\mathrm{}}(V)`$ is bounded by $`\alpha _k`$. By duality, the same bound holds for $`TQ^k:\mathrm{}^1(V,\pi )\mathrm{}^2(V,\pi )`$. As before, we deduce that the norm of $`Q^kTQ^k:\mathrm{}^1(V,\pi )\mathrm{}^{\mathrm{}}(V)`$ is at most $`\alpha _k^2`$ and the norm of $`Q^kTQ^{k+1}:\mathrm{}^1(V,\pi )\mathrm{}^{\mathrm{}}`$ is at most $`\alpha _k\alpha _{k+1}`$. Applying these inequalities to $`f:=\mathrm{𝟏}_{\{x\}}/\pi (x)`$ gives (3.3).

Remark 3.7. In the infinite case, we do not actually need to assume that $`a>0`$. That is, suppose that $`Q`$ is a transition matrix of a Markov chain that is reversible with respect to a positive measure $`\pi `$. Assume that $`c:=inf\left\{\pi (x)Q(x,y);xy\text{ and }Q(x,y)>0\right\}>0`$. If $`\pi `$ is infinite, then

$$Q^k(x,x)/\pi (x)\frac{4}{c\sqrt{k+1}}.$$

To see this, we have only to establish that

$$|f(x_0)|(1/c)\underset{x,yV}{}c_2(x,y)|f(x)f(y)|$$

as a substitute for (3.5). Let $`E_2:=\{(x,y);Q^2(x,y)>0\}`$. Because $`\pi `$ is infinite, for any finite set $`S`$ of states, there is some $`y`$ such that $`Q(y,S)Q(y,S^c)>0`$, where $`Q(y,A):=_{zA}Q(y,z)`$. Note that $`Q(y,S)+Q(y,S^c)=1`$. Either $`Q(y,S)`$ or $`Q(y,S^c)`$ is at least $`1/2`$ and $`\pi (y)`$ times the other is at least $`c`$, whence

$$\pi (y)Q(y,S)Q(y,S^c)c/2.$$

It follows that

$$\begin{array}{ccc}\hfill \underset{xS}{}\underset{zS}{}c_2(x,z)& =\underset{xS}{}\pi (x)\underset{zS}{}Q^2(x,z)=\underset{xS}{}\pi (x)\underset{y}{}\underset{zS}{}Q(x,y)Q(y,z)\hfill & \\ & =\underset{y}{}\pi (y)Q(y,S)Q(y,S^c)c/2.\hfill & \end{array}$$

That is, for any cutset of edges $`eE_2`$ that separates $`x_0`$ from infinity in the graph $`(V,E_2)`$, the sum of $`c_2(e)`$ over the cutset is at least $`c/2`$. Therefore, the max-flow min-cut theorem provides a flow $`\theta `$ from $`x_0`$ to infinity of value $`c/2`$ that is bounded by $`c_2`$ on each edge in $`E_2`$. This yields

$$\begin{array}{ccc}\hfill |f(x_0)|c& =\left|\underset{(x,y)E_2}{}\left[f(x)f(y)\right]\theta (x,y)\right|\underset{(x,y)E_2}{}|f(x)f(y)||\theta (x,y)|\hfill & \\ & \underset{(x,y)E_2}{}|f(x)f(y)|c_2(x,y),\hfill & \end{array}$$

as desired. (Recall that each pair $`(x,y)`$ is counted twice in the sum.)

Remark 3.8. The proofs as given show the very same bounds on the more general quantities $`|Q^k(y,x)/\pi (y)1|`$ or $`Q^k(y,x)/\pi (y)`$ for all states $`x,y`$ and all $`k0`$.

Corollary 3.9. If $`\rho `$ is a probability measure on infinite rooted graphs with finite expected degree, then $`𝐡(\rho )`$ is finite.

Proof. For a graph $`G`$ with transition matrix $`P`$, let $`Q:=(I+P)/2`$. Then $`Q`$ is the transition matrix of the graph $`G^{}`$ obtained from $`G`$ by adding loops to each vertex so as to double its degree. Write $`q_k(x;G):=p_k(x;G^{})`$. Lemma 3.5 tells us that

$$\underset{k}{}q_k(x;G)/k=\mathrm{log}2+\underset{k}{}p_k(x;G)/k.$$

In addition, $`Q`$ is reversible with respect to the measure $`x\mathrm{deg}_G(x)`$, so that Lemma 3.6 applies with $`a1/2`$ and $`c1/2`$ (equality holds in both cases when $`G`$ has no loops) to yield

$$q_k(x;G)\frac{4}{\sqrt{k+1}}\mathrm{deg}_G(x).$$

Therefore,

$$\begin{array}{ccc}\hfill 𝐡(\rho )& =\mathrm{log}2+\left(\mathrm{log}\mathrm{deg}_G(x)\underset{k1}{}q_k(x;G)/k\right)𝑑\rho (G,x)\hfill & \\ & \mathrm{log}2+\left(\mathrm{log}\mathrm{deg}_G(x)\underset{k1}{}\frac{4}{k\sqrt{k+1}}\mathrm{deg}_G(x)\right)𝑑\rho (G,x)\hfill & \\ & =\mathrm{log}2+\mathrm{log}\mathrm{deg}_G(x)d\rho (G,x)\overline{\mathrm{deg}}(\rho )\underset{k1}{}\frac{4}{k\sqrt{k+1}}.\hfill & \end{array}$$

This gives the corollary by the inequality between the arithmetic and geometric means.

The following lemma is well known.

Lemma 3.10. Suppose that $`Y_n`$ are real-valued random variables that converge in distribution to $`Y`$ and that $`sup_n𝐄\left[|Y_n|\right]<\mathrm{}`$. Then for all continuous functions $`f:RR`$ such that $`lim_{|x|\mathrm{}}|f(x)|/|x|=0`$, we have $`lim_n\mathrm{}𝐄\left[f(Y_n)\right]=𝐄\left[f(Y)\right]`$.

Proof. The hypotheses easily imply that $`f(Y_n)`$ form a uniformly integrable set of random variables. The continuity of $`f`$ ensures that $`f(Y_n)`$ converge in distribution to $`f(Y)`$. Together, these imply the conclusion.

Proof of Theorem 3.3. We claim that the more general second statement of the theorem follows from the first statement. The space of rooted-isomorphism classes of graphs is complete, separable and metrizable (see \[MR2023650???\] for some of the details). Thus, under the hypothesis of the second statement, we may assume by Skorohod’s theorem (see, e.g., Theorem 11.7.2 of \[MR91g:60001???\]) that $`G_n`$ are defined on a common probability space such that a.s., $`G_n`$ has a random weak limit $`\rho `$. Therefore, if the first statement holds, then so does the second.

We now prove the first statement. Double the degree of each vertex in $`G_n`$ by adding loops to give graphs $`G_n^{}`$. These new graphs have transition matrices $`Q_n:=(I+P_n)/2`$, where $`P_n`$ is the transition matrix of $`G_n`$. Furthermore, the random weak limit of $`G_n^{}`$ is $`\rho ^{}`$, where $`\rho ^{}`$ is obtained from $`\rho `$ by doubling the degree of each vertex by adding loops. By Lemma 3.5, we have $`𝐡(\rho ^{})=𝐡(\rho )`$. Also, $`\tau (G_n^{})=\tau (G_n)`$, so it suffices to show that

$$\underset{n\mathrm{}}{lim}\frac{1}{|𝖵(G_n^{})|}\mathrm{log}\tau (G_n^{})=𝐡(\rho ^{}).$$

Let $`d`$ be an upper bound for the average degree of $`G_n^{}`$, i.e., for all $`n`$,

$$2|𝖤(G_n^{})|d|𝖵(G_n^{})|,$$
$`(3.7)`$
so that $`|𝖵(G_n^{})|^1\mathrm{log}\left(2|𝖤(G_n^{})|\right)0`$ as $`n\mathrm{}`$. Since the degree of a random vertex in $`G_n^{}`$ converges in distribution to the degree of the root under $`\rho ^{}`$, it follows that

$$\frac{1}{|𝖵(G_n^{})|}\underset{x𝖵(G_n^{})}{}\mathrm{log}\mathrm{deg}_{G_n^{}}(x)\mathrm{log}\mathrm{deg}_G(x)d\rho ^{}(G,x)$$

by Lemma 3.10 \[use there $`f:=\mathrm{log}^+`$ and $`Y_n`$ equals the degree of a uniform vertex in $`G_n^{}`$\]. Thus, in using Proposition 3.1, we have left to show only that

$$\underset{n\mathrm{}}{lim}\underset{k1}{}|𝖵(G_n^{})|^1\frac{1}{k}\left(\underset{x𝖵(G_n^{})}{}p_k(x;G_n^{})1\right)=\underset{k1}{}\frac{1}{k}p_k(x;G)d\rho ^{}(G,x).$$

By definition and the hypothesis, we have for each $`k`$ that

$$\underset{n\mathrm{}}{lim}|𝖵(G_n^{})|^1\left(\underset{x𝖵(G_n^{})}{}p_k(x;G_n^{})1\right)=p_k(x;G)𝑑\rho ^{}(G,x).$$

Lemma 3.6 applies to $`G_n^{}`$ with stationary probability measure $`x\mathrm{deg}_{G_n^{}}(x)/\left[2|𝖤(G_n^{})|\right]`$ and constants $`a1/2`$, $`c1/[4|𝖤(G_n^{})|]`$ to yield

$$|𝖵(G_n^{})|^1\left|\underset{x𝖵(G_n)}{}p_k(x;G_n^{})1\right|\frac{4d}{\sqrt{k+1}}.$$

Hence Weierstrass’ M-test justifies the interchange of limit and summation and we are done.

Remark 3.11. A similar result holds for weighted graphs. That is, given a graph $`G`$ whose edges are assigned positive weights, write $`\tau (G)`$ for the sum of the weights of its spanning trees, where the weight of a spanning tree is the product of the weights of its edges. Let the weight of a vertex be the sum of the weights of its incident edges. The random walk corresponding to a weighted graph has transition probability from $`x`$ to $`y`$ equal to the sum of the weights of the edges joining $`x`$ to $`y`$ divided by the weight of $`x`$. If a sequence of weighted connected finite graphs with weights bounded above and away from 0 and with bounded average vertex weight has a random weak limit $`\rho `$ on weighted rooted infinite graphs, then the conclusion of Theorem 3.3 holds, where $`𝐡(\rho )`$ is defined using the weight of the root in place of its degree and by using the weighted random walk on the limit graph.

We now illustrate some of the consequences of Theorem 3.3. Our first result concerns the stability of the asymptotic complexity, for which we prepare with a lemma related to tightness.

Let $`B_R(x)=(𝖵_R(x),𝖤_R(x))`$ denote the ball of radius $`R`$ about a vertex $`x`$.

Lemma 3.12. Let $`G_n`$ be a sequence of finite graphs with vertex subsets $`W_n𝖵(G_n)`$ satisfying $`lim_n\mathrm{}|W_n|/v_n=0`$, where $`v_n:=|𝖵(G_n)|`$. For $`R>0`$, let

$$s_n(R,t):=|\{x𝖵(G_n);|𝖵_R(x)|>t\}|.$$

Let also

$$w_n(R):=|\{x𝖵(G_n);𝖵_R(x)W_n\mathrm{}\}|.$$

If for each $`R>0`$, we have

$$\underset{t\mathrm{}}{lim}\underset{n\mathrm{}}{lim\; sup}s_n(R,t)/v_n=0,$$
$`(3.8)`$
then for each $`R>0`$, we have $`lim_n\mathrm{}w_n(R)/v_n=0`$.

Proof. We have that $`𝖵_R(x)W_n\mathrm{}`$ iff $`x`$ lies in a ball of radius $`R`$ about some vertex of $`W_n`$. If we partition $`W_n`$ in two, one part consisting of those vertices $`x`$ with $`|𝖵_R(x)|t`$ and the other part consisting of the rest, then we deduce that

$$w_n(R)t|W_n|+s_n(2R,t)$$

for any $`R>0`$ and $`t>0`$. Thus,

$$\underset{n\mathrm{}}{lim\; sup}w_n(R)/v_n\underset{n\mathrm{}}{lim\; sup}s_n(2R,t)/v_n.$$

If we now let $`t\mathrm{}`$, we obtain the desired result.

Note that (3.8) holds if $`G_n`$ has a random weak limit. In fact, (3.8) is just slightly weaker than tightness, since this condition counts vertices, while tightness counts edges.

Corollary 3.13. Let $`G_n`$ be a tight sequence of finite connected graphs with bounded average degree such that $`lim_n\mathrm{}|𝖵(G_n)|^1\mathrm{log}\tau (G_n)=h.`$ If $`G_n^{}`$ is a sequence of connected subgraphs of $`G_n`$ such that

$$\underset{n\mathrm{}}{lim}|𝖵(G_n)|^1|\{x𝖵(G_n^{});\mathrm{deg}_{G_n^{}}(x)=\mathrm{deg}_{G_n}(x)\}|=1,$$

then $`lim_n\mathrm{}|𝖵(G_n^{})|^1\mathrm{log}\tau (G_n^{})=h`$.

Proof. By taking a subsequence, if necessary, we may assume (by tightness) that $`G_n`$ has a random weak limit, $`\rho `$. By Theorem 3.3, we have $`h=𝐡(\rho )`$. Let $`W_n:=\{x𝖵(G_n^{});\mathrm{deg}_{G_n^{}}(x)\mathrm{deg}_{G_n}(x)\}`$. Then (3.8) holds because of tightness, whence $`G_n^{}`$ also has the random weak limit $`\rho `$ by Lemma 3.12. Hence Theorem 3.3 applies again to give the desired conclusion.

We next illustrate the flexibility of Theorem 3.3 by considering hybrid graphs as follows.

Corollary 3.14. Let $`G_n`$ and $`G_n^{}`$ be tight sequences of finite connected graphs with bounded average degree such that

$$\underset{n\mathrm{}}{lim}|𝖵(G_n)|^1\mathrm{log}\tau (G_n)=h\text{and}\underset{n\mathrm{}}{lim}|𝖵(G_n^{})|^1\mathrm{log}\tau (G_n)=h^{}.$$

Suppose that

$$\underset{n\mathrm{}}{lim}\frac{|𝖵(G_n)|}{|𝖵(G_n)|+|𝖵(G_n^{})|}=\alpha [0,1].$$

Let $`H_n`$ be formed by connecting disjoint copies of $`G_n`$ and $`G_n^{}`$ with $`o\left(|𝖵(G_n)|+|𝖵(G_n^{})|\right)`$ edges in any manner that gives a sequence of connected graphs. Then

$$\underset{n\mathrm{}}{lim}\frac{1}{|𝖵(H_n)|}\mathrm{log}\tau (H_n)=\alpha h+(1\alpha )h^{}.$$

Proof. By taking subsequences, if necessary, we may assume that $`G_n`$ and $`G_n^{}`$ have random weak limits, $`\rho `$ and $`\rho ^{}`$. By Theorem 3.3, we have $`h=𝐡(\rho )`$ and $`h^{}=𝐡(\rho ^{})`$. By Lemma 3.12, the random weak limit of $`H_n`$ is $`\alpha \rho +(1\alpha )\rho ^{}`$. Thus Theorem 3.3 gives the desired conclusion.

Given probability measures $`\rho _n`$ and $`\rho `$ on rooted graphs, we say that $`\rho _n`$ converges weakly to $`\rho `$ if $`p(R,H,\rho _n)p(R,H,\rho )`$ as $`n\mathrm{}`$ for any positive integer $`R`$ and any finite graph $`H`$. It is not hard to show that tree entropy is a continuous functional when one bounds the expected degree:

Proposition 3.15. If $`\rho _n`$ converges weakly to $`\rho `$ as $`n\mathrm{}`$ with $`sup_n\overline{\mathrm{deg}}(\rho _n)<\mathrm{}`$, then $`𝐡(\rho _n)𝐡(\rho )`$ as $`n\mathrm{}`$.

Proof. As in the proof of Theorem 3.3, we may double the degree of each vertex by adding loops without changing the tree entropies. By Lemma 3.10 and our assumption of bounded expected degree, we have $`\mathrm{log}\mathrm{deg}_G(x)d\rho _n(G,x)\mathrm{log}\mathrm{deg}_G(x)d\rho (G,x)`$. Weak convergence itself already guarantees that $`p_k(x;G)𝑑\rho _n(G,x)p_k(x;G)𝑑\rho (G,x)`$ for each $`k`$. The bounded expected degree and Lemma 3.6 allow us to apply Weierstrass’ M-test to get the desired conclusion.

We now give several explicit examples illustrating the use of tree entropy, beginning with the transitive case.

In order to evaluate the infinite sum appearing in $`𝐡(G)`$, the following integral is sometimes useful. Let $`𝒢(z):=𝒢(z;G):=_{k0}p_k(o;G)z^k`$ be the return probability generating function of the graph $`G`$. Then clearly

$$\underset{k1}{}\frac{1}{k}p_k(o;G)=_0^1\frac{𝒢(z)1}{z}𝑑z.$$
$`(3.9)`$
Example 3.16. For a group $`\mathrm{\Gamma }`$ with a given generating set, let $`\mathrm{}(\mathrm{\Gamma })`$ denote the length of the smallest (nonempty) reduced word in the generating elements that represents the identity, i.e., the girth of the Cayley graph of $`\mathrm{\Gamma }`$. Suppose that $`\mathrm{\Gamma }_n`$ are finite groups, each generated by $`s`$ elements, such that $`lim_n\mathrm{}\mathrm{}(\mathrm{\Gamma }_n)=\mathrm{}`$. Then the Cayley graphs $`G_n`$ of $`\mathrm{\Gamma }_n`$ have a random weak limit equal to the usual Cayley graph $`G`$ of the free group $`\mathrm{\Gamma }`$ on $`s`$ letters, i.e., the regular tree of degree $`2s`$. By Theorem 3.3, it follows that

$$\underset{n\mathrm{}}{lim}|\mathrm{\Gamma }_n|^1\mathrm{log}\tau (G_n)=𝐡(G),$$

independently of the particular choice of $`\mathrm{\Gamma }_n`$. To evaluate $`𝐡(G)`$, we use the fact that the return series is

$$𝒢(z;G)=\frac{1s+\sqrt{s^2(2s1)z^2}}{1z^2},$$

a result of \[MR22:253???\]. The integrand in (3.9) then has an “elementary” antiderivative, which yields

$$𝐡(G)=\mathrm{log}\frac{(2s1)^{2s1}}{[4s(s1)]^{s1}}.$$

For example, for $`s=2`$, we find $`𝐡(G)=\mathrm{log}(3/2)^3`$. More generally, when $`G`$ is the regular tree of degree $`d`$, we have

$$𝒢(z;G)=\frac{2(d1)}{d2+\sqrt{d^24(d1)z^2}}$$

(see, e.g., Lemma 1.24 of \[MR2001k:60006???\]), whence

$$𝐡(G)=\mathrm{log}\frac{(d1)^{d1}}{[d(d2)]^{d/21}}.$$

For example, $`𝐡(G)=\mathrm{log}(4/\sqrt{3})`$ if $`d=3`$. As we mentioned in the introduction, this calculation of the asymptotic complexity of regular graphs with girth tending to infinity was first done by \[MR85d:05194???\] under additional hypotheses on the graphs. For the case of (uniformly) random $`d`$-regular graphs, where it is easy to see that they have a random weak limit equal to the $`d`$-regular tree, $`G`$, we obtain that the asymptotic complexity tends in probability to $`𝐡(G)`$; this was also shown by \[MR85d:05194???\], who showed in \[MR83g:05030???\] that random regular graphs satisfy his extra hypotheses.

Example 3.17. The usual Erdős-Rényi model of random graphs, $`𝒢(n,p)`$, is a graph on $`n`$ vertices, each pair of which is connected by an edge with probability $`p`$, independently of other edges. Other language for this is Bernoulli($`p`$) bond percolation on the complete graph $`K_n`$. Fix $`c>1`$. The well-known fact that the entire graph $`𝒢(n,c/n)`$ has a random weak limit $`\mathrm{𝖯𝖦𝖶}(c)`$ is proved explicitly in \[MR99k:60212???\], where $`\mathrm{𝖯𝖦𝖶}(c)`$ is the law of a rooted Galton-Watson tree with Poisson($`c`$) offspring distribution. It is well known that with probability approaching 1 as $`n\mathrm{}`$, there is a unique connected component, called the giant component, of $`𝒢(n,c/n)`$, that has $`\mathrm{\Omega }(n)`$ vertices. See, e.g., \[MR2002j:05132???\]. Also, the giant component has a random weak limit $`\mathrm{𝖯𝖦𝖶}^{}(c)`$, which is $`\mathrm{𝖯𝖦𝖶}(c)`$ conditioned on nonextinction. This limit of the giant component is folklore and seems not to be written anywhere. Let $`f(c):=𝐡\left(\mathrm{𝖯𝖦𝖶}^{}(c)\right)`$. We also define $`\mathrm{𝖯𝖦𝖶}^{}(1)`$ to be the weak limit of $`\mathrm{𝖯𝖦𝖶}^{}(c)`$ as $`c1`$. Since $`\mathrm{𝖯𝖦𝖶}^{}(1)`$ is the random weak limit of trees (more specifically, of the uniform spanning tree on $`K_n`$) by \[MR82g:05042???\], we have $`f(1)=0`$ (which also follows from Theorem –?– below). By Proposition 3.15, $`f`$ is continuous on $`[1,\mathrm{})`$. We wonder whether $`f`$ is strictly increasing on $`[1,\mathrm{})`$ and real analytic on $`(1,\mathrm{})`$. The fact that $`f(c)>0`$ for $`c>1`$ follows from Theorem –?– below, together with the well-known fact that $`\mathrm{𝖯𝖦𝖶}^{}(c)`$ has infinitely many ends a.s. for $`c>1`$. It would be interesting to see an explicit formula for $`f`$.

An additional useful tool for calculation is explained in Section 9 of \[MR2001k:60006???\]. Namely, as explained there, if we let $`𝐫`$ be the radius of convergence of $`𝒢()`$, then there is a strictly increasing function $`\mathrm{\Phi }:=\mathrm{\Phi }_G:[0,𝐫𝒢(𝐫))R`$ such that

$$𝒢(z)=\mathrm{\Phi }\left(z𝒢(z)\right)$$
$`(3.10)`$
on $`[0,𝐫𝒢(𝐫))`$. We are grateful to W. Woess for pointing out to us the remainder of this paragraph. In many cases, it is easier to find $`\mathrm{\Phi }`$ than to (solve and) find $`𝒢`$. Note that from (3.10), we have

$$𝒢(1)=\mathrm{\Phi }\left(𝒢(1)\right);$$
$`(3.11)`$
it can be much easier to solve for $`𝒢(1)`$ and use that in –?– below than it is to solve (3.10) for $`𝒢`$ and use that in (3.9). Substitute (3.10) in the right-hand side of (3.9) to obtain

$$_0^1\frac{𝒢(z)1}{z}𝑑z=_0^1\frac{\mathrm{\Phi }\left(z𝒢(z)\right)1}{z}𝑑z.$$

Now use the change of variable $`t:=z𝒢(z)`$. This gives us

$$\begin{array}{ccc}\hfill _0^1\frac{\mathrm{\Phi }\left(z𝒢(z)\right)1}{z}𝑑z& =_0^{𝒢(1)}\frac{\left(\mathrm{\Phi }(t)1\right)\left(\mathrm{\Phi }(t)t\mathrm{\Phi }^{}(t)\right)}{t\mathrm{\Phi }(t)}𝑑t\hfill & \\ & =_0^{𝒢(1)}\frac{\mathrm{\Phi }(t)1}{t}𝑑t\mathrm{\Phi }\left(𝒢(1)\right)+1+\mathrm{log}\mathrm{\Phi }\left(𝒢(1)\right)\hfill & \\ & =_0^{𝒢(1)}\frac{\mathrm{\Phi }(t)1}{t}𝑑t𝒢(1)+1+\mathrm{log}𝒢(1).\hfill & \end{array}$$

Thus, we have

$$𝐡(G)=\mathrm{log}d_0^{𝒢(1)}\frac{\mathrm{\Phi }(t)1}{t}𝑑t+𝒢(1)1\mathrm{log}𝒢(1).$$
$`(3.12)`$
If we are interested only in the asymptotic complexity of finite graphs, for which $`\rho `$ would we want to calculate $`𝐡(\rho )`$? This is answered in Section ?? , where we shall see that all $`\rho `$ whose underlying graph is a fixed Cayley graph are included, among others.

Example 3.18. Suppose that $`G`$ is the free product $`K_{s_1}\mathrm{}K_{s_n}`$ of the complete graphs $`K_{s_1}`$, …, $`K_{s_n}`$ for some integers $`s_j2`$ with $`_js_j5`$. In other words, $`G`$ is the Cayley graph of the free product of groups of order $`s_j`$ with respect to the generating set corresponding to every element of the factors other than the identities. In order to calculate $`𝐡(G)`$, we shall find it easier to work with the graph $`G^{}`$, in which we have added $`n`$ loops to each vertex of $`G`$. By Lemma 3.5, we have $`𝐡(G^{})=𝐡(G)`$. Let $`d:=_{j=1}^ns_j`$ be the degree of $`G^{}`$. Now by \[MR86i:60181???\], we have

$$\mathrm{\Phi }_G^{}(z)=1+\frac{zn}{2}+\frac{1}{2}\underset{j=1}{\overset{n}{}}\sqrt{(1s_jz/d)^2+4z/d}.$$

For example, if $`n=2`$, then (3.11) gives that $`𝒢(1,G^{})=s_1s_2/(s_1s_2s_1s_2)`$. We then find via (3.12) applied to $`G^{}`$ that

$$𝐡(G)=\left(1\frac{1}{s_1}\right)\mathrm{log}(s_11)+\left(1\frac{1}{s_2}\right)\mathrm{log}(s_21)+\left(1\frac{1}{s_1}\frac{1}{s_2}\right)\mathrm{log}\frac{s_1+s_2}{s_1s_2s_1s_2}.$$

For example, if $`s_1=2`$ and $`s_2=3`$, when $`G`$ is a Cayley graph of the modular group $`\mathrm{PSL}(2,Z)`$ \[use the generators $`\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)`$ and $`\left(\begin{array}{cc}0& 1\\ 1& 1\end{array}\right)`$\], then $`𝐡(G)=\mathrm{log}\left(2^{2/3}5^{1/6}\right)`$. As examples of other tree entropies that one may find by similar means, we mention that $`𝐡(G)=\mathrm{log}(16/3)`$ if $`n=3`$ with $`s_1=s_2=s_3=3`$, while

$$𝐡(G)=\mathrm{log}(61+9\sqrt{57})+\frac{1}{6}\mathrm{log}(31733\sqrt{57})\frac{7}{2}\mathrm{log}2\mathrm{log}7=1.190^+$$

if $`n=3`$ with $`s_1=s_2=2`$ and $`s_3=3`$. As an application, suppose that $`H_n`$ is a random 3-regular 3-uniform hypergraph on $`n`$ vertices. Let $`G_n`$ be the associated graph in which every hyperedge of $`H_n`$ is replaced by a clique on its vertices. Then $`G_n`$ tends weakly to $`K_3K_3K_3`$, whence $`n^1\mathrm{log}\tau (G_n)\mathrm{log}(16/3)`$.

Example 3.19. Choose a ray $`x_m;m0`$ in the regular tree $`T`$ of degree 3. Let $`G_m`$ be the ball in $`T`$ of radius $`m`$ about $`x_m`$. Remove the edge $`[x_m,x_{m+1}]`$ from $`G_m`$; let $`T_m`$ be the connected component of $`x_m`$ that remains. Thus, $`T_mT_{m+1}`$ for all $`m`$. Let $`G:=_{m1}T_m`$. The random weak limit of $`G_m`$ is $`\rho `$, where $`\rho (G,x_m):=2^{m1}`$ for $`m0`$. Since $`\tau (G_m)=1`$, Theorem 3.3 tells us that $`𝐡(\rho )=0`$, i.e.,

$$\underset{k1}{}\frac{1}{k}\underset{m0}{}2^{m1}p_k(x_m;G)=\mathrm{log}\sqrt{3}.$$

We comment finally on situations where the average degree of $`G_n`$ is not bounded. We suspect that the following holds for “lazy” simple random walk $`Q_G:=(I+P_G)/2`$ on any simple (unweighted) graph for some universal constant $`C`$:

$$k2|𝖵(G)|^1\left(\mathrm{tr}Q_G^k1\right)\frac{C}{\mathrm{log}^2k}.$$
$`(3.13)`$
(It may even be true with $`\mathrm{log}^2k`$ replaced by something like $`k^{1/3}`$, but as Ben Morris has pointed out, nothing better than $`k^{1/3}`$ is possible, as shown by the example of two cliques on $`n`$ vertices joined by a path of length $`n`$.) If (3.13) holds, this would replace Lemma 3.6 (except in the proof of Corollary 3.9) and allow results still more general than Theorem 3.3 for simple graphs.

As we have not been able to establish (3.13), we consider instead sequences $`G_n`$ that are an expanding family, meaning that the second largest eigenvalue $`\lambda _2(G_n)`$ of $`P_{G_n}`$ is bounded away from 1. In this case, we do not need Lemma 3.6, since if $`Q_n=Q_{G_n}`$ is the transition matrix in the proof of Theorem 3.3, we have

$$|𝖵(G_n)|^1\left(\mathrm{tr}Q_n^k1\right)\left(\frac{1+\lambda _2(G_n)}{2}\right)^k$$

for all $`n,k1`$. In addition, we do not need Lemma 3.5; that can be replaced with the corresponding statement for finite Markov chains,

$$\underset{k1}{}(\mathrm{tr}Q^k1)/k=\mathrm{log}(1\alpha )+\underset{k1}{}(\mathrm{tr}P^k1)/k,$$

where $`P`$ and $`Q`$ are as in Lemma 3.5.

If the average degree of $`G_n`$ is unbounded, we must consider a different normalization of the complexity. Let us assume that the limit (as $`n\mathrm{}`$) of the return probability after $`k`$ steps of simple random walk started at a random vertex of $`G_n`$ exists; denote it by $`p_k`$. For example, if $`G_n`$ has a random weak limit $`\rho `$ that is concentrated on infinite graphs of finite degree, then $`p_k=p_k(o;G)𝑑\rho (G,o)`$. For another example, $`p_k=0`$ when $`k1`$ for simple graphs whose minimum degree tends to infinity. The proof of Theorem 3.3 (as modified above) shows that

$$\underset{n\mathrm{}}{lim}|𝖵(G_n)|^1\left[\mathrm{log}\tau (G_n)\underset{x𝖵(G_n)}{}\mathrm{log}\mathrm{deg}x\right]=\underset{k1}{}p_k/k.$$

For a particular example, if $`G_n`$ is the giant component of the random graph $`𝒢(n,p_n)`$ with $`np_n\mathrm{log}n\mathrm{}`$ (which has $`n`$ vertices with probability tending to 1; see, e.g., Theorem 9 of Chapter VII in \[MR99h:05001???\]), one has

$$\underset{n\mathrm{}}{lim}\left(n^1\mathrm{log}\tau (G_n)\mathrm{log}(p_nn)\right)=0$$

in probability. To facilitate comparison to Cayley’s theorem (that $`\tau (K_n)=n^{n2}`$), we may state this as $`\tau (G_n)=\left([1+o(1)]p_nn\right)^n`$. (The fact that $`G_n`$ is an expanding family a.s. is probably folklore. It can be proved as follows: First, the proof that $`𝒢(n,p_n)`$ is connected with probability approaching 1 is easily modified to show that its isoperimetric constant, also called conductance, is bounded away from 0 a.s. Second, a well-known inequality relating this constant to the second largest eigenvalue gives the result; see, e.g., \[MR97e:05140???\].)

§4. Tree Entropy as Log Determinant.

Under certain assumptions, Theorem 3.3 shows that if $`\rho `$ is a random weak limit of finite connected graphs, $`G_n`$, then its tree entropy $`𝐡(\rho )`$ is a limit of the logarithm of the determinant of the graph Laplacians of $`G_n`$, normalized by omitting the zero eigenvalue and by dividing by the number of vertices of $`G_n`$. In fact, one may give a formula for $`𝐡(\rho )`$ directly in terms of a normalized determinant of the graph Laplacian for infinite graphs. This is our main purpose in the present section. We shall also use this formula to prove inequalities for tree entropy and to calculate easily and quickly the classical tree entropy for Euclidean lattices.

We first discuss the class of probability measures $`\rho `$ to which our formula will apply. This class, the class of $`\rho `$ that arise as limits of finite graphs, is the class of unimodular $`\rho `$, defined as follows. Given a rooted graph $`(G,x)`$ and an edge $`e`$ incident to $`x`$, define the involution $`\iota (G,x,e):=(G,y,e)`$, where $`y`$ is the other endpoint of $`e`$. Given a probability measure $`\rho `$ on rooted graphs, define the probability measure $`\widehat{\rho }`$ to be the law of the isomorphism class of $`(G,x,e)`$, where $`(G,x)`$ is chosen according to $`\rho `$ and $`e`$ is then chosen uniformly among the edges incident to $`x`$. Also, define $`\stackrel{~}{\rho }`$ to be the (non-probability) measure that is the result of biasing $`\widehat{\rho }`$ by the degree of the root; that is, the Radon-Nikodým derivative of $`\stackrel{~}{\rho }`$ with respect to $`\widehat{\rho }`$ at the isomorphism class of $`(G,x,e)`$ is $`\mathrm{deg}_G(x)`$. (If the expected degree of the root is finite, one could obtain a probability measure from $`\stackrel{~}{\rho }`$ by dividing by the expected degree; but this is not always the case.) The involution $`\iota `$ induces a pushforward map $`\stackrel{~}{\rho }\iota _{}\stackrel{~}{\rho }`$. We say that $`\rho `$ is unimodular or involution invariant if $`\iota _{}\stackrel{~}{\rho }=\stackrel{~}{\rho }`$. It is easy to see that any $`\rho `$ that is a random weak limit of finite graphs is unimodular, as observed by \[MR2023650???\], who introduced the notion of involution invariance; essentially the same observation occurs in \[MR1873300???\]. The converse is much harder, but is established in \[AL:uni???\]. Intuitively, unimodularity means that, up to isomorphism, all vertices are equally likely to be the root. See \[AL:uni???\] for a comprehensive treatment of unimodular random networks. In particular, it is shown there that a transitive graph is unimodular iff it is unimodular as a rooted random graph.

The preceding definitions and results extend easily to the class of rooted weighted graphs or multi-graphs $`(G,o)`$, where $`G=(𝖵(G),𝖤(G),w)`$ and $`w:𝖤(G)[0,\mathrm{})`$ is a weight function as in Remark 3.11. For $`xy𝖵(G)`$, let $`\mathrm{\Delta }_G(x,y):=_ew(e)`$, where the sum is over all the edges between $`x`$ and $`y`$, and $`\mathrm{\Delta }_G(x,x):=_ew(e)`$, where the sum is over all non-loop edges incident to $`x`$. We assume that $`\mathrm{\Delta }_G(x,x)<\mathrm{}`$ for all $`x`$. The associated random walk has the transition probability from $`x`$ to $`y`$ of $`\mathrm{\Delta }_G(x,y)/\mathrm{\Delta }_G(x,x)`$. Extend the definition of tree entropy to probability measures on rooted weighted graphs by

$$𝐡(\rho ):=\left(\mathrm{log}\mathrm{\Delta }_G(o,o)\underset{k1}{}\frac{1}{k}p_k(o;G)\right)𝑑\rho (G,o)$$

whenever this integral converges, where $`p_k(o;G)`$ is the return probability after $`k`$ steps for the associated random walk.

The (graph) Laplacian $`\mathrm{\Delta }_G`$ just defined determines an operator

$$f\left(x\underset{y𝖵}{}\mathrm{\Delta }_G(x,y)f(y)\right)$$

for functions $`f`$ on $`𝖵`$ with finite support. This operator extends by continuity to a bounded linear operator on all of $`\mathrm{}^2(𝖵)`$ when $`sup_x\mathrm{\Delta }_G(x,x)<\mathrm{}`$. In case we do not have such a uniform bound, we proceed as follows. Let $`U_e`$ be a uniform $`[0,1]`$-valued random variable chosen independently for all $`e`$. Given $`MZ^+`$, let $`G^{}`$ be the random weighted graph obtained from $`G`$ by letting the weight of $`e`$ be $`w(e)(1U_e/M)`$. Now let $`G_M`$ be the weighted graph formed from $`G^{}`$ by changing the weight to 0 of those edges $`e`$ whose weights are greater than $`M`$ or which are not among the $`M`$ largest weights of the edges incident to (or equal to) $`e`$. Clearly the matrix $`\mathrm{\Delta }_{G_M}`$ converges to $`\mathrm{\Delta }_G`$ entrywise a.s. as $`M\mathrm{}`$. Since $`\mathrm{\Delta }_{G_M}`$ is a bounded self-adjoint positive semi-definite operator, the operator $`\mathrm{log}(\mathrm{\Delta }_{G_M}+ϵI)`$ is bounded for any $`ϵ>0`$, where $`I`$ denotes the identity operator on $`\mathrm{}^2(𝖵)`$. Let $`\rho _M`$ be the law of $`(G_M,o)`$ when $`(G,o)`$ has the law of $`\rho `$. If $`\rho `$ is unimodular, then so is $`\rho _M`$.

Now the logarithm of the determinant of a matrix equals the trace of the logarithm of the matrix. Furthermore, one usually defines the determinant via this equality when one has a trace on a von Neumann algebra. This is the approach we take.

The trace we use is defined by \[AL:uni???\], which we review here. Suppose that $`\rho `$ is a unimodular probability measure on rooted weighted graphs. Let $`T:(G,o)T_{G,o}`$ be a measurable assignment of bounded linear operators $`T_{G,o}:\mathrm{}^2\left(𝖵(G)\right)\mathrm{}^2\left(𝖵(G)\right)`$ with finite supremum of the norms $`T_{G,o}`$. Let $`\mathrm{𝖠𝗅𝗀}`$ be the von Neumann algebra of such operators $`T`$ that are equivariant in the sense that for all isomorphisms $`\gamma :G_1G_2`$ and all $`o,x,y𝖵(G)`$, we have $`(T_{G_2,\gamma o}\mathrm{𝟏}_{\{\gamma x\}},\mathrm{𝟏}_{\{\gamma y\}})=(T_{G_1,o}\mathrm{𝟏}_{\{x\}},\mathrm{𝟏}_{\{y\}})`$. Since $`T_{G,o}`$ does not depend on $`oG`$ for $`T\mathrm{𝖠𝗅𝗀}`$, we shall write $`T_G`$ in place of $`T_{G,o}`$ for $`T\mathrm{𝖠𝗅𝗀}`$. We define the trace of $`T\mathrm{𝖠𝗅𝗀}`$ to be

$$\mathrm{Tr}(T):=\mathrm{Tr}_\rho (T):=𝐄\left[(T_G\mathrm{𝟏}_{\{o\}},\mathrm{𝟏}_{\{o\}})\right]:=(T_G\mathrm{𝟏}_{\{o\}},\mathrm{𝟏}_{\{o\}})𝑑\rho (G,o).$$

For self-adjoint operators $`A`$ and $`B`$, recall that $`AB`$ means that $`((BA)v,v)0`$ for all vectors $`v`$. Our trace has the following properties: $`\mathrm{Tr}()`$ is linear, $`\mathrm{Tr}(T)0`$ for $`T0`$, and $`\mathrm{Tr}(ST)=\mathrm{Tr}(TS)`$ for $`S,T\mathrm{𝖠𝗅𝗀}`$. In addition, for any increasing function $`f:RR`$ and any $`ST`$, we have $`\mathrm{Tr}\left(f(S)\right)\mathrm{Tr}\left(f(T)\right)`$.

In effect, we now show the trace formula $`𝐡(\rho )=\mathrm{log}\mathrm{Det}_\rho \mathrm{\Delta }_G:=\mathrm{Tr}_\rho (\mathrm{log}\mathrm{\Delta }_G)`$. The determinant here is a so-called Fuglede-Kadison determinant; see \[MR0052696???\].

Theorem 4.1. If $`\rho `$ is a unimodular probability measure on rooted infinite weighted graphs with

$$|\mathrm{log}\mathrm{\Delta }_G(o,o)|𝑑\rho (G,o)<\mathrm{}$$
$`(4.1)`$
and

$$\frac{\mathrm{\Delta }_G(o,o)}{inf\{\mathrm{\Delta }_G(x,y);xy\text{ and }\mathrm{\Delta }_G(x,y)0\}}𝑑\rho (G,o)<\mathrm{},$$
$`(4.2)`$
then

$$𝐡(\rho )=\underset{M\mathrm{}}{lim}\underset{ϵ0}{lim}\mathrm{Tr}_\rho \left[\mathrm{log}(\mathrm{\Delta }_{G_M}+ϵI)\right].$$
$`(4.3)`$
Proof. It is obvious that $`\mathrm{\Delta }_{G_M}+ϵI`$ is monotone increasing in $`ϵ`$. Furthermore, it is easy to check that $`\mathrm{\Delta }_{G_M}`$ is monotone increasing in $`M`$. Since $`\mathrm{log}`$ is an increasing function, it follows that the limits exist in (4.3).

The condition (4.1) and Lebesgue’s Dominated Convergence Theorem guarantee that

$$\underset{M\mathrm{}}{lim}\mathrm{log}\mathrm{\Delta }_G(o,o)𝑑\rho _M(G,o)=\mathrm{log}\mathrm{\Delta }_G(o,o)𝑑\rho (G,o).$$

Clearly, for all $`k>0`$,

$$\underset{M\mathrm{}}{lim}p_k(o;G)𝑑\rho _M(G,o)=p_k(o;G)𝑑\rho (G,o).$$

By Remark 3.7 and (4.2), it follows that

$$\underset{M\mathrm{}}{lim}\underset{k1}{}\frac{1}{k}p_k(o;G)d\rho _M(G,o)=\underset{k1}{}\frac{1}{k}p_k(o;G)d\rho (G,o).$$

Therefore, we have

$$\underset{M\mathrm{}}{lim}𝐡(\rho _M)=𝐡(\rho ).$$
$`(4.4)`$
Let $`D_G`$ be the diagonal matrix that has the same diagonal as $`\mathrm{\Delta }_G`$. For $`ϵ>0`$, define $`P_{G,ϵ}`$ by

$$(D_G+ϵI)(IP_{G,ϵ})=\mathrm{\Delta }_G+ϵI.$$

In other words, $`P_{G,ϵ}(x,x)=0`$ and $`P_{G,ϵ}(x,y)=\mathrm{\Delta }_G(x,y)/(D_G(x,x)+ϵ)`$ for $`xy`$. The matrix $`P_{G,ϵ}`$ defines a killed random walk that, at $`x`$, is killed (sent to an absorbing cemetery state outside the graph $`G`$) with probability $`ϵ/(D_G(x,x)+ϵ)`$ and transits to $`y`$ with probability $`P_{G,ϵ}(x,y)`$. Let $`p_k(o;G,ϵ)`$ be the return probability after $`k`$ steps for the killed random walk. It is clear that as $`ϵ0`$, we have $`p_k(o;G,ϵ)p_k(o;G)`$. If the degrees of $`G`$ are bounded, then the norm of $`P_{G,ϵ}`$ is less than 1, whence

$$\mathrm{log}(IP_{G,ϵ})=\underset{k1}{}\frac{1}{k}P_{G,ϵ}^k;$$

in particular,

$$\underset{k1}{}\frac{1}{k}p_k(o;G,ϵ)=(\mathrm{log}(IP_{G,ϵ})\mathrm{𝟏}_{\{o\}},\mathrm{𝟏}_{\{o\}}).$$

By a theorem of \[MR0052696???\], we have therefore for any $`M`$,

$$\begin{array}{ccc}\hfill 𝐡(\rho _M)& =(\mathrm{log}D_G\mathrm{𝟏}_{\{o\}},\mathrm{𝟏}_{\{o\}})\underset{k1}{}\frac{1}{k}p_k(o;G)d\rho _M(G,o)\hfill & \\ & =\underset{ϵ0}{lim}(\mathrm{log}(D_G+ϵI)\mathrm{𝟏}_{\{o\}},\mathrm{𝟏}_{\{o\}})\underset{k1}{}\frac{1}{k}p_k(o;G,ϵ)d\rho _M(G,o)\hfill & \\ & =\underset{ϵ0}{lim}(\mathrm{log}(D_G+ϵI)\mathrm{𝟏}_{\{o\}},\mathrm{𝟏}_{\{o\}})+(\mathrm{log}(IP_{G,ϵ})\mathrm{𝟏}_{\{o\}},\mathrm{𝟏}_{\{o\}})d\rho _M(G,o)\hfill & \\ & =\underset{ϵ0}{lim}\mathrm{Tr}_{\rho _M}\left[\mathrm{log}(D_G+ϵI)+\mathrm{log}(IP_{G,ϵ})\right]\hfill & \\ & =\underset{ϵ0}{lim}\mathrm{Tr}_{\rho _M}\left[\mathrm{log}\left((D_G+ϵI)(IP_{G,ϵ})\right)\right]\hfill & \\ & =\underset{ϵ0}{lim}\mathrm{Tr}_{\rho _M}\left[\mathrm{log}(\mathrm{\Delta }_G+ϵI)\right].\hfill & \end{array}$$

Putting together this limit relation with that of (4.4), we obtain (4.3).

Remark 4.2. As $`\mathrm{\Delta }_G`$ is unchanged by the addition or deletion of loops, we see that neither is $`𝐡(\rho )`$.

As one indication of the usefulness of Theorem 4.1 beyond its theoretical interest, we show how it leads immediately to calculation of the classically known tree entropy for the nearest-neighbor graph on $`Z^d`$. In this case, the space $`\mathrm{}^2(Z^d)`$ is isometrically isomorphic to $`L^2\left([0,1]^d\right)`$ (with Lebesgue measure) via the Fourier transform. Under this isomorphism, the Laplace operator $`\mathrm{\Delta }_{Z^d}`$ becomes the operator of multiplication by the function $`(s_1,\mathrm{},s_d)2d2_{i=1}^d\mathrm{cos}(2\pi s_i)`$, the vector $`\mathrm{𝟏}_{\{o\}}`$ becomes the constant function $`\mathrm{𝟏}`$, and thus

$$𝐡(Z^d)=_{[0,1]^d}\mathrm{log}\left(2d2\underset{i=1}{\overset{d}{}}\mathrm{cos}(2\pi s_i)\right)𝑑s.$$

More generally, suppose that $`G`$ is a graph with vertex set $`Z^d\times K`$ for a finite set $`K`$ and with edge set that is invariant under the natural action of $`Z^d`$. That is, for each $`xZ^d`$, there is an $`K\times K`$ matrix $`L^x`$ such that for $`x,yZ^d`$ and $`u,vK`$,

$$\mathrm{\Delta }_G((x,u),(y,v))=L^{yx}(u,v).$$

Such graphs $`G`$ are called “periodic” by \[MR94m:60019???\]. Consider the measure $`\rho `$ that puts equal mass on each $`(G,(\mathrm{𝟎},u))`$ ($`uK`$). We may regard $`\mathrm{\Delta }_G`$ operating on $`\mathrm{}^2(Z^d\times K)`$ as an operator $`T`$ on $`\mathrm{}^2(Z^d;\mathrm{}^2(K))`$, that is, on the space of vector-valued functions $`f:Z^d\mathrm{}^2(K)`$ with $`_{xZ^d}f(x)_{\mathrm{}^2(K)}^2<\mathrm{}`$. Under the Fourier isomorphism with $`L^2([0,1]^d;\mathrm{}^2(K))`$, the operator $`T`$ becomes the operator of multiplication by the matrix-valued function

$$M:(s_1,s_2,\mathrm{},s_d)\underset{xZ^d}{}L^xe^{2\pi ixs}(s=(s_1,s_2,\mathrm{},s_d)[0,1]^d),$$

the vector $`\mathrm{𝟏}_{\{(\mathrm{𝟎},u)\}}`$ becomes the constant function $`\mathrm{𝟏}_{\{u\}}\mathrm{}^2(K)`$, and thus

$$\begin{array}{ccc}\hfill 𝐡(\rho )& =|K|^1\underset{uK}{}((\mathrm{log}\mathrm{\Delta }_G)\mathrm{𝟏}_{\{(\mathrm{𝟎},u)\}},\mathbf{\hspace{0.17em}1}_{\{(\mathrm{𝟎},u)\}})\hfill & \\ & =|K|^1\underset{uK}{}_{[0,1]^d}(\left(\mathrm{log}M(s)\right)\mathrm{𝟏}_{\{u\}},\mathbf{\hspace{0.17em}1}_{\{u\}})𝑑s\hfill & \\ & =|K|^1_{[0,1]^d}\mathrm{tr}\left(\mathrm{log}M(s)\right)𝑑s\hfill & \\ & =|K|^1_{[0,1]^d}\mathrm{log}detM(s)ds.\hfill & \end{array}$$

This is (a slightly simpler version of) the formula in Theorem 6.1(b) of \[MR94m:60019???\].

We consider next some inequalities. If $`\rho _1`$ and $`\rho _2`$ are two probability measures on rooted weighted graphs, let us say that $`\rho _1`$ is edge dominated by $`\rho _2`$ if there exists a probability measure $`\nu `$ on rooted graphs $`(G,o)`$ with two sets of weights $`(w_1,w_2)`$ such that for all edges $`e`$, we have $`w_1(e)w_2(e)`$ and such that the law of $`(G,o,w_i)`$ is $`\rho _i`$ for $`i=1,2`$. We call $`\nu `$ a monotone coupling of $`\rho _1`$ and $`\rho _2`$. When the weight of an edge is 0, one can regard it as being absent.

Theorem 4.3. If $`\rho _1\rho _2`$ are unimodular probability measures on rooted weighted infinite loop-less graphs that both satisfy (4.1) and (4.2) and $`\rho _1`$ is edge dominated by $`\rho _2`$, then $`𝐡(\rho _1)<𝐡(\rho _2)`$.

The proof relies on the following notion. A continuous function $`f:(0,\mathrm{})R`$ is called operator monotone on $`(0,\mathrm{})`$ if for any bounded self-adjoint operators $`A,B`$ with spectrum in $`(0,\mathrm{})`$ and $`AB`$, we have $`f(A)f(B)`$. \[lowner???\] proved that the logarithm is an operator monotone function on $`(0,\mathrm{})`$ (see also Chapter V of \[MR98i:15003???\]).

Proof. As in the proof of Theorem 4.1, we have that $`\mathrm{\Delta }_{G_M,w_1}\mathrm{\Delta }_{G_M,w_2}`$. Since $`\mathrm{log}`$ is an operator monotone function on $`(0,\mathrm{})`$, it follows that $`\mathrm{Tr}_{\rho _1}\left(\mathrm{log}(\mathrm{\Delta }_{G_M,w_1}+ϵI)\right)\mathrm{Tr}_{\rho _2}\left(\mathrm{log}(\mathrm{\Delta }_{G_M,w_2}+ϵI)\right)`$, so that $`𝐡(\rho _1)𝐡(\rho _2)`$ by Theorem 4.1. If $`𝐡(\rho _1)=𝐡(\rho _2)`$, then by Theorem 4.1, we have

$$\underset{M\mathrm{}}{lim}\underset{ϵ0}{lim}\left[\mathrm{Tr}_{\rho _2}\left(\mathrm{log}(\mathrm{\Delta }_{G_M,w_2}+ϵI)\right)\mathrm{Tr}_{\rho _1}\left(\mathrm{log}(\mathrm{\Delta }_{G_M,w_1}+ϵI)\right)\right]=0.$$

Let $`\nu `$ be a monotone coupling of $`\rho _1`$ and $`\rho _2`$. Since $`\mathrm{log}`$ is an operator monotone function on $`(0,\mathrm{})`$ with $`lim_{t0}t\mathrm{log}t=0`$, we may apply a result from \[AL:uni???\] to deduce that $`\mathrm{\Delta }_{G_M,w_1}=\mathrm{\Delta }_{G_M,w_2}`$ $`\nu `$-a.s., i.e., that $`\rho _1=\rho _2`$.

Remark 4.4. In case there is a unimodular monotone coupling $`\nu `$ (via marked graphs) of probability measures $`\rho \rho ^{}`$ on rooted infinite graphs that have finite expected degree, where $`\rho `$ is edge dominated by $`\rho ^{}`$, then one can prove an explicit lower bound for the difference $`𝐡(\rho ^{})𝐡(\rho )`$. As shown in \[AL:uni???\], there is then a sequence $`(G_n,G_n^{})`$ of pairs of finite connected graphs on the same vertex sets and with the edge set of $`G_n`$ contained in the edge set of $`G_n^{}`$ such that $`G_n`$ \[resp., $`G_n^{}`$\] has a random weak limit $`\rho `$ \[resp., $`\rho ^{}`$\] with the average degree of $`G_n^{}`$ tending to the $`\rho ^{}`$-expected degree of the root. A counting argument then shows that $`𝐡(\rho ^{})𝐡(\rho )c^2(\mathrm{log}2)/[d(d+1)^2]`$, where $`c:=\nu \left[(G,G^{},o);\mathrm{deg}_G^{}(o)\mathrm{deg}_G(o)\right]`$ and $`d:=\overline{\mathrm{deg}}(\rho ^{})`$.

Corollary 3.9 shows that $`𝐡(\rho )>\mathrm{}`$ as long as $`\rho `$ has finite expected degree. As an example where $`𝐡(\rho )<0`$, consider $`\rho `$ to be concentrated on the single rooted graph $`(N,0)`$. However, this is not possible in the unimodular case of unweighted graphs:

Proposition 4.5. If $`\rho `$ is a unimodular probability measure on rooted infinite (unweighted) graphs that has finite expected degree, then $`𝐡(\rho )0`$.

Proof. Under these hypotheses, \[AL:uni???\] establish that $`\rho `$ is the random weak limit of a sequence of finite connected graphs with bounded average degree. Thus, we may apply Theorem 3.3.

Naturally, we wish to know when the tree entropy is $`0`$.

Theorem 4.6. If $`\rho `$ is a unimodular probability measure on rooted infinite (unweighted) graphs that has finite expected degree, then $`𝐡(\rho )=0`$ iff $`\overline{\mathrm{deg}}(\rho )=2`$ iff $`\rho `$-a.s. $`G`$ is a locally finite tree with 1 or 2 ends.

Proof. The last equivalence is proved in \[AL:uni???\]. To prove the first equivalence, let $`G_n`$ be finite connected graphs whose random weak limit is $`\rho `$ and with bounded average degree. Let $`T_n`$ be a spanning tree of $`G_n`$. Since $`G_n`$ is a tight sequence, so is $`T_n`$. Therefore, by taking a subsequence if necessary, we may assume that $`T_n`$ has a random weak limit $`\rho _0`$. Clearly, $`\rho _0`$ is edge dominated by $`\rho `$ and $`𝐡(\rho _0)=0`$ (since $`\tau (T_n)=1`$). \[AL:uni???\] proved that $`\overline{\mathrm{deg}}(\rho _0)=2`$. Thus, $`\overline{\mathrm{deg}}(\rho )=2`$ iff $`\rho =\rho _0`$ iff $`𝐡(\rho )=𝐡(\rho _0)`$ by Theorem 4.3.

§5. Metric Entropy.

Suppose that $`G`$ is an infinite quasi-transitive amenable connected graph. Choose one element $`o_i`$ from each vertex orbit. It is shown in BLPS (1999), Proposition 3.6, that there is a probability measure $`\rho `$ on the set $`\{o_i\}`$ such that for any Følner sequence $`H_n`$, the relative frequency of vertices in $`H_n`$ that are in the same orbit as $`o_i`$ converges to $`\rho (o_i)`$. We call this measure $`\rho `$ the natural frequency distribution of $`G`$.

Theorem 5.1. Let $`G`$ be an infinite quasi-transitive amenable connected graph with natural frequency distribution $`\rho `$. Let $`G_n`$ be finite connected Følner subgraphs of $`G`$. Then

$$\underset{n\mathrm{}}{lim}\frac{1}{|𝖵(G_n)|}\mathrm{log}\tau (G_n)=\underset{x𝖵(G)}{}\rho (x)\mathrm{log}\mathrm{deg}_G(x)\underset{k1}{}\frac{1}{k}\underset{x𝖵(G)}{}\rho (x)p_k(x;G)=𝐡(G,\rho ).$$
$`(5.1)`$
If $`\mathrm{\Gamma }\mathrm{Aut}(G)`$ is a countable finitely generated group acting freely on $`𝖵(G)`$ with a finite number $`I`$ of orbits, then

$$𝐇(\mathrm{𝖶𝖲𝖥}_G,\mathrm{\Gamma })=I𝐡(G,\rho ).$$
$`(5.2)`$
Furthermore, the $`\mathrm{\Gamma }`$-entropy of any invariant measure on essential spanning forests of $`G`$ is at most $`I𝐡(G,\rho )`$.

We shall need several lemmas to prove Theorem 5.1.

Lemma 5.2. Let $`G`$ be an infinite quasi-transitive unimodular graph. If $`G`$ has 2 ends, then $`F`$ is a tree with exactly 2 ends $`\mathrm{𝖶𝖲𝖥}`$-a.s., while otherwise, for $`\mathrm{𝖶𝖲𝖥}`$-a.e. $`F`$, each component tree of $`F`$ has exactly one end.

Proof. \[MR92g:60014???\] established this one-endedness for $`G=Z^d`$ when $`2d4`$. BLPS (2001) proved this in the general case that $`G`$ is transitive (and unimodular). This latter proof is long, but not too hard to modify so as to apply to quasi-transitive graphs. The case where $`G`$ has 2 ends or is recurrent needs only a few simple modifications that we do not detail. The major changes needed in the transient case with other than 2 ends are as follows. Let $`\{o_i\}`$ be a set of representatives of the orbits of $`𝖵`$ and let $`w_i`$ be the reciprocal of the Haar measure of the stabilizer of $`o_i`$, where we normalize Haar measure so that $`_iw_i=1`$. (In the amenable case, we have $`w_i=\rho (o_i)`$ by BLPS (1999), Proposition 3.6.) Consider any $`\mathrm{Aut}(G)`$-invariant probability measure $`𝐏`$ on $`2^{𝖤(G)}`$. For any subgraph $`\omega `$ of $`G`$ and any vertex $`x`$, write $`D(x)`$ for the degree of $`x`$ in $`\omega `$. Let $`A_i`$ be the event that the component of $`o_i`$ in $`\omega `$ is infinite and $`p_{\mathrm{},i}:=𝐏[A_i]`$. Then according to Theorem 6.4 of BLPS (1999), we have

$$\underset{i}{}w_i𝐄[D(o_i);A_i]\underset{i}{}2w_ip_{\mathrm{},i}.$$
$`(5.3)`$
We may use this to prove an analogue of Theorem 7.2 in BLPS (1999), namely, that if some component of $`\omega `$ has at least 3 ends with positive probability, then strict inequality holds in (5.3). The next step is to combine the proof of Theorem 6.5 of BLPS (2001) with Corollary 3.5 of BLPS (1999) to show that when $`𝐏=\mathrm{𝖶𝖲𝖥}_G`$, we have $`_iw_i𝐄[D(o_i)]=2`$, so that equality holds in (5.3). Therefore, each tree has at most 2 ends $`\mathrm{𝖶𝖲𝖥}`$-a.s. The rest of the proof needs simple obvious modifications only, except for the crucial “trunk” lemma, i.e., Lemma 10.5 of BLPS (2001). Almost all of this proof can also be used word for word. The only significant change needed is that if $`o_i`$ is on the trunk, then the shift along the trunk should bring to $`o_i`$ the next vertex in the orbit of $`o_i`$ in the direction of the orientation of the trunk.

For our other lemmas, we shall find the following notation convenient. Given a finite subgraph $`H`$ of a graph $`G`$ and a configuration $`\omega `$ of $`𝖤(G)`$, let $`H(\omega )`$ denote the cylinder event consisting of those configurations of $`𝖤(G)`$ that agree with $`\omega `$ on $`𝖤(H)`$. Given also a configuration $`\omega `$ of $`𝖤(G)𝖤(H)`$, we define two finite graphs from certain vertex identifications on $`H`$: Write $`H\omega `$ for the graph obtained by identifying all vertices of $`H`$ that are connected to each other in the graph $`(𝖵(G),\omega )`$. Write $`H\omega `$ for the graph obtained by identifying all vertices of $`H`$ that are connected to each other in the graph $`(𝖵(G),\omega )`$ and by identifying all vertices of $`H`$ that belong to any infinite connected component in $`(𝖵(G),\omega )`$. Note that in $`H\omega `$, each finite component of $`(𝖵(G),\omega )`$ yields a separate identification, while the infinite components of $`(𝖵(G),\omega )`$ yield together one single identification.

The next lemma provides another justification for the adjective “uniform” in “wired uniform spanning forest”, similar to a Gibbs specification. However, it does not hold for all graphs.

Lemma 5.3. Let $`G`$ be an infinite quasi-transitive unimodular graph and let $`H`$ be a finite connected subgraph of $`G`$. If $`G`$ has 2 ends, then

$$\mathrm{𝖶𝖲𝖥}\left(H(F)\right|F\mathrm{}(𝖤𝖤(H)))=\tau (H\left(F\mathrm{}(𝖤𝖤(H))\right))^1\mathrm{𝖶𝖲𝖥}\text{-a.s.},$$

while otherwise,

$$\mathrm{𝖶𝖲𝖥}\left(H(F)\right|F\mathrm{}(𝖤𝖤(H)))=\tau (H\left(F\mathrm{}(𝖤𝖤(H))\right))^1\mathrm{𝖶𝖲𝖥}\text{-a.s.}$$

Proof. The case where $`G`$ has 2 ends is similar, though simpler, than the other case, so we give the details only for the case where $`G`$ has other than 2 ends. Let $`Z`$ be the event that each tree of $`F`$ has exactly one end. By Lemma 5.2, we have $`\mathrm{𝖶𝖲𝖥}(Z)=1`$.

Let $`B_R`$ denote the ball of radius $`R`$ about some fixed vertex of $`G`$. Choose $`R_H`$ so that $`HB_{R_H}`$. Let $`A_R`$ be the event that for all $`x,y_𝖵H`$ and $`z,w_𝖵B_R`$, if in $`F\mathrm{}\left(𝖤(B_R)𝖤(H)\right)`$

$`x`$ is connected to $`z`$,

$`y`$ is connected to $`w`$, and

$`x`$ is not connected to $`w`$,

then $`x`$ and $`y`$ are not connected in $`F\mathrm{}𝖤(H)`$. Thus, $`A_RA_{R+1}`$ for all $`RR_H`$ and

$$Z\underset{R}{}A_R,$$

whence $`lim_R\mathrm{}\mathrm{𝖶𝖲𝖥}(A_R)=1`$. Since

$$\mathrm{𝖶𝖲𝖥}(A_R)=\mathrm{𝖶𝖲𝖥}\left(A_R\right|F\mathrm{}(𝖤(B_R)𝖤(H)))d\mathrm{𝖶𝖲𝖥},$$

it follows that for all large $`R`$, we have

$$\mathrm{𝖶𝖲𝖥}(C_R)1\sqrt{1\mathrm{𝖶𝖲𝖥}(A_R)},$$

where

$$C_R:=\{F;\mathrm{𝖶𝖲𝖥}\left(A_R\right|F\mathrm{}(𝖤(B_R)𝖤(H)))1\sqrt{1\mathrm{𝖶𝖲𝖥}(A_R)}\}.$$

In particular, $`\mathrm{𝖶𝖲𝖥}(lim\; sup_R\mathrm{}C_R)=1`$.

By definition,

$$\mathrm{𝖶𝖲𝖥}\left(H(F)\right|F\mathrm{}(𝖤𝖤(H)))=\underset{R\mathrm{}}{lim}\mathrm{𝖶𝖲𝖥}\left(H(F)\right|F\mathrm{}(𝖤(B_R)𝖤(H)))\mathrm{𝖶𝖲𝖥}\text{-a.s.}$$

Fix a forest $`\omega Zlim\; sup_R\mathrm{}C_R`$ for which the limit above holds. Choose $`ϵ>0`$ arbitrarily small. Choose $`RR_H`$ so large that

$$|\mathrm{𝖶𝖲𝖥}\left(H(\omega )\right|\omega \mathrm{}(𝖤𝖤(H)))\mathrm{𝖶𝖲𝖥}\left(H(\omega )\right|\omega \mathrm{}(𝖤(B_R)𝖤(H)))|<ϵ,$$
$`(5.4)`$
that $`\omega C_R`$, that $`\sqrt{1\mathrm{𝖶𝖲𝖥}(A_R)}<ϵ`$, and that each vertex in $`_𝖵H`$ that is connected in $`\omega \mathrm{}\left(𝖤(B_R)𝖤(H)\right)`$ to $`_𝖵B_R`$ belongs to an infinite component in $`\omega \mathrm{}\left(𝖤𝖤(H)\right)`$. This last requirement, in combination with $`\omega Z`$, implies that $`\omega A_R`$. Consider the cylinder set

$$D:=\left(B_R𝖤(H)\right)(\omega )=\left\{F;F\mathrm{}\left(𝖤(B_R)𝖤(H)\right)=\omega \mathrm{}\left(𝖤(B_R)𝖤(H)\right)\right\}.$$

Let $`\mu _N`$ be the uniform spanning tree measure on $`B_N^{}`$. By definition,

$$\mathrm{𝖶𝖲𝖥}\left(H(\omega )\right|D)=\underset{N\mathrm{}}{lim}\mu _N\left(H(\omega )\right|D)$$

and

$$\mathrm{𝖶𝖲𝖥}(A_RD)=\underset{N\mathrm{}}{lim}\mu _N(A_RD).$$

Since $`\omega C_R`$ and $`\sqrt{1\mathrm{𝖶𝖲𝖥}(A_R)}<ϵ`$, we have $`\mathrm{𝖶𝖲𝖥}(A_RD)>1ϵ`$. Thus, we may choose $`N>R`$ so large that

$$|\mathrm{𝖶𝖲𝖥}\left(H(\omega )\right|D)\mu _N\left(H(\omega )\right|D)|<ϵ$$

and $`\mu _N(A_RD)>1ϵ`$. Since

$$\mu _N\left(H(\omega )\right|D)=\mu _N(A_RD)\mu _N\left(H(\omega )\right|A_RD)+\mu _N(A_R^cD)\mu _N\left(H(\omega )\right|A_R^cD),$$

we have

$$|\mu _N\left(H(\omega )\right|D)\mu _N\left(H(\omega )\right|A_RD)|<2ϵ.$$

Given $`A_RD`$, the configurations inside $`H`$ and outside $`B_R`$ are $`\mu _N`$-independent. Since $`\omega A_R`$, it follows that

$$\mu _N\left(H(\omega )\right|A_RD)=\tau (H\omega )^1,$$

and so

$$|\mathrm{𝖶𝖲𝖥}\left(H(\omega )\right|D)\tau (H\omega )^1|<3ϵ.$$

Therefore,

$$|\mathrm{𝖶𝖲𝖥}\left(H(\omega )\right|\omega \mathrm{}(𝖤𝖤(H)))\tau (H\omega )^1|<4ϵ$$

by (5.4). Since $`ϵ`$ is arbitrary and $`\omega `$ is an arbitrary element of a set of measure 1, the result follows.

Lemma 5.4. Let $`H`$ be a finite connected graph and $`W`$ be a subset of vertices of $`H`$. Let $`H^{}`$ be any graph obtained from $`H`$ by making certain identifications of the vertices in $`W`$ with each other. Write $`\alpha :=(|W|1)/|𝖤(H)|`$. Then

$$|\mathrm{log}\tau (H)\mathrm{log}\tau (H^{})||𝖤(H)|\left(\alpha \mathrm{log}\alpha (1\alpha )\mathrm{log}(1\alpha )\right).$$

Proof. Let $`\mu `$ be the uniform spanning tree measure on $`H`$ and $`\mu ^{}`$ the uniform spanning tree measure on $`H^{}`$. It follows from \[FedMih???\] that $`\mu `$ stochastically dominates $`\mu ^{}`$. By \[MR31:1693(author)???\]’s (\[MR31:1693(year)???\]) theorem, this means that there is a probability measure on pairs $`(T,T^{})`$ so that the law of $`T`$ is $`\mu `$, the law of $`T^{}`$ is $`\mu ^{}`$, and $`TT^{}`$ a.s. Now $`|𝖤(T)|=|𝖵(H)|1`$ and $`|𝖤(T^{})|=|𝖵(H^{})|1`$. We deduce that a.s.

$$|𝖤(T)𝖤(T^{})|=|𝖵(H)||𝖵(H^{})||W|1.$$

It now follows from Lemma 2.1 that

$$|𝐇(\mu )𝐇(\mu ^{})||𝖤(H)|\left(\alpha \mathrm{log}\alpha (1\alpha )\mathrm{log}(1\alpha )\right).$$

Since $`𝐇(\mu )=\mathrm{log}\tau (H)`$ and $`𝐇(\mu ^{})=\mathrm{log}\tau (H^{})`$, this is the same as the desired inequality.

Lemma 5.5. Let $`G`$ be an infinite quasi-transitive unimodular graph and $`H`$ be a finite connected subgraph of $`G`$. Write $`\alpha :=(|_𝖵H|1)/|𝖤(H)|`$. Then for $`\mathrm{𝖶𝖲𝖥}`$-a.e. $`F`$,

$$|\mathrm{log}\mathrm{𝖶𝖲𝖥}\left(H(F)\right)\mathrm{log}\tau (H)^1||𝖤(H)|\left(\alpha \mathrm{log}\alpha (1\alpha )\mathrm{log}(1\alpha )\right).$$

Proof. Write $`\beta :=\alpha ^\alpha (1\alpha )^{(1\alpha )}`$. According to Lemma 5.4, we have $`\tau (H^{})^1I_H`$, where

$$I_H:=[\tau (H)^1\beta ^{|𝖤(H)|},\tau (H)^1\beta ^{|𝖤(H)|}]$$

and $`H^{}:=H\left(F\mathrm{}\left(𝖤𝖤(H)\right)\right)`$ if $`G`$ has 2 ends, while $`H^{}:=H\left(F\mathrm{}\left(𝖤𝖤(H)\right)\right)`$ otherwise. Combining the preceding relation with Lemma 5.3, we obtain

$$\mathrm{𝖶𝖲𝖥}\left(H(F)\right)=𝐄\left[\mathrm{𝖶𝖲𝖥}\left(H(F)\right|F\mathrm{}(𝖤𝖤(H)))\right]I_H$$

a.s. This is the same as the desired inequality.

Lemma 5.6. Let $`H`$ be a finite connected graph and $`W`$ be a subset of vertices of $`H`$. Let $`\tau _\mathrm{e}(H,W)`$ be the number of spanning forests of $`H`$ such that each tree contains at least one vertex of $`W`$. Write $`\alpha :=(|W|1)/|𝖤(H)|`$. Then

$$\mathrm{log}\tau _\mathrm{e}(H,W)\mathrm{log}\tau (H)+|𝖤(H)|\left(\alpha \mathrm{log}\alpha (1\alpha )\mathrm{log}(1\alpha )\right).$$

Proof. Let $`\mu `$ be the uniform measure on spanning forests of $`H`$ such that each tree contains at least one vertex of $`W`$. Let $`\nu `$ be obtained from $`\mu `$ by choosing a spanning forest $`F`$ with distribution $`\mu `$ and then randomly adding to $`F`$ enough edges of $`H`$ so that a spanning tree of $`H`$ results. By Lemma 2.1, we have

$$|𝐇(\mu )𝐇(\nu )||𝖤(H)|\left(\alpha \mathrm{log}\alpha (1\alpha )\mathrm{log}(1\alpha )\right)$$

since at most $`|W|1`$ edges are added. Since $`𝐇(\mu )=\mathrm{log}\tau _\mathrm{e}(H,W)`$ and $`𝐇(\nu )\mathrm{log}\tau (H)`$, the desired inequality follows.

Proof of Theorem 5.1. We first prove that (5.1) holds. By definition of $`\rho `$, the graphs $`G_n`$ have a random weak limit $`(G,\rho )`$. Thus, (5.1) is a consequence of Theorem 3.3.

We next show (5.2). Choose a ball $`B_R(o)`$ of vertices and edges such that $`\mathrm{\Gamma }B_R(o)=G`$. Let

$$\mathrm{\Gamma }_n:=\{\gamma \mathrm{\Gamma };\gamma B_R(o)G_n\mathrm{}\}$$

and put

$$G_n^{}:=\mathrm{\Gamma }_nB_R(o).$$

Since $`G_n`$ is a Følner sequence in $`G`$, it follows that $`\mathrm{\Gamma }_n`$ is a Følner sequence in $`\mathrm{\Gamma }`$. Therefore,

$$𝐇(\mathrm{𝖶𝖲𝖥},\mathrm{\Gamma })=\underset{n\mathrm{}}{lim}|\mathrm{\Gamma }_n|^1\mathrm{log}\mathrm{𝖶𝖲𝖥}\left(G_n^{}(F)\right)$$

in $`L^1(\mathrm{𝖶𝖲𝖥})`$ by the generalized Shannon-McMillan Theorem of \[MR52:14232???\]. Now

$$\underset{n\mathrm{}}{lim}|𝖵(G_n^{})|/|\mathrm{\Gamma }_n|=I$$

since $`\mathrm{\Gamma }`$ acts freely on $`𝖵`$. Hence

$$𝐇(\mathrm{𝖶𝖲𝖥},\mathrm{\Gamma })=\underset{n\mathrm{}}{lim}I|𝖵(G_n^{})|^1\mathrm{log}\mathrm{𝖶𝖲𝖥}\left(G_n^{}(F)\right)$$
$`(5.5)`$
in $`L^1(\mathrm{𝖶𝖲𝖥})`$. As we recalled in Section 2, every quasi-transitive amenable graph is unimodular. The result now follows from Lemma 5.5 in conjunction with (5.5).

We finally show that no measure $`\mu `$ on essential spanning forests of $`G`$ has larger entropy. Using some of the same reasoning as above, we have that

$$𝐇(\mu ,\mathrm{\Gamma })=\underset{n\mathrm{}}{lim}|\mathrm{\Gamma }_n|^1𝐇(\mu \mathrm{}G_n^{}).$$

Because $`\mu `$ is concentrated on essential spanning forests, the number of elements of the partition generated by $`G_n^{}`$ that have positive $`\mu `$-measure is at most $`\tau _\mathrm{e}(G_n^{},_𝖵G_n^{})`$, whence $`𝐇(\mu \mathrm{}G_n^{})\mathrm{log}\tau _\mathrm{e}(G_n^{},_𝖵G_n^{})`$. We may apply Lemma 5.6 to obtain the desired conclusion.

Acknowledgements. I am grateful to Wolfgang Woess, Thierry Coulhon, Ben Morris, Yuval Peres, and Scott Sheffield for useful discussions and references. Thanks are due to Benny Sudakov for asking about the asymptotics for graphs whose degree tends to infinity.

REFERENCES

Aldous, D. (1998). Tree-valued Markov chains and Poisson-Galton-Watson distributions. In Aldous, D. and Propp, J., editors, Microsurveys in Discrete Probability, volume 41 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 1–20. Amer. Math. Soc., Providence, RI. Papers from the workshop held as part of the Dimacs Special Year on Discrete Probability in Princeton, NJ, June 2–6, 1997.

Aldous, D.J. and Lyons, R. (2004). Processes on unimodular random networks. In preparation.

Aldous, D.J. and Steele, J.M. (2004). The objective method: probabilistic combinatorial optimization and local weak convergence. In Kesten, H., editor, Probability on discrete structures, volume 110 of Encyclopaedia Math. Sci., pages 1–72. Springer, Berlin. Probability Theory, 1.

Barlow, M., Coulhon, T., and Grigor’yan, A. (2001). Manifolds and graphs with slow heat kernel decay. Invent. Math. 144, 609–649.

Benjamini, I., Lyons, R., Peres, Y., and Schramm, O. (1999). Group-invariant percolation on graphs. Geom. Funct. Anal. 9, 29–66.

Benjamini, I., Lyons, R., Peres, Y., and Schramm, O. (2001). Uniform spanning forests. Ann. Probab. 29, 1–65.

Benjamini, I. and Schramm, O. (2001). Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6, no. 23, 13 pp. (electronic).

Bhatia, R. (1997). Matrix Analysis, volume 169 of Graduate Texts in Mathematics. Springer-Verlag, New York.

Bollobás, B. (1998). Modern Graph Theory, volume 184 of Graduate Texts in Mathematics. Springer-Verlag, New York.

Bollobás, B. (2001). Random Graphs, volume 73 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, second edition.

Burton, R.M. and Pemantle, R. (1993). Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances. Ann. Probab. 21, 1329–1371.

Carlen, E.A., Kusuoka, S., and Stroock, D.W. (1987). Upper bounds for symmetric Markov transition functions. Ann. Inst. H. Poincaré Probab. Statist. 23, 245–287.

Chung, F.R.K. (1996). Laplacians of graphs and Cheeger’s inequalities. In Miklós, D., Sós, V.T., and Szőnyi, T., editors, Combinatorics, Paul Erdős is Eighty. Vol. 2, volume 2 of Bolyai Soc. Math. Stud., pages 157–172. János Bolyai Math. Soc., Budapest. Papers from the International Conference on Combinatorics held at Keszthely, July 19–24, 1993.

Coulhon, T. (2000). Random walks and geometry on infinite graphs. In Ambrosio, L. and Cassano, F.S., editors, Lecture Notes on Analysis on Metric Spaces, Trento, C.I.R.M., 1999, pages 5–30. Scuola Normale Superiore di Pisa.

Dudley, R.M. (1989). Real Analysis and Probability. The Wadsworth & Brooks/Cole Mathematics Series. Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, CA.

Feder, T. and Mihail, M. (1992). Balanced matroids. In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, pages 26–38, New York. Association for Computing Machinery (ACM). Held in Victoria, BC, Canada.

Felker, J.L. and Lyons, R. (2003). High-precision entropy values for spanning trees in lattices. J. Phys. A 36, 8361–8365.

Fuglede, B. and Kadison, R.V. (1952). Determinant theory in finite factors. Ann. of Math. (2) 55, 520–530.

Godsil, C. and Royle, G. (2001). Algebraic Graph Theory, volume 207 of Graduate Texts in Mathematics. Springer-Verlag, New York.

Grenander, U. and Szegő, G. (1984). Toeplitz Forms and Their Applications. Chelsea Publishing Co., New York, second edition.

Grimmett, G.R. (1980/81). Random labelled trees and their branching networks. J. Austral. Math. Soc. Ser. A 30, 229–237.

Häggström, O. (1995). Random-cluster measures and uniform spanning trees. Stochastic Process. Appl. 59, 267–275.

Häggström, O. (1998). Uniform and minimal essential spanning forests on trees. Random Structures Algorithms 12, 27–50.

Helson, H. and Lowdenslager, D. (1958). Prediction theory and Fourier series in several variables. Acta Math. 99, 165–202.

Kesten, H. (1959). Symmetric random walks on groups. Trans. Amer. Math. Soc. 92, 336–354.

Kieffer, J.C. (1975). A generalized Shannon-McMillan theorem for the action of an amenable group on a probability space. Ann. Probab. 3, 1031–1037.

Lind, D. and Tuncel, S. (2001). A spanning tree invariant for Markov shifts. In Marcus, B. and Rosenthal, J., editors, Codes, Systems, and Graphical Models (Minneapolis, MN, 1999), volume 123 of IMA Vol. Math. Appl., pages 487–497. Springer, New York. Proceedings of the IMA Workshop held in Minneapolis, MN, August 2–13, 1999.

Löwner, K. (1934). Über monotone Matrixfunktionen. Math. Z. 38, 177–216.

Lyons, R. (1998). A bird’s-eye view of uniform spanning trees and forests. In Aldous, D. and Propp, J., editors, Microsurveys in Discrete Probability, volume 41 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 135–162. Amer. Math. Soc., Providence, RI. Papers from the workshop held as part of the Dimacs Special Year on Discrete Probability in Princeton, NJ, June 2–6, 1997.

Lyons, R. and Steif, J.E. (2003). Stationary determinantal processes: Phase multiplicity, Bernoullicity, entropy, and domination. Duke Math. J. 120, 515–575.

McKay, B.D. (1981). Spanning trees in random regular graphs. In Cadogan, C.C., editor, Proceedings of the Third Caribbean Conference on Combinatorics and Computing, pages 139–143, Cave Hill Campus, Barbados. Univ. West Indies. Held at the University of the West Indies, Bridgetown, January 5–8, 1981.

McKay, B.D. (1983). Spanning trees in regular graphs. European J. Combin. 4, 149–160.

Morris, B. and Peres, Y. (2004). Evolving sets, mixing and heat kernel bounds. Probab. Theory Related Fields. To appear.

Ornstein, D.S. and Weiss, B. (1987). Entropy and isomorphism theorems for actions of amenable groups. J. Analyse Math. 48, 1–141.

Pemantle, R. (1991). Choosing a spanning tree for the integer lattice uniformly. Ann. Probab. 19, 1559–1574.

Runge, F. and Sachs, H. (1974). Berechnung der Anzahl der Gerüste von Graphen und Hypergraphen mittels deren Spektren. In Papers presented at the Fifth Balkan Mathematical Congress, volume 4, pages 529–536. Beogradski Izdavačko-Grafički Zavod, Belgrade. Held in Belgrade, 25–30. 06. 1974, Math. Balkanica 4 (1974).

Saloff-Coste, L. (1997). Lectures on finite Markov chains. In Lectures on Probability Theory and Statistics (Saint-Flour, 1996), volume 1665 of Lecture Notes in Math., pages 301–413. Springer, Berlin. Lectures from the 26th Summer School on Probability Theory held in Saint-Flour, August 19–September 4, 1996, Edited by P. Bernard.

Salvatori, M. (1992). On the norms of group-invariant transition operators on graphs. J. Theoret. Probab. 5, 563–576.

Sheffield, S. (2003). Random Surfaces: Large Deviations Principles and Gradient Gibbs Measure Classifications. Ph.D. thesis, Stanford University.

Shrock, R. and Wu, F.Y. (2000). Spanning trees on graphs and lattices in $`d`$ dimensions. J. Phys. A 33, 3881–3902.

Soardi, P.M. and Woess, W. (1990). Amenability, unimodularity, and the spectral radius of random walks on infinite graphs. Math. Z. 205, 471–486.

Strassen, V. (1965). The existence of probability measures with given marginals. Ann. Math. Statist 36, 423–439.

Woess, W. (1984). A random walk on free products of finite groups. In Heyer, H., editor, Probability Measures on Groups, VII (Oberwolfach, 1983), volume 1064 of Lecture Notes in Math., pages 467–470. Springer, Berlin. Proceedings of the seventh conference held in Oberwolfach, April 24–30, 1983.

Woess, W. (2000). Random Walks on Infinite Graphs and Groups, volume 138 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge.

Department of Mathematics, Indiana University, Bloomington, IN 47405-5701

rdlyons@indiana.edu

http://mypage.iu.edu/~rdlyons/


format: text

text:
# References

Comment on “Highly Extended Image States around Nanotubes”

In their Letter granger , Granger et.al. have discussed the image states around carbon nanotubes. To do that, they derive the interaction potential $`V(\rho )=\frac{2q^2}{\pi a}\underset{n=1,3,5,\mathrm{}}{}li[(\frac{a}{\rho })^n]`$ between a nanotube of radius $`a`$ and an electron at a distance $`\rho `$ from its axis. Then, they formally introduce the effective interaction $`V_{eff}(\rho )=V(\rho )+\frac{l^2\frac{1}{4}}{2\mu \rho }`$ and give the transverse Schrödinger equation

$$\{\frac{d^2}{d\rho ^2}+2\mu [E_{nl}V_{eff}(\rho )\}\psi _{nl}(\rho )=0.$$
(1)
In our viewpoint, the interaction potential $`U`$ between a nanotube and an electron must be the function of $`\rho `$, $`\varphi `$ and $`z`$ in terms of the lattice structure of the carbon nanotube. Here $`\rho `$, $`\varphi `$ and $`z`$ are the components of cylindrical coordinate system whose $`z`$-axis is the tube axis. Besides, $`U`$ satisfies $`U(\rho ,\varphi +2\pi j_1/N,z+j_1\tau +j_2T)=U(\rho ,\varphi ,z)`$ because the nanotube’s symmetrysaito ; tzc . Here $`j_1,j_2`$ are integer numbers, and $`N,\tau ,T`$ are characteristic quantities of the nanotube, e.g., for (10,10) nanotube, $`N=20,\tau =1.23\text{Å},T=2\tau `$. When $`\rho a`$, it seems rational to approximate $`U(\rho ,\varphi ,z)V(\rho )`$. But, there is no reason to think $`U(\rho ,\varphi ,z)V(\rho )`$ when $`\rho a`$. Therefore, we believe that the energies $`E_{nl}`$ obtained from Eq.(1) are merely valid for $`n,l1`$.

If we know $`U(\rho ,\varphi ,z)`$, we can calculate the energies of image states in principle. From the periodical structure of $`U`$, we can obtain the general Bloch’s theoremtzc

$$\begin{array}{c}H\phi (\rho ,\varphi ,z)=E\phi (\rho ,\varphi ,z),\hfill \\ \phi (\rho ,\varphi +\frac{2\pi j_1}{N},z+j_1\tau +j_2T)=e^{i[\frac{2\pi lj_1}{N}+\kappa (j_1\tau +j_2T)]}\phi (\rho ,\varphi ,z),\hfill \end{array}$$
(2)
where $`l=0,1,\mathrm{},N1`$ because of the periodical boundary condition along circumference and $`0k<2\pi /T`$. Adopting the thought of plane wave expansions callaway , $`\phi _{nl\kappa }(\rho ,\varphi ,z)=\underset{j_1j_2}{}C_{j_1j_2}\chi _{nl\kappa }(\rho )e^{i[(l+j_1Nj_2N\tau /T)\varphi +(\kappa +2\pi j_2/T)z]}`$, we substitute it in $`H\phi _{nl\kappa }(\rho ,\varphi ,z)=E_{nl\kappa }\phi (\rho ,\varphi ,z)`$ and obtain the transverse Schrödinger equation

$$det[(_{m_1m_2j_1j_2}E_{nl\kappa }\delta _{j_1m_1}\delta _{j_2m_2})\chi _{nl\kappa }(\rho )]=0,$$
(3)
where $`_{j_1j_2m_1m_2}=𝒯_{j_1j_2}\delta _{j_1m_1}\delta _{j_2m_2}+𝒰_{j_1j_2m_1m_2}`$, $`𝒯_{j_1j_2}=\frac{\mathrm{}^2}{2\mu }[\frac{d^2}{d\rho ^2}+\frac{d}{\rho d\rho }\frac{(l+j_1N\frac{j_2N\tau }{T})^2}{\rho ^2}(\kappa +\frac{2\pi j_2}{T})^2]`$, and $`𝒰_{j_1j_2m_1m_2}=\frac{N}{2\pi T}_0^{2\pi }𝑑\varphi _0^T𝑑zU(\rho ,\varphi ,z)e^{i[(j_1m_1)\frac{(j_2m_2)\tau }{T}]N\varphi +\frac{i2\pi (j_2m_2)z}{T}}`$.

Hence, the key problem is to determine the potential $`U(\rho ,\varphi ,z)`$. It is an extremely difficult project beyond this comment.

Z. C. Tu1 and Z. C. Ou-Yang1,2
1Institute of Theoretical Physics
The Chinese Academy of Sciences
P.O.Box 2735 Beijing 100080, China
2Center for Advanced Study
Tsinghua University, Beijing 100084, China

PACS numbers: 61.46.+w, 34.60.+z, 34.80.Lx, 36.10. Ck