The local limit of uniform spanning trees

Abstract

We show that the local limit of the uniform spanning tree on any finite, simple, connected, regular graph sequence with degree tending to $\infty$ is the Poisson(1) branching process conditioned to survive forever. An extension to “almost” regular graphs and a quenched version are also given.

1 Introduction

A spanning tree T of a finite connected graph G is a subset of edges spanning a connected graph, containing no cycles, and such that every vertex of G is incident to some edge of T. The uniform spanning tree (UST) of such a graph G is a uniformly drawn tree from the finite set of spanning trees of G. In this paper we study the local limit of the UST on regular connected graphs with large degree. This limit, defined by Benjamini and Schramm [3], is an infinite random rooted tree which encodes the local structure of the UST viewed from a typical vertex, see further definitions and discussion below.

Theorem 1.1

Let $\{G_n\}$ be a sequence of finite, simple, connected, regular graphs with degree $d(n)\rightarrow \infty$. Then the local limit of the UST on $G_n$ is the Poisson(1) branching process conditioned to survive forever.

The large scale geometry of the UST on regular graphs of high degree may behave very differently depending on the underlying graph, see Sect. 7.1. It is therefore surprising that from the local point of view the UST’s behavior is universal.

Let us present an equivalent yet more concrete version of this theorem giving precisely the probability of seeing a fixed rooted tree in a ball of radius r around a random vertex. Let T be a finite rooted tree of height $r \ge 1$, that is, the maximal graph distance between the root and a vertex of T equals r. Denote by $T_r$ the set of vertices of T at graph distance precisely r from the root and by $\mathrm {Stab}_T$ the set of graph automorphisms of T that preserve the root. Given a tree $\Gamma$, an integer $r \ge 0$ and a vertex v we write $B_{\Gamma }(v,r)$ for the induced rooted subtree of $\Gamma$ on the vertices that are at graph distance at most r from v in $\Gamma$. Theorem 1.1 can be now restated as follows.

Theorem 1.2

Let $\{G_n\}$ be a sequence of finite, simple, connected, regular graphs with degree $d(n)\rightarrow \infty$. Let $\Gamma _n$ be a UST of $G_n$ and X a uniformly chosen vertex of $G_n$. Then for any fixed rooted tree T of height $r \ge 1$ we have that

$$\begin{aligned} \lim _{n\rightarrow \infty } {{\,\mathrm{{\mathbb {P}}}\,}}( B_{\Gamma _n}(X, r) \cong T) = \frac{|T_r| e^{-|V(T)|+|T_r|}}{|\mathrm {Stab}_T|} , \end{aligned}$$

where $\cong$ means rooted graph isomorphism.

We also provide a stronger version of Theorem 1.2 (Theorem 1.4) in which the assumption of regularity can be weakened to “almost regular” graphs of high degree which include small perturbations of regular graphs and graphs in which the degree of most vertices are almost equal. Furthermore, in this more general setting we obtain a quenched version of Theorem 1.2 (Theorem 1.5) showing that with probability $1-o(1)$ the number of appearances of a fixed rooted tree T in the UST $\Gamma _n$ is

$$\begin{aligned} (1+o(1)) \frac{|V(G_n)||T_r| e^{-|V(T)|+|T_r|}}{|\mathrm {Stab}_T|} . \end{aligned}$$

For instance, with high probability the density of leaves in $\Gamma _n$ is $(1+o(1))e^{-1}$ and the density of leaves attached to a vertex of degree k is $(1+o(1))e^{-2}/(k-1)!$. These extensions are presented in Sect. 1.3.

When G is the complete graph on n vertices the conclusion of Theorem 1.1 was established in the pioneering work of Grimmett [6]. The local limit of USTs on dense graphs (i.e., when the number of edges is proportional to the number of vertices squared) was recently investigated in [7] where it was shown to be a certain multi-type branching process that can be described explicitly via the limiting graphon. The assumption of density of the graph is used in [7] to apply partition theorems in the spirit of Szemerédi’s Lemma and to use “graph-limit” techniques to explicitly describe the local limit. These techniques are unavailable in the setting of this paper where the degree tends to infinity arbitrarily slow.

We remark that Theorem 1.1 recovers the result of [7] in the special case when the underlying graph is dense and regular (or close to regular). We also remark that regularity is a necessary assumption for for Theorem 1.1. Indeed, if G is the complete bipartite graph with n/3 and 2n/3 vertices on each side, respectively, then the local limit of the UST is a branching process (conditioned to survive) in which the progeny distribution alternates between Poisson(1/2) and Poisson(2), see [7].

In the rest of this section we formally define the notion of local limits (Sect. 1.1), discuss the Poisson(1) Galton–Watson tree conditioned to survive and show that Theorem 1.1 follows from Theorem 1.2 (Sect. 1.2), present the most general versions of our main theorems as described above (Sect. 1.3) and close with a brief summary of our notation (Sect. 1.4).

1.1 Local limits

The local limit of finite graphs was first defined in the seminal paper of Benjamini and Schramm [3], see also [1] for further background.

We denote by ${\mathcal {G}}_\bullet$ the space of all locally finite rooted graphs viewed up to root-preserving graph isomorphisms. In other words, the elements of ${\mathcal {G}}_\bullet$ are pairs $(G,\rho )$ where G is a graph and $\rho$ is a vertex of it, and two elements $(G_1,\rho _1), (G_2,\rho _2)$ are considered equivalent if there is a graph automorphism $\varphi :V(G_1)\rightarrow V(G_2)$ for which $\varphi (\rho _1)=\rho _2$. For a pair $(G,\rho )$ and an integer $r \ge 0$ we write $B_G(\rho ,r)$ for the induced graph of G on the vertex set which is of graph distance at most r from $\rho$.

We endow ${\mathcal {G}}_\bullet$ with a natural metric: the distance between $(G_1,\rho _1)$ and $(G_2,\rho _2)$ is $2^{-R}$ where R is the maximal integer such that there is a root-preserving isomorphism between $B_{G_1}(\rho _1,R)$ and $B_{G_2}(\rho _2,R)$; possibly $R=\infty$. We consider the Borel $\sigma$-algebra on this space and remark that with this metric ${\mathcal {G}}_\bullet$ is a polish space, hence we can discuss convergence in distribution on it (see [1]).

We say that a law of a random element $(G,\rho )$ of ${\mathcal {G}}_\bullet$ is the local limit of a sequence of (possibly random) finite graphs $G_n$ if for any integer $r\ge 0$ the random rooted graphs $B_{G_n}(\rho _n,r)$ converge in distribution to $B_{G}(\rho ,r)$, where $\rho _n$ is a uniformly drawn random vertex of $G_n$ that is drawn independently conditioned on $G_n$.

1.2 Poisson Galton–Watson trees

Let us now describe the local limit of Theorem 1.1. The Poisson(1) Galton–Watson tree conditioned to survive is defined as the local limit as $n\rightarrow \infty$ of a random rooted tree drawn according to a Poisson(1) Galton–Watson tree conditioned to survive n generations. It is classical (see [10]) that this limit exists and can be drawn directly by taking an infinite path starting from the root vertex and hanging a Poisson(1) unconditional Galton–Watson tree on each vertex of the path; however, we will not use this fact in this paper.

Proof of heorem 1.1

given Theorem 1.2. Let $(\Gamma ,\rho )$ be an instance of the Poisson(1) Galton–Watson tree conditioned to survive and let T be a finite rooted tree of height $r\ge 1$. Our goal is to prove that

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}( B_\Gamma (\rho ,r)\cong T) = {|T_r| e^{-|V(T)|+|T_r|} \over |\mathrm {Stab}_T|} . \end{aligned}$$

(1)

Denote by $\Gamma ^u$ an instance of an unconditional Poisson(1) branching process. We will prove that

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}( B_{\Gamma ^u}(\rho ,r) \cong T ) = {e^{-|V(T)| + |T_r|}\over |\mathrm {Stab}_T|} , \end{aligned}$$

(2)

which implies (1) by the following argument. Let $p_n$ denote the probability that $\Gamma ^u$ survives n generations. It is well known (see [10, Theorem C]) that $p_n={2 +o(1) \over n}$. Thus, the probability that $B_{\Gamma ^u}(\rho ,r) \cong T$ and $\Gamma ^u$ survives n generations by (2) is just

$$\begin{aligned} {e^{-|V(T)| + |T_r|}\over |\mathrm {Stab}_T|} \big ( 1 - (1-p_{n-r})^{|T_r|} \big ) = (1+o(1)) {e^{-|V(T)| + |T_r|}\over |\mathrm {Stab}_T|} |T_r| p_n . \end{aligned}$$

Hence, if we condition on the event that $\Gamma ^u$ survives n generations and take $n\rightarrow \infty$ we get precisely (1).

We prove (2) by induction on r. When $r=1$ we have that $\mathrm {Stab}_T=k!$ where k is the degree of the root of T and (2) follows. Assume now that $r \ge 2$ and let k be again the degree of the root of T and call its children $\{u_1,\ldots , u_k\}$. For $1 \le i \le k$ write $T_{u_i}$ for the subtree of T induced on all the descendants of $u_i$ (that is, all the vertices of T for which the unique path to $u_i$ does not visit the root of T). We view $T_{u_i}$ as a tree rooted at $u_i$.

We put an equivalence relation on $\{u_1,\ldots , u_k\}$ by declaring $u_i$ equivalent to $u_j$ if and only if there exists a root-preserving automorphism between $T_{u_i}$ and $T_{u_j}$. Let $\ell \le k$ denote the number of equivalence classes and put $k_t$ for the number of elements in the tth equivalence class, where $1 \le t \le \ell$, so that $k=k_1 + \cdots + k_\ell$. For $1 \le t\le \ell$ we also denote by $T^{(t)}$ the rooted tree $T_{u_i}$ where $u_i$ is a representative of the tth equivalence class. Since T is of height r at least one of the $T^{(t)}$’s must be at height $r-1$ and all others have height at most $r-1$. A moment’s reflection shows that

$$\begin{aligned} |\mathrm {Stab}_T| = \prod _{t=1}^{\ell } k_t! \prod _{i=1}^k |\mathrm {Stab}_{T_{u_i}}| = \prod _{t=1}^{\ell }k_t! |\mathrm {Stab}_{T^{(t)}}|^{k_t} . \end{aligned}$$

(3)

Now, for the event $B_{\Gamma ^u}(\rho ,r) \cong T$ to occur, we must first have that the root of $\Gamma ^u$ has k children (with probability $e^{-1}/k!$) and that there is a partition of the k children of the root into $\ell$ subsets of sizes $\{k_t\}_{t=1}^\ell$ so that if a child of the root is at the tth set, the $r-1$ generations of the branching process emanating from this child is isomorphic to $T^{(t)}$. Thus, by the induction hypothesis we have that

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}(B_{\Gamma ^u}(\rho ,r) \cong T ) = {e^{-1} \over k!} {k \atopwithdelims ()k_1, k_2,\ldots , k_t} \prod _{t=1}^\ell \Big [ {e^{-|V(T^{(t)})|+ |T^{(t)}_{r-1}|} \over |\mathrm {Stab}_{T^{(t)}}|} \Big ]^{k_t} . \end{aligned}$$

Since $|V(T)|=1+\sum _{t=1}^\ell k_t |V(T^{(t)})|$ and $|T_r|=\sum _{t=1}^\ell k_t |T^{(t)}_{r-1}|$ and by (3) we get that (2) holds, concluding our proof. $\square$

1.3 Extensions

The assumption of regularity in Theorems 1.1 and  1.2 can often be very restrictive. For instance, the removal of a single edge from the graph violates the assumptions though it is intuitively clear that the conclusion of the theorems will not be altered. Moreover, the proof of Theorem 1.5, even in the regular case, requires an extended version of Theorem 1.2 in which the graphs involved are “close” to being regular. For these two reasons we now state this extension.

Definition 1.3

A sequence of finite, simple connected graphs $\{G_n\}$ is called high degree almost regular if there exists some $d(n)\rightarrow \infty$ such that

• (1) At least $(1-o(1))|V(G_n)|$ of the vertices of $G_n$ have degree $(1\pm o(1))d(n)$, and,

• (2) The sum of degrees in $G_n$ is $(1\pm o(1))d(n)|V(G_n)|$.

It is immediately deduced from this definition that the total variation distance between a uniformly chosen vertex and a vertex drawn according to the stationary distribution is o(1), indeed,

$$\begin{aligned} \sum _{v} \Big | {\deg (v) \over \sum _v \deg (v)} - {1 \over n} \Big | = o(1) . \end{aligned}$$

(4)

We comment that it is straightforward to see that if the average degree of the graphs tends to infinity, then (4) in fact implies that the graph sequence is high degree almost regular. We will not use this direction in our proof though.

Theorem 1.4

Let $\{G_n\}$ be a sequence of high degree almost regular graphs. Then the conclusions of Theorems 1.1 and 1.2 hold.

Lastly, the following gives the quenched version of Theorem 1.4

Theorem 1.5

Let $\{G_n\}$ be a sequence of high degree almost regular graphs. Let $\Gamma _n$ be a UST of $G_n$ and T be a fixed rooted tree of height $r\ge 1$. Denote by $Y_n(T)$ the number of vertices v of $G_n$ satisfying $B_{\Gamma _n}(v,r) \cong T$. Then with probability tending to 1 as $n\rightarrow \infty$ we have that

$$\begin{aligned} Y_n(T) = (1+o(1)) \frac{|V(G_n)| |T_r| e^{-|V(T)|+|T_r|}}{|\mathrm {Stab}_T|} . \end{aligned}$$

1.4 Notation

• Given a graph G we write V(G) and E(G) for its vertex and edge set, respectively.

• For an integer $k\ge 1$ we write [k] for $\{1,\ldots , k\}$.

• We write $\deg (u)$ for the degree of a vertex u.

• For vertices $u,v\in V(G)$ we write $u\sim v$ if there is an edge between them.

• For two positive sequences $\{a_n\}, \{b_n\}$ we write $a_n = O(b_n)$ when there exists a constant C such that $a_n \le C b_n$ for all n, and $a_n = o(b_n)$ when $a_n/b_n$ tends to 0.

2 Preliminaries

2.1 Random walks and electric networks

We give here a brief review of the theory of electric networks and refer the reader to [11, Chapter 2] or [13, Chapter 2] for more details.

A network is a connected graph G equipped with positive edge weights c(u, v) for any edge $(u,v)\in E(G)$. We write $\pi (v) = \sum _{u : u \sim v} c(u,v)$, where possibly $u=v$ if there is a loop at v. The network random walk on the network is a reversible Markov chain $\{X_t\}_{t=0}^\infty$ on V(G) with transition probabilities

$$\begin{aligned} p(u,v) = {c(u,v) \over \pi (u)} . \end{aligned}$$

We write ${{\,\mathrm{{\mathbb {P}}}\,}}_u(\cdot )$ for the probability measure of the chain conditioned on $X_0=u$ and ${{\,\mathrm{{\mathbb {E}}}\,}}_u$ for the corresponding expectation. We denote by $\tau _u$ and $\tau ^+_u$ the stopping times

$$\begin{aligned} \tau _u = \min \{ t \ge 0 : X_t = u\} \qquad \tau ^+_u = \min \{ t \ge 1 : X_t = u\} , \end{aligned}$$

which are of course equal unless $X_0=u$.

The effective resistance between two vertices u, v of the network is the voltage difference between u and v when unit current flows from u to v. We will not use this definition directly but rather a probabilistic interpretation of it which can serve as its definition. We define the effective resistance between u and v in the network G by

$$\begin{aligned} R_\mathrm {eff}(u \leftrightarrow v ; G) = {1 \over \pi (u) {{\,\mathrm{{\mathbb {P}}}\,}}_u(\tau _v < \tau ^+_u) } . \end{aligned}$$

(5)

We often write $R_\mathrm {eff}(u \leftrightarrow v)$ when the underlying network is evident from the context. When $A\subset V(G)$ we write $R_\mathrm {eff}(u\leftrightarrow A)$ for the electric resistance between u and A in the graph obtained from G by identifying the vertices of A and keeping all edges.

2.1.1 Nash–Williams inequality

The following is useful method of bounding the resistance from below and is due to Nash–Williams [14]. We say that a subset of edges of the network separates the vertices a and z if every path from a to z uses at least one edge of the subset. If $\Pi _1, \ldots , \Pi _n$ are disjoint subsets of edges separating a and z, then

$$\begin{aligned} R_\mathrm {eff}(a \leftrightarrow z) \ge \sum _{i=1}^n \Big ( \sum _{e \in \Pi _i} c_e \Big )^{-1} , \end{aligned}$$

see [11, Chapter 2.5]. An immediate application of this inequality is that

$$\begin{aligned} R_\mathrm {eff}(u \leftrightarrow v) \ge {1 \over \deg (u) + 1} + {1 \over \deg (v)+1}, \end{aligned}$$

(6)

whenever $u\ne v$ are vertices of a simple graph and all the conductances are unit. Indeed, if u and v do not share an edge the lower bound can be improved by dropping the two $+1$’s in the denominators since the edges emanating from u separate u from v and similarly for the edge emanating from v. If u and v do share an edge, we replace that edge with a path of length 2 and assign conductance 2 to the two edges of the path and apply again Nash–Williams inequality.

2.1.2 The commute-time identity

The commute time between two vertices $a\ne z$ in a network is ${{\,\mathrm{{\mathbb {E}}}\,}}_a \tau _z + {{\,\mathrm{{\mathbb {E}}}\,}}_z \tau _a$. In other words, it is the expected time it takes to the random walk started at a to visit z and then go back to a. It turns out [4] that this quantity is just the rescaled resistance between a and z (see also [11, Corollary 2.21]):

$$\begin{aligned} {{\,\mathrm{{\mathbb {E}}}\,}}_a \tau _z + {{\,\mathrm{{\mathbb {E}}}\,}}_z \tau _a = 2|E(G)| R_\mathrm {eff}(a \leftrightarrow z) , \end{aligned}$$

(7)

in any network G with unit conductances.

2.2 Uniform spanning trees

Let G be a finite connected graph. The set of spanning trees of G is non-empty and finite hence we may draw one uniformly at random; denote by $\Gamma$ the resulting spanning tree. We call $\Gamma$ a uniform spanning tree (UST) of G. In this paper we will only use two basic properties of the UST.

2.2.1 Kirchhoff’s formula

Kirchhoff [8] discovered a fundamental relation between the uniform spanning tree and electric networks. Let $e=(x,y)\in E(G)$. Then

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}( e \in \Gamma ) = R_\mathrm {eff}(x \leftrightarrow y; G) . \end{aligned}$$

(8)

2.2.2 Spatial Markov property of the UST

Let $A,B\subset E(G)$ be two disjoint subset of edges of G. We would like to condition on the event $A \subset \Gamma$ and $B \cap \Gamma = \emptyset$. For this event to have positive probability we must have that A does not contain a cycle and that when erasing the edges of B from G we remain with a connected graph. It turns out that this conditional measure can be described as drawing a UST on a modified graph, see [11, Chapter 4]. We denote by $G/A-B$ the graph obtained from G by contracting the edges of A and erasing the edges of B.

Proposition 2.1

Let G be a finite connected graph and A, B two disjoint subsets of edges such that $G-B$ is connected and A has no cycles. Then the law of the UST on G conditioned on the event $A \subset \Gamma$ and $B\cap T=\emptyset$ equals the law of the UST on $G/A-B$, viewed as a random edge subset of G, union the edges of A.

Lastly we recall the negative correlations of the UST. It is an immediate corollary of (8) and Proposition 2.1 together with Rayleigh’s monotonicity for electric networks [11, Chapter 2] that the UST has negative correlations. That is, if $e\ne f$ are two edges of a finite connected graph and $\Gamma$ is a UST of G, then

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}( e \in \Gamma , f \in \Gamma ) \le {{\,\mathrm{{\mathbb {P}}}\,}}(e\in \Gamma ) {{\,\mathrm{{\mathbb {P}}}\,}}( f \in \Gamma ) , \end{aligned}$$

(9)

see [11, Chapter 4].

3 Foster’s theorem and variants

Recall that Foster’s Theorem [5] (which also follows from (8) immediately) asserts that on any connected graph G

$$\begin{aligned} \sum _{\{x,y\}\in E(G)} R_\mathrm {eff}(x \leftrightarrow y) = |V(G)|-1 . \end{aligned}$$

(10)

When G is a regular graph with degree d, its number of edges is ${|V(G)|d \over 2}$. Hence Foster’s Theorem in this case states that

$$\begin{aligned} {{\,\mathrm{{\mathbb {E}}}\,}}R_\mathrm {eff}(X_0 \leftrightarrow X_1) = {2 \over d} - {2 \over |V(G)|d} , \end{aligned}$$

(11)

where $\{X_0,X_1\}$ is a uniformly drawn edge of G, or equivalently, $X_0$ is a uniformly drawn vertex of G and $X_1$ is an independent uniform neighbor of $X_0$. By (6) the resistance between two vertices in a d-regular graph is deterministically lower bounded by ${2 \over d+1}$. Since this bound is rather close to the expectation above, it gives a useful concentration estimate for the random variable $R_\mathrm {eff}(X_0 \leftrightarrow X_1)$.

Lemma 3.1

On any d-regular graph G and for any $\varepsilon >2/d$ the number of edges $e=(x,y)$ with $R_\mathrm {eff}(x \leftrightarrow y) \ge \varepsilon$ is at most ${|V(G)| \over \varepsilon d - 2}$.

Proof

Denote by $N_\varepsilon$ the number of such edges. By (6) we bound $R_\mathrm {eff}(x\leftrightarrow y) \ge {2 \over d+1} \ge {2 \over d} - {2 \over d^2}$. Hence by Foster’s Theorem (10)

$$\begin{aligned} |V(G)|-1 \ge N_\varepsilon \varepsilon + \Big ( {|V(G)|d \over 2} - N_\varepsilon \Big ) (2/d - 2/d^2) , \end{aligned}$$

giving the required upper bound on $N_\varepsilon$. $\square$

Our first variant is an estimate of the resistance between two endpoints of a longer random walk.

Lemma 3.2

Let $(X_0,\ldots ,X_k)$ be a k-step random walk, $k\ge 1$, on a simple d-regular graph G starting from a uniformly drawn vertex $X_0$. Then

$$\begin{aligned} {{\,\mathrm{{\mathbb {E}}}\,}}R_\mathrm {eff}(X_0 \leftrightarrow X_k) \le {2 \over d} + {2(k-1) \over d^2} . \end{aligned}$$

Remark. In fact the proof gives that

$$\begin{aligned} {{\,\mathrm{{\mathbb {E}}}\,}}R_\mathrm {eff}(X_0 \leftrightarrow X_k)\le & {} {2 \over d} + {2(k-1) \over d^2} - {2 k \over |V(G)|d} \big ( 1-{1 \over d} \big )^{k-1} \\&\quad - {2k \over |V(G)|d(d-1)} \sum _{i=1}^{k-1} \big ( 1 - {1 \over d} \big )^{i} , \end{aligned}$$

which is an equality when $k=1$ by (11).

Proof

In any irreducible finite Markov chain the expected return time from a state to itself equals the inverse of its stationary mass. Thus, since G is regular we have that ${{\,\mathrm{{\mathbb {E}}}\,}}_{x_0}\tau ^+_{x_0} = |V(G)|$ for any vertex $x_0$ of G. Hence for any vertex $x_0$ and $k\ge 1$

$$\begin{aligned} |V(G)| \ge {{\,\mathrm{{\mathbb {E}}}\,}}_{x_0} \tau ^+_{x_0} \mathbf{1} _{\{\tau ^+_{x_0} > k\}}\ge & {} {1 \over d^{k}} \sum _{\begin{array}{c} (x_1,\ldots ,x_k) \\ x_i \ne x_0 \forall i=1,\ldots ,k \end{array}} \big [ {{\,\mathrm{{\mathbb {E}}}\,}}_{x_k} \tau _{x_0} + k \big ] , \end{aligned}$$

(12)

where $(x_1,\ldots ,x_k)$ is a walk of length k in G starting from a neighbor $x_1$ of $x_0$. On the other hand we have that

$$\begin{aligned} {{\,\mathrm{{\mathbb {E}}}\,}}{{\,\mathrm{{\mathbb {E}}}\,}}_{X_k} \tau _{x_0} = {1 \over d^{k} } \sum _{\begin{array}{c} (x_1, \ldots , x_k) \end{array}} {{\,\mathrm{{\mathbb {E}}}\,}}_{x_k} \tau _{x_0} . \end{aligned}$$

The last sum contains all the terms on the right hand side of (12) except those for which there is an $i\in [k-1]$ for which $x_{i}=x_0$ (if $x_k=x_0$ the hitting time is 0 so the case $i=k$ is dismissed). We let i be the last such index and by (12) we get

$$\begin{aligned} {{\,\mathrm{{\mathbb {E}}}\,}}{{\,\mathrm{{\mathbb {E}}}\,}}_{X_k} \tau _{x_0} \le |V(G)| - k \big (1 - {1 \over d} \big )^{k-1} + {1 \over d^{k}} \sum _{i=1}^{k-1} \sum _{\begin{array}{c} (x_1,\ldots ,x_{i}) \\ x_i=x_0 \end{array}} \sum _{\begin{array}{c} (x_{i+1}, \ldots , x_k) \\ x_j \ne x_0 \forall j=i+1,\ldots ,k \end{array}} {{\,\mathrm{{\mathbb {E}}}\,}}_{x_k} \tau _{x_0} , \end{aligned}$$

(13)

where for the second term on the right hand side we bounded the number of $(x_1,\ldots ,x_k)$ in (12) below by $d(d-1)^{k-1}$. By (12) we have that for each $i\in [k-1]$, if $x_i=x_0$, then

$$\begin{aligned} \sum _{\begin{array}{c} (x_{i+1}, \ldots , x_k) \\ x_j \ne x_0 \forall j=i+1,\ldots ,k \end{array}} {{\,\mathrm{{\mathbb {E}}}\,}}_{x_k} \tau _{x_0} \le |V(G)| d^{k-i} - kd(d-1)^{k-i-1}. \end{aligned}$$

We put this back into (13) and bound the number of $(x_1,\ldots ,x_{i})$ for which $x_i=x_0$ by $d^{i-1}$, sum over i and obtain

$$\begin{aligned} {{\,\mathrm{{\mathbb {E}}}\,}}{{\,\mathrm{{\mathbb {E}}}\,}}_{X_k} \tau _{X_0} \le |V(G)|\big ( 1+ {k-1 \over d}\big ) - k \big ( 1-{1 \over d} \big )^{k-1} - {k \over d-1} \sum _{i=1}^{k-1} \big ( 1 - {1 \over d} \big )^{i} . \end{aligned}$$

Since G is d-regular and $X_0$ is a uniformly drawn vertex we have that $(X_0,\ldots ,X_k)$ has the distribution as $(X_k,\ldots , X_0)$, hence

$$\begin{aligned} {{\,\mathrm{{\mathbb {E}}}\,}}\big [ {{\,\mathrm{{\mathbb {E}}}\,}}_{X_0} \tau _{X_k} + {{\,\mathrm{{\mathbb {E}}}\,}}_{X_k} \tau _{X_0} \big ]\le & {} 2|V(G)|\big ( 1+ {k-1 \over d}\big ) - 2k \big ( 1-{1 \over d} \big )^{k-1} \\&\quad - {2k \over d-1} \sum _{i=1}^{k-1} \big ( 1 - {1 \over d} \big )^{i}. \end{aligned}$$

By the commute-time identity (7) we get that

$$\begin{aligned} {{\,\mathrm{{\mathbb {E}}}\,}}R_\mathrm {eff}(X_0 \leftrightarrow X_k)\le & {} {2 \over d} + {2(k-1) \over d^2} - {2 k \over |V(G)|d} \big ( 1-{1 \over d} \big )^{k-1}\\&\quad - {2k \over |V(G)|d(d-1)} \sum _{i=1}^{k-1} \big ( 1 - {1 \over d} \big )^{i} , \end{aligned}$$

concluding our proof. $\square$

As in Lemma 3.1 we obtain a concentration estimate using (6).

Corollary 3.3

Let $(X_0,\ldots ,X_k)$ be a k-step random walk on a simple d-regular graph G starting from a uniformly drawn vertex $X_0$. Then for any $\varepsilon > {2 \over d}$ we have that

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}\big ( R_\mathrm {eff}(X_0 \leftrightarrow X_k) \ge \varepsilon \big ) \le {2k \over \varepsilon d^2 - 2d } . \end{aligned}$$

Proof

Denote the probability above by p. By (6) the resistance between distinct vertices is always at least ${2 \over d} - {2 \over d^2}$. By Lemma 3.2

$$\begin{aligned} {2 \over d} + {2k -2 \over d^2} \ge {{\,\mathrm{{\mathbb {E}}}\,}}R_\mathrm {eff}(X_0 \leftrightarrow X_k) \ge \varepsilon p + (1-p)\Big ( {2 \over d} - {2 \over d^2} \Big ) , \end{aligned}$$

and rearranging gives the result. $\square$

We present now our final variant of Foster’s Theorem. Let T be a fixed rooted tree with $k\ge 3$ vertices and G a d-regular graph with n vertices; we think of n and d as large and k as fixed. We denote T’s vertex set by [k] so that 1 is the root and such that for any $2 \le i \le k$ the graph spanned on [i] is a tree and the vertex i is a leaf. For instance, we can label all vertices according to a breadth-first search (BFS) order.

We say that a k-tuple of vertices $(v_1,\ldots ,v_k)$ of G is T-compatible when they are distinct vertices and for any $i,j\in [k]$ such that the pair $\{i,j\}$ is an edge of T, the pair $\{v_i,v_j\}$ is an edge of G. We draw a random k-tuple in the following iterative fashion. Let $X_1$ be a uniformly drawn vertex of G; for $2 \le i \le k-1$ assume we have drawn $(X_1,\ldots , X_{i-1})$ and let $1 \le j \le i-1$ be the unique index such that the vertex i of the subtree of T induced on [i] is a leaf hanging on j. We draw $X_i$ to be a random neighbor of $X_j$. When T is a path with k vertices, the tuple $(X_1,\ldots ,X_k)$ is distributed just as $k-1$ steps of the simple random walk starting from a uniform vertex. Let us remark that the tuple $(X_1,\ldots ,X_k)$ drawn this way is not necessarily T-compatible since the vertices are not necessarily distinct, but with high probability it will be T-compatible.

Theorem 3.4

Let G be a simple d-regular graph and T a rooted tree on $k\ge 3$ vertices such that $d \ge 16 k \log ^k d$. Let $\{X_1,\ldots ,X_k\}$ be a random k-tuple drawn as described above. Then with probability at least $1 - {2k^3 \over \log ^k d}$ we have that $(X_1,\ldots ,X_k)$ are T-compatible and

$$\begin{aligned} \Big | R_\mathrm {eff}\big (X_k \leftrightarrow \{X_1, \ldots , X_{k-1}\} \big ) - {k \over (k-1) d} \Big | \le {72 k \log ^k d \over d^2} . \end{aligned}$$

We first prove the following lemma.

Lemma 3.5

Let G be a network and [k] are distinct vertices of it with $k \ge 3$. Let $x>0$ be given and $\varepsilon >0$ satisfy $\varepsilon \le {x \over 32k}$. Assume that for any distinct $i \ne j$ in [k] one has

$$\begin{aligned} | R_\mathrm {eff}( i \leftrightarrow j ) -x | \le \varepsilon . \end{aligned}$$

(14)

Then

$$\begin{aligned} \Big | R_\mathrm {eff}\big (1 \leftrightarrow \{2,\ldots , k\}\big ) - {kx\over 2(k-1)} \Big | \le 72 k \varepsilon . \end{aligned}$$

(15)

Proof

Let p(i, j) be the probability that the network random walk on G started at i is at j when it first returns to [k]; possibly $i=j$. Then p is the transition matrix for the network random walk on [k] with conductances $c(i,j) = \pi (i)p(i,j)$ ($=c(j,i)$ by reversibility). This implies that $\pi (i)$ remains unchanged in this reduced network and by (5) we conclude that the pairwise effective resistances as well as the effective resistance between 1 and $\{2,\ldots ,k\}$ also remain unchanged. Hence (14) holds and it suffices to prove (15) for this reduced chain on [k]. Since loops do not change the resistance we remove them from this network, and we denote ${\tilde{\pi }}(i) = \sum _{j \ne i} c(i,j)$ the modified stationary measure after removing the loops.

Let $\Delta$ be the network Laplacian, that is, $\Delta$ is a $k\times k$ symmetric matrix defined by $\Delta (i,i)={\tilde{\pi }}(i)$ for any $i \in [k]$ and $\Delta (i,j) = -c(i,j)$ for any distinct $i\ne j$ in [k]. Given $a\in [k]$ we write $\Delta [a]$ for the $(k-1)\times (k-1)$ matrix obtained from $\Delta$ by erasing the row and column indexed by a.

For three vertices $a,i,j \in [k]$ with $i,j\in [k] \setminus \{a\}$, we write $g_a(i,j)=G_{a}(i,j)/{\tilde{\pi }}(j)$ for the normalized Green’s function of the random walk killed at a, that is, $G_{a}(i,j)$ is the expected number of visits to j of a random walk started at i before it visits a. We view $g_a(\cdot ,\cdot )$ as a $(k-1)\times (k-1)$ matrix. The quantity $g_a(i,j)$ is also the voltage at i when unit current flows from a to j (so that the voltage at a is zero). Hence, $g_a(i,j) = {{\,\mathrm{{\mathbb {P}}}\,}}_i(\tau _j < \tau _a) \cdot R_\mathrm {eff}(a \leftrightarrow j)$. It is well known that this quantity can be expressed in terms of the pairwise effective resistances, indeed, by Exercise 2.68 of [11] we get that

$$\begin{aligned} g_a(i,j) = {R_\mathrm {eff}(a \leftrightarrow j) + R_\mathrm {eff}(a\leftrightarrow i) - R_\mathrm {eff}(i \leftrightarrow j) \over 2} , \end{aligned}$$

from which we deduce by our assumption (14) that $|g_a(i,j)-x/2| \le 3\varepsilon /2$ for all $i \ne j$ in $[k]\setminus \{a\}$ and $|g_a(i,i) -x|\le \varepsilon$ for all $i\in [k]\setminus \{a\}$.

It is classical (see Exercise 2.62(a) in [11]) that $g_a(\cdot ,\cdot )$ is an invertible matrix and that $\Delta [a] = \big [g_a(\cdot ,\cdot ) \big ]^{-1}$. Denote by A the $(k-1)\times (k-1)$ matrix with x on the diagonal and x/2 in all other entries, so that $g_a = A+E$ and $||E||_1 \le {3\varepsilon \over 2}(k-4/3)$ where $||E||_1$ the maximum $\ell _1$ norm of the rows of E viewed as vectors in ${\mathbb {R}}^{k-1}$.

It is straightforward to verify that $A^{-1}$ is a matrix with $\alpha$ on the diagonal and $\beta$ in all other entries, where

$$\begin{aligned} \alpha = {2(k-1) \over kx} \qquad \qquad \beta = -{2 \over kx} , \end{aligned}$$

so that $||A^{-1}||_1 = {4k-6 \over kx}$. It is a well known fact [15] that if $||A^{-1}||_1\cdot ||E||_1<1$, then

$$\begin{aligned} ||(A+E)^{-1} - A^{-1} ||_1 \le {||A^{-1}||_1^2 ||E||_1\over 1-||A^{-1}||_1||E||_1} . \end{aligned}$$

Since $\varepsilon \le {x \over 32 k}$ we learn that $||A^{-1}||_1\cdot ||E||_1\le 1/4$ from which we conclude that $||\Delta [a] - A^{-1}||_1 \le {32 k \varepsilon / x^{2}}$. Since a was arbitrary for any $i,j\in [k]$ with $i\ne j$ we get

$$\begin{aligned} \Big |c(i,j) - {2 \over kx} \Big | \le {32 k \varepsilon \over x^{2}} \qquad \qquad \Big | {\tilde{\pi }}(i) - {2(k-1) \over kx} \Big | \le {32 k \varepsilon \over x^{2}} \le {1 \over x}, \end{aligned}$$

since $\varepsilon \le {x \over 32 k}$. Since $k \ge 3$ we have that ${\tilde{\pi }}(i) \ge {1 \over 3x}$ and ${k \over k-1} \le 3/2$. Thus,

$$\begin{aligned} \Big | {1 \over {\tilde{\pi }}(i)} - {kx\over 2(k-1)} \Big | \le {32 k^2 \varepsilon /x \over 2(k-1){\tilde{\pi }}(i)} \le {72 k \varepsilon } , \end{aligned}$$

where we used that if $|a-b|\le c$ then $|{1 \over a}-{1 \over b}| \le c/|ab|$.

Since there are no loops in our reduced network, the network random walk started at 1 visit $\{2,\ldots ,k\}$ before returning to 1 with probability 1. Hence $R_\mathrm {eff}(1 \leftrightarrow \{2,\ldots ,k\})$ is just $1 \over {\tilde{\pi }}(1)$ by (5), concluding the proof. $\square$

Proof of Theorem 3.4

Put $\varepsilon = {2 + {\log ^k d \over d} \over d}$. For any $i,j\in [k]$ with $i\ne j$ the random vertex $X_i$ is uniformly distributed over the vertices of G and $X_j$ is the endpoint of a random walk starting at $X_i$ of length $\ell \le k$, where $\ell$ is the length of the path between i and j in T. By Corollary 3.3

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}\Big ( R_\mathrm {eff}(X_i \leftrightarrow X_j) \ge {2 + {\log ^k d\over d} \over d} \Big ) \le {2k \over \log ^k d } . \end{aligned}$$

By the union bound

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}\Big ( \exists i\ne j \in [k] \quad R_\mathrm {eff}(X_i \leftrightarrow X_j) \ge {2 + {\log ^k d\over d} \over d} \Big ) \le {k^3 \over \log ^k d } . \end{aligned}$$

Furthermore, by (6), if $X_i \ne X_j$, then the resistance across them is at least ${2 \over d} - {2 \over d^2}$. At each step of the random process of drawing $(X_1,\ldots ,X_k)$, the probability we draw an already chosen vertex is at most k/d hence the probability that $(X_1,\ldots ,X_k)$ is compatible with T (in particular they are distinct vertices) is at least $1-{k^2 \over d} \ge 1-{k^3 \over \log ^k d }$ by our assumption on d.

We conclude that with probability at least $1-2k^3/\log ^k d$ for all $i,j\in [k]$ with $i\ne j$ we have

$$\begin{aligned} \Big | R_\mathrm {eff}(X_i \leftrightarrow X_j) - {2 \over d} \Big | \le {\log ^k d \over d^2} , \end{aligned}$$

from which Theorem 3.5 implies that desired result (we have used our assumption $d \ge 16 k \log ^k d$ to verify the assumption of Theorem 3.5). $\square$

Corollary 3.6

Let G be a simple d-regular graph and T a rooted tree on $k\ge 3$ vertices such that $d \ge 16 k \log ^k d$. Denote by N the number of k-tuples $(v_1,\ldots ,v_k)$ that are T-compatible and such that

$$\begin{aligned} \Big | R_\mathrm {eff}( v_k \leftrightarrow \{v_1,\ldots ,v_{k-1}\}) - {k \over (k-1) d} \Big | \ge {72 k \log ^k d \over d^2} . \end{aligned}$$

Then

$$\begin{aligned} N \le {2 nd^{k-1}k^3 \over \log ^k d}. \end{aligned}$$

Proof

Immediate from Theorem 3.4. $\square$

4 Tightness

Our goal in this section is to prove Theorem 4.2 showing that, in the setting of Theorem 1.1, for any integer $r\ge 1$ the random variables $|B_{\Gamma _n}(X,r)|$ are a tight sequence. We remark that for $r=1$ this is trivial since the expected degree of a randomly chosen vertex in any tree is at most 2. This reasoning fails for $r \ge 2$, indeed, the behavior of bigger balls is inherently different, for example, ${{\,\mathrm{{\mathbb {E}}}\,}}|B_{\Gamma _n}(X,3)|$ may be unbounded, see Sect. 7.2 for an example and further discussion.

Lemma 4.1

Let $\Gamma$ be a fixed finite tree, $S\subset V(\Gamma )$ be a subset of its vertices and X a uniformly drawn vertex of $V(\Gamma )$. Then for any positive integers r, m, M we have

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}\Big ( B_\Gamma (X,r-1) \cap S \ne \emptyset ,\, |B_\Gamma (X,r-1)| \le m , \, |B_\Gamma (X,r)| \le M \Big ) \le \frac{r|S|m^{r-2} M}{|V(\Gamma )|} . \end{aligned}$$

Proof

If $x\in \Gamma$ is a vertex such that $B_\Gamma (x,r-1) \cap S \ne \emptyset$, then there exists a vertex $v \in S$ and a simple path in $\Gamma$ of length $\ell \le r-1$ from x to v. If in addition $|B_\Gamma (x,r-1)| \le m$ and $|B_\Gamma (x,r)| \le M$, then when $\ell <r-1$ all vertex degrees on this path are at most m and if $\ell =r-1$, then the degrees of the first $r-2$ vertices of the path are at most m and the degree of v is at most M. For each $v \in S$, the number of such paths of length $\ell <r-1$ is at most $m^{\ell }$ and the number of such paths when $\ell = r-1$ is at most $M m^{r-2}$. Hence the number of possible x’s is at most

$$\begin{aligned} |S| \sum _{\ell =1} ^{r-2} m^{\ell } + |S| m^{r-2} M \le r|S|m^{r-2} M , \end{aligned}$$

concluding the proof. $\square$

Theorem 4.2

(Tightness) Let $\{G_n\}$ be a sequence of finite, simple, connected, regular graphs with degree $d(n)\rightarrow \infty$. Let $\Gamma _n$ be a uniformly drawn spanning tree of $G_n$ and let X be a uniformly chosen random vertex of $G_n$. Then for any integer $r\ge 0$ we have

$$\begin{aligned} \lim _{M \rightarrow \infty } \sup _n {{\,\mathrm{{\mathbb {P}}}\,}}\Big ( |B_{\Gamma _n}(X,r)| \ge M \Big ) = 0 . \end{aligned}$$

Proof

To simplify the notation we write $B_{r}$ for the random variable $|B_{\Gamma _n}(X,r)|$. Our proof is by induction. The case $r=0$ is obvious since $B_0=1$ always. Let $r \ge 1$ and let $\varepsilon >0$ be arbitrary. By induction we know that there exists some $m>0$ such that for all n we have

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}\Big ( B_{r-1} \ge m \Big ) \le \varepsilon /2 . \end{aligned}$$

(16)

We fix $M \ge m$ that we will choose later depending only on m, r and $\varepsilon$. Our goal is to estimate ${{\,\mathrm{{\mathbb {P}}}\,}}( B_r \ge M , B_{r-1} \le m )$. This equals

$$\begin{aligned} \sum _{k=0}^\infty {{\,\mathrm{{\mathbb {P}}}\,}}\Big ( B_r \in [2^k M, 2^{k+1}M) , B_{r-1} \le m \Big ) . \end{aligned}$$

(17)

For each $k\ge 0$ we choose some large $A_k \ge 4$ that will also be chosen later (it will depend only k, r, m and $\varepsilon$) and apply Lemma 3.1 to obtain that the number of edges with resistance on them at least $A_k/d$ is at most $n/(A_k-2) \le 2n/A_k$. Let $S_k$ denote the set of vertices which touch at least $2^{k-1} M/m$ edges with resistance at least $A_k/d$. Thus, $|S_k| \le \frac{8n m}{A_k 2^{k} M}$. By Lemma 4.1 we have

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}( B_r \in [2^k M, 2^{k+1}M) , B_{r-1} \le m , B_{\Gamma _n}(X,r-1) \cap S_k \ne \emptyset \Big ) \le \frac{16 r m^{r-1} }{A_k} . \end{aligned}$$

(18)

We now upper bound

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}\Big ( B_r \in [2^k M, 2^{k+1}M) , B_{r-1} \le m , B_{\Gamma _n}(X,r-1) \cap S_k = \emptyset \Big ) . \end{aligned}$$

(19)

If the event above occurs, then there is a path $v_0,v_1,\ldots ,v_{r-1}$ in $\Gamma _n$ starting at $v_0=X$ of length $r-1$ such that

• (1) All vertices in the path are not in $S_k$, and,

• (2) $v_{r-1}$ has at least $D=2^kM/m$ edges of $\Gamma _n$ touching it whose other endpoint is not in $B_{\Gamma _n}(X,r-1)$.

Since $v_{r-1} \not \in S_k$ at least D/2 of the edges specified above have resistance at most $A_k/d$ between their endpoints. We enumerate over all the possibilities of the path $(v_0,\ldots ,v_{r-1})$ (there are at most $nd^{r-1}$ choices) and D/2 children of $v_{r-1}$ (there are ${d \atopwithdelims ()D/2}$ choices). We apply (9) and bound the probability of each edge being in $\Gamma _n$ by $A_k/d$. We obtain that (19) is bounded by

$$\begin{aligned} d^{r-1} (A_k/d)^{r-1} {d \atopwithdelims ()D/2} (A_k/d)^{D/2} \le A_k^{r-1} \Big ( {2eA_k \over D} \Big )^{D/2} . \end{aligned}$$

We put this bound together with (16), (17) and (18) to obtain that

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}( B_r \ge M ) \le {\varepsilon \over 2} + \sum _{k=0}^\infty {16 r m^{r-1} \over A_k} + \sum _{k=0}^\infty A_k^{r-1} \Big ( {2eA_k \over D} \Big )^{D/2} , \end{aligned}$$

(20)

where $D=2^k M/m$. We now choose $A_k = 2^{k+7} r m^{r-1} \varepsilon ^{-1}$ so that the first sum on the right hand side is at most $\varepsilon /4$. We then take $M=M(m,r,\varepsilon )$ so large such that for any $k\ge 0$ we have

$$\begin{aligned} A_{k}^{r-1} \Big ( {2eA_k \over D} \Big )^{D/2} \le \varepsilon (1/4)^k /8 , \end{aligned}$$

for example, M can be chosen so that $2eA_k/D \le \varepsilon ^{2r} 2^{-r} r^{-r}m^{-r^2}$ and $D/2 \ge 2^{k+1}$ so that the third sum in (20) is at most $\varepsilon /4$. We get that ${{\,\mathrm{{\mathbb {P}}}\,}}( B_r \ge M ) \le \varepsilon$, concluding the proof. $\square$

5 Proof of main theorem

We say that a vertex of G is good if it does not touch an edge such that the effective resistance between its endpoints is at least ${\log d \over d}$. Given a fixed rooted tree T of height r on $k\ge 2$ vertices, we say that T-compatible k-tuple $(v_1,\ldots ,v_k)$ is $\mathbf{good}$ if all the vertices of tree-distance at most $r-1$ to the root are good. In other words, if the vertices $(v_1,\ldots , v_{k-|T_r|})$ are good vertices. The following is a key calculation.

Lemma 5.1

Let G be a simple d-regular graph and T a rooted tree on $k\ge 2$ vertices. If $d \ge 72 k \log ^{k+1} d$, then

$$\begin{aligned} {1 \over n} \sum _{\begin{array}{c} (v_1,\ldots , v_k) \\ T{\mathrm{-compatible}} \\ \text {good} \end{array}} \prod _{i=2}^k R_\mathrm {eff}(v_i \leftrightarrow \{v_1,\ldots , v_{i-1}\}) \le k + {4^k 2 k^3 \over \log d} , \end{aligned}$$

(21)

Proof

We prove by induction on k. The base case $k=2$ follows (without the second term on the right hand side of (21)) by Foster’s Theorem (10). We proceed to the general $k\ge 3$ case.

We write $C=2k^3$. By Corollary 3.6 the number of T-compatible k-tuples $(v_1,\ldots ,v_k)$ for which

$$\begin{aligned} R_\mathrm {eff}(v_k \leftrightarrow \{v_1,\ldots ,v_{k-1}\}) \ge {k + {72 k\log ^{k} d \over d} \over (k-1)d} \end{aligned}$$

(22)

is at most $Cnd^{k-1} / \log ^{k} d$. For these tuples, we bound each term in the product by ${\log d \over d}$; indeed, we may do so since $v_i$ has a good neighbor in $\{v_1,\ldots ,v_{i-1}\}$ for all $i\in \{2,\ldots ,k\}$. This gives us an upper bound of

$$\begin{aligned} {1 \over n} \times {Cnd^{k-1} \over \log ^{k} d} \times \Big ( {\log d \over d} \Big )^{k-1} = {C \over \log d} . \end{aligned}$$

For all other tuples we have the opposite inequality at (22). Thus we may bound the last term in the product by this, sum it over the d possible choices of $v_k$ and obtain that the sum at the left hand side of (21) is bounded above by

$$\begin{aligned} {C \over \log d} + {k + {1 \over \log d} \over (k-1)} \cdot {1 \over n} \cdot \sum _{\begin{array}{c} (v_1,\ldots , v_{k-1}) \\ T\setminus \{v_k\}{\mathrm{-compatible}} \\ \text {good} \end{array}} \prod _{i=2}^{k-1} R_\mathrm {eff}(v_i \leftrightarrow \{v_1,\ldots , v_{i-1}\}) , \end{aligned}$$

where we used our assumption on d to bound ${72 k \log ^{k} d \over d} \le {1 \over \log d}$. We use our induction hypothesis to bound the last term and get that

$$\begin{aligned} {1 \over n} \sum _{\begin{array}{c} (v_1,\ldots , v_k) \\ T{\mathrm{-compatible}} \\ \text {good} \end{array}} \prod _{i=2}^k R_\mathrm {eff}(v_i \leftrightarrow \{v_1,\ldots , v_{i-1}\})\le & {} {C \over \log d} + {k + {1 \over \log d} \over (k-1)} \Big ( k-1 + {4^{k-1}C \over \log d} \Big ) \\\le & {} k + {2C \over \log d} + {3 \cdot 4^{k-1} C \over \log d} , \end{aligned}$$

where we bounded ${k + {1 \over \log d} \over (k-1)} \le 3$. Since $2+3\cdot 4^{k-1}\le 4^k$ we get the desired inequality and conclude our proof. $\square$

Proof of Theorem 1.2

Let $(v_1,\ldots ,v_k)$ be a T-compatible k-tuple of $G_n$. We write $T(v_1,\ldots ,v_k)$ for the subset of edges $\big \{ \{v_i,v_j\} : \{i,j\} \in E(T) \}$ of $G_n$ (by definition of T-compatible all of these pairs must be edges of $G_n$). We have that

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}(B_{\Gamma _n}(X, r) \cong T) = {1 \over |V(G_n)| |\mathrm {Stab}_T|} \sum _{\begin{array}{c} (v_1,\ldots , v_k) \\ T{\mathrm{-compatible}} \end{array}} {{\,\mathrm{{\mathbb {P}}}\,}}( B_{\Gamma _n}(v_1, r) = T(v_1,\ldots ,v_k) ) , \end{aligned}$$

since for each root preserving isomorphism $\sigma \in \mathrm {Stab}_T$ the edge subsets $T(v_1,\ldots ,v_k)$ and $T(v_{\sigma (1)},\ldots ,v_{\sigma (k)})$ are equal so the corresponding events identify as well. Up to these isomorphisms, all the events are disjoint and hence the $|\mathrm {Stab}_T|^{-1}$ term above.

Recall that $T_r$ are the vertices at the last level of T viewed from the root. Set $t=k-|T_r|$ so that by our labeling convention the vertices [t] are the vertices of T that are not in $T_r$. Denote by $\lambda _T(v_1,\ldots , v_k)$ the event that all edges emanating from $v_1, \ldots , v_{t}$ which do not belong to $T(v_1,\ldots ,v_k)$ are not in the UST $\Gamma _n$. We have

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}(B_{\Gamma _n}(X, r) \cong T) = {1 \over |V(G_n)| |\mathrm {Stab}_T|} \ \sum _{\begin{array}{c} (v_1,\ldots , v_k) \\ T{\mathrm{-compatible}} \end{array}} \ {{\,\mathrm{{\mathbb {P}}}\,}}\big ( T(v_1,\ldots ,v_k) \subset \Gamma _n , \, \lambda _T(v_1,\ldots , v_k) \big ) . \end{aligned}$$

By Kirchhoff’s formula (8) together with spatial Markov’s property (Proposition 2.1) for any T-compatible tuple $(v_1,\ldots ,v_k)$, we have that

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}(T(v_1,\ldots ,v_k) \subset \Gamma _n) = \prod _{i=2}^k R_\mathrm {eff}(v_i \leftrightarrow \{v_1,\ldots , v_{i-1}\}) . \end{aligned}$$

(23)

By the spatial Markov property (Proposition 2.1), the probability of the event $\lambda _T(v_1,\ldots , v_k)$ conditioned on $T(v_1,\ldots ,v_k) \subset \Gamma _n$ is the probability that all edges emanating from $\{v_1,\ldots , v_t\}$ that do not belong to $T(v_1,\ldots ,v_k)$ are not in a UST of the graph $G/(v_1,\ldots ,v_k)$ in which the edges $T(v_1,\ldots ,v_k)$ are contracted and loops erased. The degree in this graph of the vertex corresponding to $(v_1,\ldots ,v_k)$ is at least $kd-k^2$ and at most kd.

Denote by $\{e_1,\ldots , e_L\}$ the set of edges of G that have precisely one endpoint in $\{v_1,\ldots , v_t\}$ and do not belong to $T(v_1,\ldots ,v_k)$. Since all degree are d we have that $L\ge td - k^2$. For any $\ell$ satisfying $1 \le \ell \le L$ we have

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}( e_\ell \not \in \Gamma _n \mid \{e_1,\ldots ,e_{\ell -1}\} \cap \Gamma _n&= \emptyset , \, T(v_1,\ldots ,v_k) \subset \Gamma _n) \\&\le 1 - {1 \over d-k+1} - {1 \over kd - k^2 - \ell +1} , \end{aligned}$$

since if $e_\ell =(v_i,u)$ for some $1 \le i \le k$ and $u\not \in \{v_1,\ldots ,v_k\}$, then the degree of u in $G/(v_1,\ldots ,v_k) - \{e_1,\ldots ,e_{\ell -1}\}$ is at least $d-k$ (since $G_n$ is simple) and the degree of $v_i$ in the same graph is at least $kd - k^2 - \ell +1$, and the estimate follows by the spatial Markov property and our deterministic lower bound (6) on the effective resistances between two vertices.

We apply this estimate sequentially over $\{e_1,\ldots , e_L\}$, use the fact that $L\ge td - O(1)$ and obtain that

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}\big ( \lambda _T(v_1,\ldots , v_k) \mid T(v_1,\ldots ,v_k) \subset \Gamma _n \big )\le & {} \prod _{\ell =1}^{L} \Big ( 1 - {1 \over d-k+1} - {1 \over dk - k^2 - \ell +1} \Big ) \\\le & {} \exp \Big ( -\sum _{\ell =1}^{td-k^2} \big ( {1 \over d} + {1 \over dk - \ell } \big ) \Big ) \\\le & {} (1+O(d^{-1})) {e^{-t} (k - t) \over k} , \end{aligned}$$

where the second inequality is a straightforward computation with harmonic series. The constants in the O-notation depend on k. Thus,

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}(B_{\Gamma _n}(X, r) \cong T) \le {(1+O(d^{-1})) e^{-t} (k - t) \over k |V(G_n)| |\mathrm {Stab}_T|} \ \sum _{\begin{array}{c} (v_1,\ldots , v_k) \\ T{\mathrm{-compatible}} \end{array}} \prod _{i=2}^k R_\mathrm {eff}(v_i \leftrightarrow \{v_1,\ldots , v_{i-1}\}) . \end{aligned}$$

We now show that the probability that $B_{\Gamma _n}(X, r-1)$ contains a vertex that is not good is negligible. Indeed, by Lemma 3.1 the number of such vertices is at most $Cn/\log d$ and so by Lemma 4.1 the probability that $B_{\Gamma _n}(X, r) \cong T$ and that there exists a vertex of $B_{\Gamma _n}(X, r-1)$ touching such a vertex is bounded by ${C r k^{r-1} \over \log d} = o(1)$ since $d(n) \rightarrow \infty$ and k and r are fixed. Hence by Lemma 5.1 we get

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}(B_{\Gamma _n}(X, r) \cong T) \le { e^{-t} (k - t) \over |\mathrm {Stab}_T|} + o(1) . \end{aligned}$$

(24)

Denote by $T_M$ the set of rooted trees T with $|V(T)|\le M$, viewed up to root preserving graph isomorphism. Let $\varepsilon >0$ be arbitrary, apply Theorem 4.2 to obtain a number $M_1=M_1(\varepsilon )<\infty$ so that for all n

$$\begin{aligned} \sum _{T \in T_{M_1}}{{\,\mathrm{{\mathbb {P}}}\,}}( B_{\Gamma _n}(X, r) \cong T ) \in [1- \varepsilon ,1] . \end{aligned}$$

By (1) there exists $M_2=M_2(\varepsilon )<\infty$ such that

$$\begin{aligned} \sum _{T \in T_{M_2}} { e^{-t} (k - t) \over |\mathrm {Stab}_T|} \in [1-\varepsilon ,1] . \end{aligned}$$

We put $M=\max (M_1, M_2)$. By (24) we learn that there exists $N=N(M,\varepsilon )$ such that for any $T\in T_M$ and any $n\ge N$ one has

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}(B_{\Gamma _n}(X, r) \cong T) \le { e^{-t} (k - t) \over |\mathrm {Stab}_T|} + {\varepsilon \over |T_M|} . \end{aligned}$$

If two positive sequences $\{a_\ell \}_{\ell =1}^N$ and $\{b_\ell \}_{\ell =1}^N$ satisfy $a_\ell \le b_\ell$ for all $\ell \in [N]$ as well as $\sum _{\ell =1}^N a_\ell \in [1-\varepsilon ,1]$ and $\sum _{\ell =1}^N b_\ell \in [1-\varepsilon ,1+\varepsilon ]$, then $\sum _{\ell =1}^N |a_\ell -b_\ell | \le 2\varepsilon$. Hence

$$\begin{aligned} \sum _{T\in T_M} \Big | {{\,\mathrm{{\mathbb {P}}}\,}}(B_{\Gamma _n}(X, r) \cong T) - {e^{-t} (k - t) \over |\mathrm {Stab}_T|} \Big | \le 2\varepsilon , \end{aligned}$$

concluding our proof. $\square$

6 The UST on high degree almost regular graphs

In this section we describe the necessary changes to the proof of Theorem 1.2 in order for it to work when $\{G_n\}$ is a sequence of high degree almost regular graphs with $d(n)\rightarrow \infty$ (see Definition 1.3), that is, in order to prove Theorem 1.4. Furthermore, we prove the quenched version Theorem 1.5 which relies on Theorem 1.4 (even in the purely regular setting of Theorem 1.2).

We will need to take into account the rate of decay of the o(1) terms in Definition 1.3. Therefore we assume for the rest of this section that $\{G_n\}$ is a sequence of high degree almost regular graphs such that

$$\begin{aligned} \Big | \big \{ v \in V(G_n): | \deg (v) - d(n) | \le \delta _n d(n) \big \} \Big | \ge (1-\delta _n)|V(G_n)| , \end{aligned}$$

(25)

and

$$\begin{aligned} \Big |\sum _{v\in V(G_n)} \deg (v) - d(n)|V(G_n)| \Big | \le \delta _n d(n)|V(G_n)| ,\ \end{aligned}$$

(26)

where $\delta _n = o(1)$ is some non-negative sequence tending to 0. Without loss of generality we assume that $d(n)^{-1} = O(\delta _n)$; otherwise we take the sequence $\max (\delta _n, d(n)^{-1})$.

For such a sequence we have that

$$\begin{aligned} \sum _{v \in V(G_n)} \Big | {\deg (v) \over \sum _v \deg (v)} - {1 \over |V(G_n)|} \Big | = O(\delta _n) , \end{aligned}$$

(27)

or in other words, we may couple the uniformly drawn vertex with a vertex drawn according to the stationary distribution so that they are equal with probability at least $1-O(\delta _n)$, see [9, Proposition 4.7].

6.1 Almost regular versions of Sections 3 and 4

Let $X_0$ be a vertex drawn according to the stationary distribution and let $X_1$ be a random neighbor of it so that $\{X_0,X_1\}$ is a uniformly drawn edge of $G_n$. Then Foster’s Theorem gives the analogue of (11) for high degree almost regular graphs

$$\begin{aligned} {{\,\mathrm{{\mathbb {E}}}\,}}R_\mathrm {eff}(X_0 \leftrightarrow X_1) = {2 + O(\delta _n) \over d(n)} . \end{aligned}$$

Lemma 3.1′

Let $\{G_n\}$ be a high degree almost regular graph satisfying (25) and (26). For any $\varepsilon >2/d$ the number of edges $e=(x,y)\in E(G_n)$ with $R_\mathrm {eff}(x \leftrightarrow y) \ge \varepsilon$ is at most ${(1+O(\delta _n))|V(G_n)| \over \varepsilon d - 2}$.

Proof

Similarly to the proof of Lemma 3.1, we denote by $N_\varepsilon$ the number of such edges. For every edge (x, y) for which the degree of both its vertices is at most $(1+\delta _n)d(n)$ we bound $R_\mathrm {eff}(x \leftrightarrow y) \ge {2 - O(\delta _n) \over d}$ using (6). By (25) and (26) the number of such edges is at least $(1-O(\delta _n))|V(G_n)|d/2$, so by Foster’s Theorem (10)

$$\begin{aligned} |V(G_n)|-1 \ge N_\varepsilon \varepsilon + \Big ( {(1-O(\delta _n))|V(G_n)|d \over 2} - N_\varepsilon \Big ) { 2-O(\delta _n) \over d} , \end{aligned}$$

giving the required upper bound on $N_\varepsilon$. $\square$

We use Lemma 3.1’to prove tightness in the almost regular setting.

Theorem 4.2′

(Tightness) Let $\{G_n\}$ be a high degree almost regular graph sequence. Let $\Gamma _n$ be a uniformly drawn spanning tree of $G_n$ and let X be a random vertex chosen according to the stationary distribution of $G_n$. Then for any integer $r\ge 0$ we have

$$\begin{aligned} \lim _{M \rightarrow \infty } \sup _n {{\,\mathrm{{\mathbb {P}}}\,}}\Big ( |B_{\Gamma _n}(X,r)| \ge M \Big ) = 0 . \end{aligned}$$

Proof

The proof of Theorem 4.2 applies verbatim with Lemma 3.1’replacing the use of Lemma 3.1. $\square$

Next we alter the statement of Lemma 3.2 to the following.

Lemma 3.2′

Let $\{G_n\}$ be a high degree almost regular graph satisfying (25) and (26) and let $(X_0,\ldots ,X_k)$ be a k-step random walk on $G_n$, with $k\ge 1$, starting from a random vertex $X_0$ drawn according to the stationary distribution. Then

$$\begin{aligned} {{\,\mathrm{{\mathbb {E}}}\,}}R_\mathrm {eff}(X_0 \leftrightarrow X_k) \le {2 + O(\delta _n) \over d}. \end{aligned}$$

where the implicit constant may depend on k.

Proof

The alterations required in the proof of Lemma 3.2 are changing the stationary mass of $x_0$ and replacing powers of d into the corresponding products of degrees. So that (12) now becomes

$$\begin{aligned} \sum _{\begin{array}{c} (x_1,\ldots ,x_k) \\ x_i \ne x_0 \forall i=1,\ldots ,k \end{array}} {1 \over \prod _{i=0}^{k-1} \deg (x_i) } \big [ {{\,\mathrm{{\mathbb {E}}}\,}}_{x_k} \tau _{x_0} + k \big ] \le {1 \over \pi (x_0)} , \end{aligned}$$

where $\pi (x_0) = \deg (x_0) / \sum _{v\in V(G_n)} \deg (v)$ is the stationary mass of $x_0$. The analogue of (13) is now

$$\begin{aligned} {{\,\mathrm{{\mathbb {E}}}\,}}{{\,\mathrm{{\mathbb {E}}}\,}}_{X_k} \tau _{x_0} \le {1 \over \pi (x_0)} + \sum _{i=1}^{k-1} \sum _{\begin{array}{c} (x_1,\ldots ,x_{i}) \\ x_i=x_0 \end{array}} {1 \over \prod _{j=0}^{i-1} \deg (x_j) } \quad \sum _{\begin{array}{c} (x_{i+1}, \ldots , x_k) \\ x_j \ne x_0 \forall j=i+1,\ldots ,k \end{array}} {1 \over \prod _{j=i}^{k-1} \deg (x_j) } {{\,\mathrm{{\mathbb {E}}}\,}}_{x_k} \tau _{x_0} . \end{aligned}$$

Hence plugging in the previous estimate yields

$$\begin{aligned} {{\,\mathrm{{\mathbb {E}}}\,}}{{\,\mathrm{{\mathbb {E}}}\,}}_{X_k} \tau _{x_0} \le {1 \over \pi (x_0)} + {1 \over \pi (x_0)} \sum _{i=1}^{k-1} {{\,\mathrm{{\mathbb {P}}}\,}}(X_i=x_0 \mid X_0= x_0) . \end{aligned}$$

We average this inequality over $x_0$ according to the stationary measure of $G_n$ and get that

$$\begin{aligned} {{\,\mathrm{{\mathbb {E}}}\,}}{{\,\mathrm{{\mathbb {E}}}\,}}_{X_k} \tau _{X_0} \le |V(G_n)|+ \sum _{i=1}^{k-1} \sum _{x_0} {{\,\mathrm{{\mathbb {P}}}\,}}(X_i=x_0 \mid X_0= x_0) . \end{aligned}$$

For each $i\in [k-1]$, the corresponding term in the sum on the right hand side, divided by |V(G)|, is just the probability that ${{\,\mathrm{{\mathbb {P}}}\,}}(X_i=X_0)$ when $X_0$ is a uniformly chosen vertex. It is easier to bound the return probability when $X_0$ is a stationary vertex rather than a uniform vertex. By (27) the difference between the two probabilities is $O(\delta _n)$. If $X_0$ is stationary, then $X_{i-1}$ is also a stationary vertex, hence the probability that it is a vertex with degree smaller than d/2 is $O(\delta _n)$ by (25), and if that does not occur the probability of moving to $X_0$ in the next step is at most $2/d=O(\delta _n)$. We deduce that

$$\begin{aligned} {{\,\mathrm{{\mathbb {E}}}\,}}{{\,\mathrm{{\mathbb {E}}}\,}}_{X_k} \tau _{X_0} \le (1+O(\delta _n))|V(G_n)| , \end{aligned}$$

and the proof continues precisely as in Lemma 3.2 to give the desired result. $\square$

Corollary 3.3′

Let $\{G_n\}$ be a high degree almost regular graph satisfying (25) and (26) and let $(X_0,\ldots ,X_k)$ be a k-step random walk on $G_n$, with $k\ge 1$, starting from a random vertex $X_0$ drawn according to the stationary distribution. Then for any $\varepsilon > 2/d$ we have

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}\big ( R_\mathrm {eff}(X_0 \leftrightarrow X_k) \ge \varepsilon \big ) \le {O(\delta _n) \over \varepsilon d - 2 } . \end{aligned}$$

Proof

Denote the probability that $R_\mathrm {eff}(X_0 \leftrightarrow X_k) \ge \varepsilon$ by p. Since $X_0$ is stationary so is $X_k$ hence by (25) the probability that they both are vertices of degree $(1\pm O(\delta _n))d(n)$ is at least $1-O(\delta _n)$. In this case we bound the resistance between them from below by ${2-O(\delta _n) \over d(n)}$ using (6). Thus, by Lemma 3.2’we obtain

$$\begin{aligned} {2 + O(\delta _n) \over d} \ge {{\,\mathrm{{\mathbb {E}}}\,}}R_\mathrm {eff}(X_0 \leftrightarrow X_k) \ge \varepsilon p + (1-p-O(\delta _n)){2 - O(\delta _n) \over d} , \end{aligned}$$

and rearranging gives the result. $\square$

We are now ready to state the analogue of Theorem 3.4. Given a fixed finite rooted tree T with $k\ge 3$ vertices, the random k-tuple $(X_1,\ldots ,X_k)$ of vertices is drawn exactly as described above Theorem 3.4 with the only exception that $X_0$ is now a stationary vertex.

Theorem 3.4′

Let $\{G_n\}$ be a high degree almost regular graph satisfying (25) and (26). Let $\{X_1,\ldots ,X_k\}$ be a random k-tuple drawn as described above. Then there exists $C=C(k)>0$ such that with probability at least $1 - O(\delta _n^{1/2})$ we have that $(X_1,\ldots ,X_k)$ are T-compatible and

$$\begin{aligned} \Big | R_\mathrm {eff}\big (X_k \leftrightarrow \{X_1, \ldots , X_{k-1}\} \big ) - {k \over (k-1) d} \Big | \le {C\delta _n^{1/2} \over d} . \end{aligned}$$

Proof

We closely follow the proof of Theorem 3.4. For $i\ne j$ as in the beginning of that proof, we have by Corollary 3.3’that

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}\Big ( R_\mathrm {eff}(X_i \leftrightarrow X_j) \ge {2 + \sqrt{\delta _n} \over d} \Big ) = O(\delta _n^{1/2}) . \end{aligned}$$

By the union bound

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}\Big ( \exists i\ne j \in [k] \quad R_\mathrm {eff}(X_i \leftrightarrow X_j) \ge {2 + \sqrt{\delta _n} \over d} \Big ) = O(\delta _n^{1/2}) . \end{aligned}$$

Furthermore, since $X_i$ are stationary, by (25) and (27), with probability at least $1-O(\delta _n)$ the degrees of $X_1,\ldots ,X_k$ are all $(1+O(\delta _n))d(n)$, hence the resistance between any distinct pair is at least ${2-O(\delta _n) \over d}$. Furthermore, as before, the probability that $X_1,\ldots ,X_k$ are all distinct is $1-O(d^{-1})$ which is $1-O(\delta _n)$. We conclude that with probability at least $1-O(\delta _n^{1/2})$ for all $i,j\in [k]$ with $i\ne j$ we have

$$\begin{aligned} \Big | R_\mathrm {eff}(X_i \leftrightarrow X_j) - {2 \over d} \Big | \le {O(\delta _n^{1/2}) \over d} , \end{aligned}$$

from which Theorem 3.5 implies that desired result. $\square$

6.2 Proof of main theorem, extended version

In the proofs of the rest of this section we will need to discard undesirable T-compatible k-tuples such as those that have atypical vertex degrees. To that aim we introduce the following definitions. Recall that our convention is that the vertices [t] where $t<k$ are the vertices of T at graph distance at most $r-1$ from the root, while $\{t+1,\ldots , k\}$ are the vertices at graph distance precisely r from the root.

Definition 6.1

Let $\{G_n\}$ be a high degree almost regular graph sequence satisfying (25) and (26).

• (1) We say that a T-compatible k-tuple $(v_1,\ldots ,v_k)$ has typical degrees if

  $$\begin{aligned} (1-\delta _n) d(n) \le \deg (v_i)\le (1+\delta _n) d(n) \qquad \forall i \in [t] . \end{aligned}$$

• (2) We say that a T-compatible k-tuple $(v_1,\ldots ,v_k)$ which has typical degrees has typical neighbor degrees if for each $i \in [t]$ the number of neighbors of $v_i$ which have degree at least $(1-\delta _n) d(n)$ is at least $(1-\sqrt{\delta _n}) d(n)$.

• (3) We say that a T-compatible k-tuple $(v_1,\ldots ,v_k)$ is $\mathbf{good}$ if none of the vertices $v_1,\ldots ,v_t$ are incident to edges with resistance at least ${\delta _n^{-{1 \over 4(k-1)}} \over d}$ across them.

In the rest of this section all implicit constants in the O-notation depend on k.

Claim 6.2

Let T be a fixed rooted tree with k vertices, and $(X_1,\ldots ,X_k)$ be a T-compatible k-tuple drawn as described above Theorem 3.4’. Then with probability at least $1-O(\sqrt{\delta _n})$ the tuple $(X_1,\ldots ,X_k)$ has typical degrees and typical neighbor degrees. Also, with probability $1-O(\delta _n^{1/4(k-1)})$ it is good.

Proof

Since $X_i$ is distributed according to the stationary distribution for $i\in [t]$ it suffices to prove that $X_1$ satisfies the requirement of Definition 6.1 and use the union bound to obtain the desired result.

Indeed, firstly, by (25) and (27) we learn that with probability $1-O(\delta _n)$ the vertex $X_1$ has degree within $(1\pm \delta _n)d(n)$. Secondly, by Lemma 3.1’the probability that $X_1$ is not good is $O(\delta _n^{1/4(k-1)})$. Thirdly, denote by $V_1 \subset V(G_n)$ the set of vertices with degree within $(1\pm \delta _n)d(n)$ and by $V_2 \subset V_1$ the set of vertices in $V_1$ such that at least $(1-\sqrt{\delta _n})d(n)$ of their neighbors are in $V_1$. As before we have that ${{\,\mathrm{{\mathbb {P}}}\,}}(X_2 \in V_1) = 1-O(\delta _n)$. On the other hand,

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}(X_2 \in V_1 \mid X_1 \in V_1 \setminus V_2) \le 1 - O(\sqrt{\delta _n}) . \end{aligned}$$

Thus

$$\begin{aligned} 1-O(\delta _n) \le {{\,\mathrm{{\mathbb {P}}}\,}}(X_2 \in V_1) \le (1-O(\sqrt{\delta _n})) {{\,\mathrm{{\mathbb {P}}}\,}}(X_1 \in V_1 \setminus V_2) + 1 - {{\,\mathrm{{\mathbb {P}}}\,}}(X_1 \in V_1 \setminus V_2) , \end{aligned}$$

and we deduce that ${{\,\mathrm{{\mathbb {P}}}\,}}(X_1 \in V_1 \setminus V_2) = O(\sqrt{\delta _n})$ concluding the proof. $\square$

The corresponding analogue of Corollary 3.6 requires that we consider k-tuples having typical degrees.

Corollary 3.6′

Let $\{G_n\}$ be a high degree almost regular graph satisfying (25) and (26). Denote by N the number of k-tuples $(v_1,\ldots ,v_k)$ that are T-compatible, have typical degrees, and such that

$$\begin{aligned} \Big | R_\mathrm {eff}( v_k \leftrightarrow \{v_1,\ldots ,v_{k-1}\}) - {k \over (k-1) d} \Big | \ge {C \delta _n^{1/2} \over d} , \end{aligned}$$

where C is the constant from Theorem 3.4’. Then

$$\begin{aligned} N = O(\delta _n^{1/2} |V(G_n)| d^{k-1}) . \end{aligned}$$

Proof

For any T-compatible k-tuple $(v_1,\ldots ,v_k)$ that has typical degrees the probability that $(X_1,\ldots ,X_k)$ equals $(v_1,\ldots ,v_k)$ is ${1+O(\delta _n) \over |V(G_n)| d(n)^{k-1}}$. Furthermore, by Claim 6.2, the probability that $(X_1,\ldots ,X_k)$ have typical degrees is $1-O(\sqrt{\delta _n})$, hence the total number of T-compatible k-tuples that have typical degrees is $(1+O(\sqrt{\delta _n}))|V(G_n)| d^{k-1}$.

Lastly, by Claim 6.2 we learn that the assertion of Theorem 3.4’continues to hold when we condition on $(X_1,\ldots ,X_k)$ to have typical degrees and the desired assertion follows. $\square$

We may now proceed to the proof of the main theorem in the almost regular setting. We first state the analogue of Lemma 5.1.

Lemma of 5.1′

Let $\{G_n\}$ be a high degree almost regular graph satisfying (25) and (26). Then

$$\begin{aligned} {1 \over |V(G_n)|} \sum _{\begin{array}{c} (v_1,\ldots , v_k) \\ T{\mathrm{-compatible}} \\ \mathrm {good,\ typical\ degrees} \end{array}} \prod _{i=2}^k R_\mathrm {eff}(v_i \leftrightarrow \{v_1,\ldots , v_{i-1}\}) \le k + O(\delta _n^{1/4}) . \end{aligned}$$

(28)

Proof

We closely follow the proof of Lemma 5.1 and prove by induction on k. By Corollary 3.6’the number of T-compatible k-tuples $(v_1,\ldots ,v_k)$ for which

$$\begin{aligned} R_\mathrm {eff}(v_k \leftrightarrow \{v_1,\ldots ,v_{k-1}\}) \ge {k/(k-1) + C\sqrt{\delta _n} \over d} \end{aligned}$$

(29)

is $O(\delta _n^{1/2} |V(G_n)| d^{k-1})$. For such tuples, we bound each term in the product by ${\delta _n^{-1/4(k-1)} \over d}$. Thus we may bound the sum over such tuples (with the $|V(G_n)|^{-1}$ factor) from above by

$$\begin{aligned} O(\delta _n^{1/2} d^{k-1}) \times \Big ( {\delta _n^{-1/4(k-1)} \over d} \Big )^{k-1} = O(\delta _n^{1/4}) . \end{aligned}$$

For all other tuples we have the opposite inequality at (29). Thus we may bound the last term in the product by this, sum it over the at most $(1+\delta _n)d$ possible choices of $v_k$ and obtain that the left hand side of (28) is bounded above by

$$\begin{aligned} O(\delta _n^{1/4}) + {k+O(\sqrt{\delta _n}) \over k-1} {1 \over |V(G_n)|} \sum _{\begin{array}{c} (v_1,\ldots , v_{k-1}) \\ T\setminus \{v_k\}{\mathrm{-compatible}} \\ \mathrm {good,\ almost\ regular} \end{array}} \prod _{i=2}^{k-1} R_\mathrm {eff}(v_i \leftrightarrow \{v_1,\ldots , v_{i-1}\}) . \end{aligned}$$

We apply our induction hypothesis to the sum on the right hand side, collect the telescoping terms and get the desired result. $\square$

Proof of Theorem 1.4

Recall the definitions of the events $T(v_1,\ldots ,v_k)$ and $\lambda _T(v_1,\ldots ,v_k)$ from the proof of Theorem 1.2. We still have that

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}(B_{\Gamma _n}(X, r) \cong T) = {1 \over |V(G_n)| |\mathrm {Stab}_T|} \sum _{\begin{array}{c} (v_1,\ldots , v_k) \\ T{\mathrm{-compatible}} \end{array}} {{\,\mathrm{{\mathbb {P}}}\,}}( B_{\Gamma _n}(v_1, r) = T(v_1,\ldots ,v_k) ) . \end{aligned}$$

To proceed with the proof we need to discard a larger set of k-tuples than we did in the proof of Theorem 1.2 and to do so earlier. By Lemma 4.1 and Claim 6.2 the probability that $B(X,r)\cong T$ and $B(X,r-1)$ contains a vertex that is not of typical degree or not good or does not have typical neighbor degree is o(1). Thus,

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}(B_{\Gamma _n}(X, r) \cong T)&= {1 \over |V(G_n)| |\mathrm {Stab}_T|} \quad \sum _{\begin{array}{c} (v_1,\ldots , v_k) \\ T{\mathrm{-compatible}} \\ \text {good, typical degrees,} \\ \text {typical neighbor degrees} \end{array}} {{\,\mathrm{{\mathbb {P}}}\,}}( T(v_1,\ldots ,v_k) \subset \Gamma _n , \, \lambda _T(v_1,\ldots ,v_k) ) \\&+ o(1) . \end{aligned}$$

The analysis performed in the proof of Theorem 1.2 shows that for any T-compatible k-tuple $(v_1,\ldots ,v_k)$ that has typical degrees and typical neighbor degrees we have

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}( \lambda _T(v_1,\ldots ,v_k) \mid T(v_1,\ldots ,v_k) \subset \Gamma _n) \le (1+o(1)) {e^{-t} (k-t) \over k} . \end{aligned}$$

Since (23) holds, by Lemma 5.1’and the above we get that

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}(B_{\Gamma _n}(X, r) \cong T) \le {e^{-t}(k-t) \over |\mathrm {Stab}_T|} + o(1) . \end{aligned}$$

Now the same proof as in Theorem 1.2, below (24), can now be used verbatim, with the exception that Theorem 4.2’takes the role of Theorem 4.2. $\square$

6.3 Proof of Theorem 1.5

The proof by a second moment argument. By Theorem 1.4 we have that

$$\begin{aligned} {{\,\mathrm{{\mathbb {E}}}\,}}Y_n(T) = (1+o(1))\frac{|V(G_n) |T_r| e^{-|V(T)|+|T_r|}}{|\mathrm {Stab}_T|} . \end{aligned}$$

The second moment can be expressed as

$$\begin{aligned} {{\,\mathrm{{\mathbb {E}}}\,}}Y_n(T)^2 = \sum _{u,v\in V(G_n)} {{\,\mathrm{{\mathbb {P}}}\,}}(B_{\Gamma _n}(v,r)\cong T , B_{\Gamma _n}(u,r)\cong T) . \end{aligned}$$

We split the last sum to two according to whether the intersection $B_{\Gamma _n}(v,r) \cap B_{\Gamma _n}(u,r)$, viewed as a vertex subset, is empty or not. If the intersection is non-empty, then $u \in B_{\Gamma _n}(v,2r)$. Hence we bound

$$\begin{aligned} {{\,\mathrm{{\mathbb {E}}}\,}}Y_n(T)^2\le & {} \sum _{u,v} {{\,\mathrm{{\mathbb {P}}}\,}}(B_{\Gamma _n}(v,r)\cong T , B_{\Gamma _n}(u,r)\cong T , B_{\Gamma _n}(v,r) \cap B_{\Gamma _n}(u,r) = \emptyset )\nonumber \\&\quad + \sum _{v} {{\,\mathrm{{\mathbb {E}}}\,}}\big [ |B_{\Gamma _n}(v,2r)| \big ] . \end{aligned}$$

(30)

Theorem 4.2’immediately yields that the second term in (30) is $o(|V(G_n)|^2)$ so we focus on estimating the first sum of the above inequality. To that aim, we condition on $B_{\Gamma _n}(v,r)\cong T$ and on $B_{\Gamma _n}(v,r)$ itself. That is, in the terminology of the proof of Theorem 1.2, we condition the T-compatible k-tuple $(v_1,\ldots ,v_k)$ and on the edges $T(v_1,\ldots ,v_k)$ being in the UST $\Gamma _n$ and on the event $\lambda _T(v_1,\ldots ,v_k)$, i.e., that all edges touching $\{v_1,\ldots ,v_t\}$, except for those in $T(v_1,\ldots ,v_k)$, are not in $\Gamma _n$. Conditioned on this information, the UST $\Gamma _n$ restricted to the unconditioned edges is distributed as a UST on the graph obtained by $G_n$ by contracting the vertices $\{v_1,\ldots ,v_k\}$ to a single vertex and erasing edges touching $\{v_1,\ldots ,v_t\}$. Denote the resulting graph by $G_n'$.

It is not hard to verify that $G_n'$ is high degree almost regular. Indeed, since $G_n$ is simple, the degrees of all vertices of $G_n$ except $\{v_1,\ldots ,v_k\}$ have dropped by at most k. The degree of the conjoined vertex $\{v_1,\ldots ,v_k\}$ is at most kn and at least 1 and the total number of edges that were erased from $G_n$ is at most $t n = o(dn)$. Thus $G_n'$ satisfied Definition 6.1 perhaps with a slightly larger $\delta _n$ than the one of $G_n$, but still o(1). Denote by $\Gamma _n'$ the UST on $G_n'$. Then Theorem 1.4 gives

$$\begin{aligned} \sum _{u\in V(G_n')} {{\,\mathrm{{\mathbb {P}}}\,}}(B_{\Gamma _n'}(u,r)\cong T) = (1+o(1))\frac{|V(G_n)||T_r| e^{-|V(T)|+|T_r|}}{|\mathrm {Stab}_T|} . \end{aligned}$$

Therefore, the first sum in (30) is just $(1+o(1)) [ {{\,\mathrm{{\mathbb {E}}}\,}}Y_n(T) ] ^2$ while the second sum is $o({{\,\mathrm{{\mathbb {E}}}\,}}Y_n(T))$. We deduce that ${{\,\mathrm{{\mathbb {E}}}\,}}Y_n(T)^2 = (1+o(1)) [{{\,\mathrm{{\mathbb {E}}}\,}}Y_n(T)^2]$, or in other words, the variance of $Y_n(T)$ is $o([{{\,\mathrm{{\mathbb {E}}}\,}}Y_n(T)]^2)$ and the assertion of the theorem follows by Chebychev’s inequality. $\square$

7 Concluding remarks and open problems

7.1 Maximal diameter of the UST on regular graphs

The diameter of the UST, i.e., the maximal graph distance between two vertices, is the most natural “global” property of the UST. We cannot hope this quantity has a universal behavior only under the assumption of regularity. Indeed, the complete graph on $d+1$ vertices is a d-regular graph in which the diameter of the UST is of order $\sqrt{d}$. In fact, in [12] it shown that that the diameter of the UST on various “high-dimensional” (such as regular expanders, the hypercube and d-dimensional tori for $d>4$) is of order $\sqrt{|V(G)|}$.

On the other hand, take m disjoint copies $K_1,\ldots , K_m$ of complete graphs on $d+1$ vertices and for each $i\in [m]$ let $(x_i,y_i)$ be an edge of $K_i$. Add the edges $(y_i,x_{i+1})$ for each $i\in [m-1]$ to form the connected graph G—it is easily seen that the diameter of the UST on G is of order $n/\sqrt{d}$. (We remark that G is not regular, however, it is not difficult to make small changes to this construction to make it regular, we omit the details.) Our first question is whether this upper bound is best possible.

Question. Let $\{G_n\}$ be a sequence of simple, finite, connected d(n)-regular graphs with $d(n)\rightarrow \infty$. Let $D_n$ be the diameter of a UST of $G_n$. Does it hold that

$$\begin{aligned} {{\,\mathrm{{\mathbb {E}}}\,}}D_n = O\Big ({ |V(G_n)| \over \sqrt{d(n)}} \Big ) \qquad ? \end{aligned}$$

Remark 1

In [2] it is shown that if G is a simple, finite, connected graph with minimal degree $\Omega (n)$, then its diameter is $\Theta (\sqrt{n})$. This confirms the question above when d(n) is linear in $|V(G_n)|$.

Remark 2

Theorem 1.1 implies that with high probability that diameter of the UST in the setting of the question above is $o(|V(G_n)|)$. In fact, the following much more general statement can be made. We thank Jan Hladký for showing this to us.

Proposition 7.1

Let $\{G_n\}$ be a sequence of graphs with $|V(G_n)| \rightarrow \infty$ such that the uniform spanning tree $\Gamma _n$ of $G_n$ has a local limit $(\Gamma ,o)$ that almost surely has no bi-infinite paths. Then, for any fixed $\varepsilon >0$ one has

$$\begin{aligned} \lim _{n \rightarrow \infty } \,\,{{\,\mathrm{{\mathbb {P}}}\,}}\big ( D_n \ge \varepsilon V(G_n) \big ) = 0 , \end{aligned}$$

where $D_n$ is the diameter of $\Gamma _n$.

Proof

Assume by contradiction that there exists some fixed positive number $\varepsilon _1, \varepsilon _2$ such that for infinitely many $n's$ we have

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}\big ( D_n \ge \varepsilon _1 V(G_n) \big ) \ge \varepsilon _2 . \end{aligned}$$

By passing to a subsequence we may assume without loss of generality that this happens for every n. Let X be a uniform vertex of $G_n$. Then for any positive integer r, the probability that $B_{\Gamma _n}(X,r)$ contains two disjoint paths of length r emanating from X is at least $\varepsilon _2 (\varepsilon _1 - 2r /|V(G_n)|)$ which is at least $\varepsilon _1 \varepsilon _2/2>0$ when n is large enough. This contradicts the fact that $(\Gamma ,o)$ has no bi-infinite paths almost surely. $\square$

Corollary 7.2

The conclusion of Proposition 7.1 hold for any sequence $\{G_n\}$ of simple, finite, connected d(n)-regular graphs with $d(n)\rightarrow \infty$.

Proof

It is well-known that the Poisson(1) Galton–Watson tree conditioned to survive forever has no bi-infinite paths almost surely, see [10]. $\square$

7.2 Moments of degrees and graph distance balls

The average degree of a finite tree is at most 2 so ${{\,\mathrm{{\mathbb {E}}}\,}}\deg _{\Gamma _n}(X) \le 2$ where $\Gamma _n$ is a UST of some finite graph and X is a uniformly drawn vertex. What can be said about higher moments?

Without the assumption of regularity no higher moments are necessarily bounded as can be seen by taking a star on n vertices. In the class of regular graphs we have the following construction. Assume that d is a large even integer and consider d/2 disjoint copies of complete graphs on d vertices. From each complete graph remove an edge, add a new vertex to the graph and connect it to each complete graph with two edges to the two endpoints of the removed edges. In any spanning tree of this graph the degree of the special vertex must be at least d/2 and the probability that a uniform vertex is the special one is of order $d^{-2}$. Thus, the pth moment of the degree for any $p>2$ need not be bounded. However, we can use the techniques of this paper to show that the pth moment exists for any $p\in (1,2)$.

Lemma 7.3

There exists a constant $C<\infty$ such that for any finite connected regular graph G

$$\begin{aligned} {{\,\mathrm{{\mathbb {P}}}\,}}( \deg _\Gamma (X) \ge k ) \le {C \over k^2} , \end{aligned}$$

where $\Gamma$ is a UST of G and X is a uniformly drawn vertex.

Proof

Assume that $k\ge 16e$. By Lemma 3.1 there are no more than ${8e|V(G)| \over k}$ edges with effective resistance at least ${k \over 4ed}$ between their endpoints. So the number of vertices which touch at least k/2 such edges is at most ${32 e |V(G)| \over k^2}$. Hence the probability that X is such a vertex is at most ${32 e \over k^2}$. If X is not such a vertex and its degree is at least k, then there are at least k/2 edges that touch X which have effective resistance at most ${k \over 4ed}$ that are in the UST. The probability of this, by (9), is at most

$$\begin{aligned} {d \atopwithdelims ()k/2} (k/4ed)^{k/2} \le (2ed/k)^{k/2} (k/4ed)^{k/2} \le 2^{-k} , \end{aligned}$$

concluding the proof. $\square$

Question. Does there exist a constant C such that for any finite connected regular graph G one has ${{\,\mathrm{{\mathbb {E}}}\,}}\deg ^2_{\Gamma }(X) \le C$?

A very much related quantity is the size of the graph distance ball of radius r. In Theorem 4.2 we have proved that its size is tight. The case $r=1$ of this statement is trivial since $|B_\Gamma (X,1)| = \deg _\Gamma (X)$ and so their first moment is at most 2. When $r=2$ the question above about ${{\,\mathrm{{\mathbb {E}}}\,}}\deg ^2_\Gamma (X)$ is equivalent to asking whether ${{\,\mathrm{{\mathbb {E}}}\,}}|B_\Gamma (X,2)|$ is bounded. Indeed, it is easy to see by the mass transport principle [11, Chapter 8] that ${{\,\mathrm{{\mathbb {E}}}\,}}\deg ^2_\Gamma (X) = {{\,\mathrm{{\mathbb {E}}}\,}}|B_\Gamma (X,2)|$—(each vertex transports its degree in $\Gamma$ to all of its neighbors). The mean of $|B_\Gamma (X,3)|$ can already be unbounded—we leave this as an exercise to the reader.