Quantum Diffusion and Delocalization for Band Matrices with General Distribution

Introduction

The proof of quantum diffusion for general band matrices is considerably more involved than for matrices satisfying (1.1). Our proofs are based on an expansion in so-called nonbacktracking powers of $H$. As observed by Feldheim and Sodin , under the assumption (1.1) these powers satisfy a simple algebraic recursion relation which immediately implies that they are given by Chebyshev polynomials in $H$. In the language of perturbative quantum field theory, the nonbacktracking powers correspond to a self-energy renormalization up to all orders. The underlying algebraic identity, however, heavily relies on the special form (1.1). If (1.1) does not hold, the renormalization is no longer algebraically exact and the recursion relation becomes much more complicated. There are two main reasons for this complication. The first is that the absolute value of each matrix element is genuinely random, and hence powers of matrix elements $|H_{xy}|^{k}$ cannot be replaced by a constant. The second reason is that the variance $\sigma_{xy}^{2}$ is no longer given by a step function in $x-y$. These two complications give rise to different types of error terms that substantially increase the complexity of the Feynman graphs to be estimated. For instance if, instead of (1.1), we assumed

i.e. if the band were given by a step function, then our proof would be simpler (in the language of the graphical representation of Section 6, we would not have any wiggly lines).

We remark that some of the additional complications when considering ensembles more general than (1.1) have been tackled in and . In particular, Feldheim and Sodin, in Section III of , describe how to extend their result on the expectation value of traces of Chebyshev polynomials of Wigner matrices from (1.1) to more general distributions. In Section 9 of his paper on band matrices , Sodin states that the procedure of Section III of can be extended to band matrices satisfying the restriction (1.2), but no details are given. It seems, however, that $\sigma_{xy}^{2}$ being either a fixed constant or zero plays an important role. In this paper we consider more general band matrices (assuming less decay of the law of the matrix elements, and an arbitrary band shape), and we need to compute squares of matrix elements. Hence the structure of our expansion is more involved, and a novel approach is required to control it.

We remark that the restriction $\kappa<1/3$ needs to be imposed for several different reasons; see the discussion in Section 10.1. This restriction is natural and can also be understood as follows. If (i) we do not resum terms associated with different $n$ and $n^{\prime}$ (see (4.7) below), and (ii) we do not make systematic use of detailed heat kernel boundsAs explained in Section 11 of , this involves a refined classification of all skeleton graphs in terms of how much they deviate from the 2/3 rule (Lemma 7.7 in )., then our method must fail for $\kappa>1/3$. For otherwise we could prove, as in Section 11, that the largest eigenvalue of an $N\times N$ Wigner matrix is less than $2+N^{-2/3-\varepsilon}$ with high probability; this is known to be false.

We use the letters $C,c$ to denote arbitrary positive constants whose values are not important and may change from one equation to the next. They may depend on fixed parameters (such as $d$, $f$, $\alpha$, and $\beta$ defined below). We use $C$ for large constants and $c$ for small constants. For easy reference, we include a list of commonly used symbols and concepts in Appendix E.

Acknowledgements

We are grateful to a referee for suggesting improvements in the presentation as well as for pointing out some inaccuracies in a previous version of this manuscript.

The setup

We consider Hermitian (or symmetric) random band matrices $H^{\omega}\equiv H$ whose entries $H_{xy}$ are indexed by $x,y\in\Lambda_{N}$. Here $\omega\in\Omega$ denotes the element of a probability space $\Omega$. The entries $H_{xy}$ are always taken to be independent random variables, with the obvious restriction that $H_{yx}=\overline{H}\!\,_{xy}$.

Roughly speaking, we shall allow matrices $H$ whose variances

form a (doubly) stochastic matrix, such that the law of each matrix element $H_{xy}$ is symmetric.

for all $x,y$ and $\xi\geqslant 0$. In particular, we may consider Gaussian entries.

and assume that there is a $\eta>0$ such that

We also assume that the covariance matrix $\Sigma=(\Sigma_{ij})_{1\leqslant i,j\leqslant d}$ of $f$, defined by

Let $W$, $1\leqslant W\leqslant N$, be the band width, and define the family of standard deviations $\sigma_{xy}\geqslant 0$ through

as $W\to\infty$, uniformly for all $N\geqslant W$. In the following we make use of (2.6) without further comment. For notational convenience, we use both $W$ and $M$ in tandem. The definition of $H$ immediately implies that

for all $x$. Moreover, by symmetry of the law of $A_{xy}$, we have

whenever $n+m$ is odd. Finally, we assume that

Results

The quantity $\varrho(t,x)$ has the interpretation of the probability of finding a quantum particle at the lattice site $x$ at time $t$, provided it started from the origin at time . Here the time evolution of the quantum particle is governed by the Hamiltonian $H$. See for more details.

We consider time scales of order $M^{\kappa}$ where $\kappa<1/3$. Thus, we set

where $T\geqslant 0$ is a quantity of order one. We consider diffusive length scales in $x$, i.e. distances

Our main result generalizes Theorem 3.1 of to the class of band matrices with general distribution and covariance introduced in Section 2.

uniformly in $N\geqslant W^{1+d/6}$ and $0\leqslant T\leqslant T_{0}$. Here

where, we recall, $\Sigma$ is the covariance matrix (2.3) of the probability density $f$.

As a corollary of Theorem 3.1, we get delocalization of eigenvectors of $H$ on scales $W^{1+d\kappa/2}$. Indeed, the methods of , Section 10, imply that the localization length of the eigenvectors of $H$ is with high probability larger than the band width times $W^{d\kappa/2}$. See , Theorem 3.3 and Corollary 3.4, for a precise statement as well as a proof.

Our methods also yield a new bound on the largest eigenvalue of a band matrix. This bound is in fact valid for a larger class of random matrices, for which the spatial structure and dimensionality are irrelevant.

Let the $N\times N$ matrix $A$ be as in Section 2, and take a family $\{\sigma_{xy}^{2}\}_{x,y=1}^{N}$ of variances that satisfy (2.7). Define

and set $H_{xy}\mathrel{\mathop{:}}=\sigma_{xy}A_{xy}$ . Then there is a constant $c>0$ such that for any $\varepsilon$ satisfying $0<\varepsilon<2/3$ we have

We stress here that the condition (2.9) applies to Theorem 3.1 only, and is not imposed in Theorem 3.4.

The rest of this paper is devoted to the proof of Theorem 3.1, with the exception of Section 11 which contains the proof of Theorem 3.4.

Summary of the Chebyshev expansion from [1]

For the following, we fix $T\geqslant 0$; the claimed uniformity on compacts is a trivial consequence of our analysis and we shall not mention it any more. For notational convenience, we often abbreviate

The starting point of our proof is the same as in , i.e. the Chebyshev expansion of the propagator,

Here $U_{n}$ denotes the $n$-th Chebyshev polynomial of the second kind, defined through

For our purposes it is more convenient to work with the rescaled polynomials $\widetilde{U}_{n}(\xi)\mathrel{\mathop{:}}=U_{n}(\xi/2)$. They satisfy the recursion relation

where $J_{n}(t)$ is the $n$-th Bessel function of the first kind. We shall need the following basic estimates on $\alpha_{n}(t)$; see , Equations (5.4) and (7.14). We have the bound

Using the Chebyshev expansion (4.1) we may write

The expansion (4.7) is the starting point of our analysis.

Truncations

We begin the proof of Theorem 3.1 by introducing a series of truncations in the expansion (4.7). First, we truncate in the lattice size $N$ by showing that the error we make by assuming $N\leqslant W^{C}$ is negligible (see (5.2)). Second, we use the subexponential decay of the matrix elements of $A$ to cut off $\lvert A_{xy}\rvert$ at scales $M^{\delta}$ for an arbitrary $\delta>0$. Third, we introduce a cutoff in the summation over $n$ and $n^{\prime}$ in (4.7); this will prove necessary because the combinatorial estimates for the right-hand side of (4.7) that we shall derive in Sections 8 – 10 deteriorate for very large $n$ and $n^{\prime}$.

We replace the matrix $H$ with a truncated matrix $\widehat{H}$, whereby we truncate in both the size of the lattice and the support of the distribution of the matrix entries. Both truncations are made possible by the following estimate on the speed of propagation of $H$.

Let \widetilde{N}\equiv\widetilde{N}(W)=\min\bigl{(}{W^{10d+16},N}\bigr{)} and introduce the truncated Hamiltonian $\widetilde{H}$ defined by

Then there is a constant $C>0$ such that, for all $t\leqslant M$ we have

where $\alpha$ is the constant from (2.1).

In a first step we truncate the lattice size $N$. Defining

Then the absolute value of (5.1) is equal to

where we used that $H$ and $\widetilde{H}$ are Hermitian, and $\lVert E\rVert\leqslant C$. Using Proposition 5.1 we therefore conclude that (5.1) vanishes as $W\to\infty$, uniformly for $t\leqslant M$. Note that the matrix $a(W,N)\widetilde{H}$, where $a(W,N)\mathrel{\mathop{:}}=\frac{M(W,N,f)}{M(W,\widetilde{N},f)}$, satisfies (2.7). Since $\lim_{W\to\infty}a(W,N)=1$, is is enough to prove Theorem 3.1 for the matrix $a(W,N)\widetilde{H}$ (it is straightforward to check that replacing $T$ with $a(W,N)T$ in our proof has no effect).

We conclude that it is enough to prove Theorem 3.1 for

We shall always assume (5.2) from now on.

In a second step we truncate the support of the entries of $A$. Let $\delta$ satisfy

and define the matrix $\widehat{A}$ through

In following we adopt the convention that adding a hat $\widehat{(\cdot)}$ to a quantity $(\cdot)$ means that in the definition of $(\cdot)$ we replace $A$ with $\widehat{A}$. In particular, we set

By the uniform subexponential decay of the entries (2.1), we have

It is now easy to prove the main result of this subsection.

Using the bound $\lvert\varrho(t,x)\rvert\leqslant 1$, (5.5), and (5.2) we find

Note that, by the definition (5.4), the law of $\widehat{A}_{xy}$ is symmetric. In particular, $\widehat{H}$ satisfies (2.8). Moreover, we have the following bounds on the variance of $\widehat{H}_{xy}$.

There is a constant $C$ independent of $x$ and $y$ such that

The upper bound is obvious from (5.4). In order to prove the lower bound, we write

3 The tail of the expansion

As observed in , the coefficient $\alpha_{n}(t)$ is very small for $n\gg t$. Thus, we choose a cutoff exponent $\mu$ satisfying

The key ingredient for controlling the tail, i.e. the terms $n+n^{\prime}\geqslant M^{\mu}$ in (5.6), is the following a priori estimate on the norm of $\widehat{H}$.

There are constants $C,\varepsilon>0$, depending on $\delta$, such that

Split $\widehat{\varrho}_{b}(t,x)=\widehat{\varrho}_{b,\leqslant}(t,x)+\widehat{\varrho}_{b,>}(t,x)$ by splitting the summation over $n,n^{\prime}$ in (5.8) into the parts $n+n^{\prime}\leqslant M^{\mu}$ and $n+n^{\prime}>M^{\mu}$.

We now estimate $\sum_{x}\lvert\widehat{\varrho}_{b,>}(W^{d\kappa}T,x)\rvert$. To this end, we use the following rough estimate on Chebyshev polynomials.

The recursion relation (4.3) combined with a simple induction argument shows that the coefficients of $\widetilde{U}_{n}$ are bounded in absolute value by $2^{n}$. This implies that

Let us now consider the main term $\widehat{\varrho}_{b,\leqslant}(t,x)$. In order to get a graph expansion scheme from (2.8), we need to get rid of the conditioning on the norm of $\widehat{H}$, i.e. recover the expression

The expectation is estimated, using Lemma 5.5, by

where in the last step we used the trivial bound

Thus, using (4.6), (5.2), and Proposition 5.4, we find

The following proposition summarizes our results from this section. It shows that on time scales $t\lesssim W^{d\kappa}$, instead of the original density $\varrho(x,t)$ defined in (3.1) it will be sufficient to deal with the density $\widehat{\varrho}_{\leqslant}(x,t)$ of the truncated dynamics defined in (5.10). In the rest of the paper we shall work with $\widehat{\varrho}_{\leqslant}(x,t)$.

for some $c>0$, where $\widehat{\varrho}_{\leqslant}$ is defined in (5.10).

Proposition 5.6 is an immediate consequence of Proposition 5.2 and the equations (5.3), (5.9), and (5.11). ∎

Note moreover that in the definition (5.10) the sum ranges only over indices $n$ and $n^{\prime}$ such that $n+n^{\prime}$ is even. This follows from the fact that $U_{n}$ is odd (even) for odd (even) $n$, and that $\widehat{H}$ satisfies the moment condition (2.8).

The path expansion

In this section we develop a graphical expansion to compute the matrix elements of $\widetilde{U}_{n}(\widehat{H})$ needed to evaluate $\widehat{\varrho}_{\leqslant}(x,t)$; see (5.10). The result of this expansion is summarized in Proposition 6.7, which expresses $\widetilde{U}_{n}(\widehat{H})$ as a sum over graphs. The main idea is that, thanks to the special properties of the Chebyshev polynomials, we can express $\widetilde{U}_{n}(\widehat{H})$ in terms of nonbacktracking powers of $\widehat{H}$, up to some error terms. The nonbacktracking powers make it easier to identify the main terms and the error terms in the computation of the expectation in (5.10). The expectation will be computed in Section 7 by introducing an additional structure, the lumping of edges, to the graphical representation. Eventually, the main terms will correspond to certain very simple graphs with a trivial lumping (ladders) and their contribution yields the final limiting equation (Section 8). The contribution of all other nontrivial graphs or nontrivial lumpings will be negligible in the $W\to\infty$ limit; the estimate of these error terms constitutes the rest of the paper.

(Note that in (4.1) $U_{n}=U_{n}(\xi)$ denoted the standard Chebyshev polynomials, but for the rest of the paper we shall use $U_{n}$ to denote the matrix $\widetilde{U}_{n}(\widehat{H})$.) Thus we have

Next, for $n\geqslant 2$ we define $V_{n}$ as the $n$-th nonbacktracking power of $\widehat{H}$, i.e.

where in (6.2a) we used (2.7). Moreover, we introduce the shorthand $\underline{\Phi_{3}V_{n}}\!\,$, defined by

we use the convention that $\underline{\Phi_{3}V_{0}}\!\,=\Phi_{3}$.

The expressions for $V_{0},V_{1},V_{2}$ are easy to derive from the definition of $V_{n}$. Moreover, for $n\geqslant 3$ we find

We may now derive the path expansion of $U_{n}$. To streamline notation, it is convenient to define $\underline{\Phi_{2}V_{n}}\!\,\mathrel{\mathop{:}}=\Phi_{2}V_{n}$.

It is easy to see from (6.1) and Lemma 6.1 that

using a simple induction argument. The cases $n=0,1,2$ are trivial. Assuming the claim holds up to $n-1$, we get from (6.5)

where in the last step we used Lemma 6.1. Thus (6.6) is proved.

Finally, (6.4) is an immediate consequence of (6.6). ∎

2 Graphical representation

The path expansion (6.4) is the key algebraic identity of our proof. We now introduce a graphical representation of (6.4) by associating a rooted tree graph $G$ with each summand in (6.4).

Before giving a precise definition of our graphs, we outline how they arise from (6.4). A matrix element $\widehat{H}_{x_{0}x_{1}}$ is represented by two vertices, and $1$. To each vertex $v$ we assign a label $x_{v}\in\Lambda_{N}$. Matrix multiplication is represented by concatenating such edges. Thus, $\widehat{H}_{x_{0}x_{1}}\cdots\widehat{H}_{x_{n-1}x_{n}}$ is represented as a sequence of vertices $0,\dots,n$ joined by $n$ edges. The root is always the leftmost vertex, and the edges are directed away from the root. If two neighbouring vertices $u,w$ of a vertex $v$ are constrained to have different labels (the nonbacktracking condition), we draw $v$ using a black dot; otherwise, we draw $v$ using a white dot. A factor $\Phi_{2}$ gives rise to a directed edge, represented by a slashed double line, whose final vertex is “dangling” in the sense that it has degree one. A factor $\Phi_{3}$ is represented by a wiggly edge. See Figure 6.1 for an illustration of these rules.

Using these graphical building blocks we may conveniently represent any summand of (6.4). See Figure 6.2 for an example.

3 Definition of graphs

We now give a precise definition of a set of graphs that is sufficiently general for our purposes. Let $G$ be a finite, oriented, unlabelled, rooted tree. We denote by $\mathcal{V}(G)$ the set of vertices of $G$, by $\mathcal{E}(G)$ the set of edges of $G$, and by $a(G)\in\mathcal{V}(G)$ the root of $G$. That $G$ is oriented means that $G$ is drawn in the plane, and the edges incident to any vertex are ordered. (Thus, each edge $e$ adjacent to a vertex $v$ has a successor, defined as the next edge adjacent to $v$ counting anticlockwise from $e$.) In particular, two graphs are considered different even if they are isomorphic in the usual graph-theoretical sense but the ordering of the edges at some vertex differs. This notion of orientation can be formalized using Dick paths (see e.g. , Chapter 1). Such a formal definition is not necessary for our purposes however.

The choice of a root $a(G)$ implies that we may view $G$ as a directed graph, whereby edges are directed away from the root. Thus we shall always regard an edge $e=(v,w)$ as an ordered pair of vertices. Given an edge $e=(v,w)\in\mathcal{E}(G)$, we denote by $a(e)=v$ the initial vertex of $e$ and by $b(e)=w$ the final vertex of $e$.

There is a natural notion of distance between vertices: For $v,w\in\mathcal{V}(G)$ we set $d(v,w)$ to be equal to the number of edges in the shortest path from $v$ to $w$. Each vertex $v\neq a(G)$ has a parent $w$, defined as the unique vertex adjacent to $v$ and satisfying $d(a(G),w)=d(a(G),v)-1$. If $w$ is the parent of $v$ we also say that $v$ is a child of $w$. Similarly, if an edge $e$ is not incident to $a(G)$, we call the (unique) edge $e^{\prime}$ satisfying $a(e)=b(e^{\prime})$ the parent of $e$; in this case we also call $e$ a child of $e^{\prime}$.

We require that $G$ have an additional distinguished vertex $b(G)\in\mathcal{V}(G)$, which need not be different from $a(G)$. The path connecting $a(G)$ to $b(G)$ is called the stem of $G$, and denoted by $\mathcal{S}(G)$. When drawing $G$ in the plane, we draw the stem as a horizontal path from $a(G)$ at its left edge to $b(G)$ at its right edge. We require that all edges not belonging to the stem lie above it (see Figure 6.3). Ultimately, the vertices $a(G)$ and $b(G)$ will receive the fixed labels $x_{a(G)}=x$ and $x_{b(G)}=y$ in the graphical expansion of the matrix element $(U_{n})_{xy}$.

We denote the set of such graphs by $\mathfrak{W}$. We call an edge $e\in\mathcal{E}(G)$ a stem edge if it belongs to $\mathcal{E}(\mathcal{S}(G))$, and a bough edge otherwise. If $G$ has no bough edges, we call it a bare stem. A bare stem is uniquely determined by its number of edges.

Thus, a graph $G\in\mathfrak{W}$ consists of a stem and a collection of rooted trees, called boughs. Each bough is directed away from its root vertex, which belongs to the stem $\mathcal{S}(G)$. We abbreviate with $\mathcal{B}(G)$ the subgraph of $G$ consisting of all bough edges. We call a bough edge $e\in\mathcal{E}(\mathcal{B}(G))=\mathcal{E}(G)\setminus\mathcal{E}(\mathcal{S}(G))$ a leaf if $b(e)$ has degree one. See Figure 6.3 for an example of a graph in $\mathfrak{W}$.

Next, we decorate graphs $G\in\mathfrak{W}$ as follows. First, we tag the edges, i.e. we choose a map $\tau_{G}$ on $\mathcal{E}(G)$, called a tagging, with values in the set of tags

Here $s$ stands for “stem” and $b$ for “bough”. We require that the tag $\tau_{G}(e)$ be of the form $(s,i)$ if $e\in\mathcal{E}(\mathcal{S}(G))$ and of the form $(b,i)$ otherwise. The index $i$ (taking values in $\{0,1\}$ for stem edges and $\{0,\dots,4\}$ for bough edges) is used to tag different types of edges. Edges whose tag is $(s,0)$ or $(b,0)$ are called large; other edges are called small. The reason for this nomenclature lies in the magnitude of their contribution to the value of the graph after taking the expectation; see Section 9. Second, we choose a symmetric map $l_{G}:\mathcal{V}(G)^{2}\to\{0,1\}$ which will be used to encode all nonbacktracking conditions on $G$. The idea is that $l_{G}(v,w)=1$ induces a constraint $x_{v}\neq x_{w}$ on the labels. We require that $l(v,w)=0$ unless $d(v,w)=2$. We call the triple $(G,\tau_{G},l_{G})$ a decorated graph, and denote the set of decorated graphs by $\mathfrak{G}$.

Next, we associate a value $\mathfrak{V}_{xy}(\mathcal{G})$ with each decorated graph $\mathcal{G}\in\mathfrak{G}$. The value $\mathfrak{V}_{xy}(\mathcal{G})$ is a random variable that depends on two labels $x,y\in\Lambda_{N}$. For the following we fix $\mathcal{G}=(G,\tau_{G},l_{G})$. We shall assign a label $x_{v}\in\Lambda_{N}$ to each vertex $v\in\mathcal{V}(G)$ in such a way that $x=x_{a(G)}$ and $y=x_{b(G)}$. To define $\mathfrak{V}_{xy}(G)$ we first assign a polynomial in the matrix entries to each edge. Let $e\in\mathcal{E}(G)$ and abbreviate $x_{0}=x_{a(e)}$ and $x_{1}=x_{b(e)}$. We associate a polynomial $P_{\tau_{G}(e)}(\widehat{H}_{x_{0}x_{1}},\widehat{H}_{x_{1}x_{0}})$, and a degree $\deg_{\tau_{G}}(e)\equiv\deg(e)$, with $e$ according to the following table.

Note that $\deg(e)$ is nothing but the degree of the polynomial $P_{\tau_{G}(e)}$. The degree of $\mathcal{G}$ is

We call a stem vertex $v\in\mathcal{V}(\mathcal{S}(G))\setminus\{a(G),b(G)\}$ nonbacktracking if the two stem edges adjacent to $v$, $(u,v)$ and $(v,w)$, satisfy $l_{G}(u,w)=1$; according to (6.9), this means that we have the constraint $x_{u}\neq x_{w}$. Otherwise we call $v$ backtracking. We call the stem $\mathcal{S}(G)$ completely nonbacktracing if all vertices in $\mathcal{V}(\mathcal{S}(G))\setminus\{a(G),b(G)\}$ are nonbacktracking. Decorated graphs $(G,\tau_{G},l_{G})\in\mathfrak{G}$ are represented graphically as follows. Each edge of $G$ is drawn using a decoration that identifies its tag $\tau_{G}(e)$; see Figure 6.4. (Note that, although Figure 6.4 suggests that decorated bough edges are double, they are in fact single. This graphical representation using double lines is chosen in the light of the graph operations $\mathcal{F}_{n}$, $\mathcal{F}_{c}$, and $\mathcal{R}$ defined below.) Non-backtracking stem vertices are drawn with a black dot; other vertices are drawn with a white dot. Note that using black and white dots to draw the vertices displays only partial information about $l_{G}$: Only nonbacktracking restrictions pertaining to pairs of vertices both in the stem are indicated in our graphical representation.

See Figure 6.5 for an example of a decorated graph.

4 Operations on graphs

As it turns out, in order to control the graph expansion we shall have to make all stem vertices apart from $a(G)$ and $b(G)$ nonbacktracking. To this end, we introduce two operations, $\mathcal{F}_{n}$ and $\mathcal{F}_{c}$, on the set of decorated graphs $\mathfrak{G}$. We shall prove that after a finite number of successive applications of either $\mathcal{F}_{n}$ or $\mathcal{F}_{c}$ to an arbitrary decorated graph, we always get a graph with a completely nonbacktracking stem. The index $n$ stands for “nonbacktracking” and $c$ for “collapsing”. The idea behind the definition of $\mathcal{F}_{n}$ and $\mathcal{F}_{c}$ is to choose the first (in the natural order of $\mathcal{S}(G)$) backtracking stem vertex $v_{1}\in\mathcal{V}(\mathcal{S}(G))\setminus\{a(G),b(G)\}$ and introduce a splitting in the definition (6.9) using

where the vertices $v_{0},v_{2}\in\mathcal{V}(\mathcal{S}(G))$ are the neighbours of $v_{1}$ in the stem, i.e. they satisfy $(v_{0},v_{1}),(v_{1},v_{2})\in\mathcal{E}(\mathcal{S}(G))$.

We now define $\mathcal{F}_{n}$ and $\mathcal{F}_{c}$ more precisely. If $\mathcal{S}(G)$ has no backtracking vertex, set $\mathcal{F}_{n}(\mathcal{G})\mathrel{\mathop{:}}=\mathcal{G}$ and $\mathcal{F}_{c}(\mathcal{G})\mathrel{\mathop{:}}=\emptyset$, where $\emptyset$ is the empty graph satisfying $\mathfrak{V}_{xy}(\emptyset)\mathrel{\mathop{:}}=0$.

Otherwise, let $v_{1}$ be the first backtracking vertex in $\mathcal{V}(\mathcal{S}(G))\setminus\{a(G),b(G)\}$ and define $v_{0}$ and $v_{2}$ as above. Then we set $\mathcal{F}_{n}(\mathcal{G})\mathrel{\mathop{:}}=(G,\tau_{G},\widetilde{l}_{G})$, where

Thus, the operation $\mathcal{F}_{n}$ simply makes the vertex $v_{1}$ a nonbacktracking vertex of $\mathcal{S}(G)$ without changing $G$ or $\tau_{G}$, i.e. it sets $\widetilde{l}_{G}(v_{0},v_{2})=\widetilde{l}_{G}(v_{2},v_{0})=1$ and leaves $\widetilde{l}_{G}$ unchanged for any other pair of vertices.

Next, we define $\mathcal{F}_{c}$. Let $v_{0},v_{1},v_{2}$ be as above. The operation $\mathcal{F}_{c}$ collapses the two nearest stem neighbours, $v_{0}$ and $v_{2}$, of $v_{1}$ into one vertex and fuses the two edges $(v_{0},v_{1})$ and $(v_{1},v_{2})$ into one edge (see Figure 6.6). This definition is very natural in the light of Figure 6.6 and our choice of conventions for drawing bough edges as double lines. Thus, a reader who believes his eyes when gazing at pictures like Figure 6.6 may safely skip the following two paragraphs.

To define the operation $\mathcal{F}_{c}$ precisely, we identify $v_{0}$ with $v_{2}$, i.e. introduce the equivalence classes

Define the graph $\widetilde{G}$ through its vertex set $\mathcal{V}(\widetilde{G})=\{[v]\,:\,v\in\mathcal{V}(G)\}$, and its edge set, which is obtained as follows. Each edge $(v,w)\in\mathcal{E}(G)\setminus\{(v_{1},v_{2})\}$ gives rise to the edge $([v],[w])\in\mathcal{E}(\widetilde{G})$. Thus, the edges $(v_{0},v_{1})$ and $(v_{1},v_{2})$ are fused into a single edge $([v_{0}],[v_{1}])$. The tag \tau_{\widetilde{G}}\bigl{(}{([v],[w])}\bigr{)} is by definition equal to the tag \tau_{G}\bigl{(}{(v,w)}\bigr{)} if $(v,w)\neq(v_{0},v_{1})$; the tag of the edge $([v_{0}],[v_{1}])$ is defined by the following table.

The initial and final vertices of $\widetilde{G}$ are given by $a(\widetilde{G})\mathrel{\mathop{:}}=[a(G)]$ and $b(\widetilde{G})\mathrel{\mathop{:}}=[b(G)]$. The edges of $\widetilde{G}$ are oriented in the natural way when drawing $G$ and $\widetilde{G}$ in the plane; instead of giving a formal definition of the orientation, we refer to Figure 6.6.

Finally, we define the map $l_{\widetilde{G}}$, which encodes the nonbacktracking information of $\widetilde{G}$, through

Thus, in the graphical representation of $\mathcal{F}_{c}(\mathcal{G})\mathrel{\mathop{:}}=(\widetilde{G},\tau_{\widetilde{G}},l_{\widetilde{G}})$, the vertex $[v_{0}]=[v_{2}]$ is always white (i.e. backtracking). Note that if $v_{0}$ or $v_{2}$ was nonbacktracking, this restriction remains encoded in the map $l_{\widetilde{G}}$, but is no longer visible in the colouring of the vertices.

We summarize the key properties of $\mathcal{F}_{n}$ and $\mathcal{F}_{c}$, which follow immediately from their construction.

Let $\mathcal{G}\in\mathfrak{G}$. Then $\mathcal{F}_{n}(\mathcal{G}),\mathcal{F}_{c}(\mathcal{G})\in\mathfrak{G}$. Moreover,

5 Graphs with completely nonbacktracking stem

Next, we introduce two special subsets of decorated graphs. We define $\mathfrak{G}^{\prime}\subset\mathfrak{G}$ to be the set of decorated graphs corresponding to terms in (6.4). See Figure 6.2 for an example. More precisely:

The set $\mathfrak{G}^{\prime}$ is the subset of $(G,\tau_{G},l_{G})\in\mathfrak{G}$ satisfying

All boughs of $G$ contain only one edge, whose tag is $(b,1)$;

$l_{G}(u,w)=1$ if and only if there is a vertex $v$ that is not the root of a bough, such that $(u,v),(v,w)\in\mathcal{E}(\mathcal{S}(G))$ with \tau_{G}\bigl{(}{(v,w)}\bigr{)}=(s,0).

Property (ii) says that all bough vertices (including the bough roots) are white, and that the left vertex of a wiggly edge is white. The remaining vertices (apart from $a(G)$ and $b(G)$) are black. It is easy to see that the graphs associated with terms on the right-hand side of (6.4) belong to $\mathfrak{G}^{\prime}$

Note that, unlike in the case of a general graph $\mathcal{G}\in\mathfrak{G}$, the nonbacktracking information of a graph $\mathcal{G}\in\mathfrak{G}^{\prime}$ is fully encoded in the colouring of its vertices. Indeed, $l_{G}(v,w)$ can only be $1$ if $v,w\in\mathcal{V}(\mathcal{S}(G))$. Moreover, from (ii) we see that $l_{G}$ is uniquely determined by $G$ and $\tau_{G}$. Thus, a decorated graph $\mathcal{G}=(G,\tau_{G},l_{G})\in\mathfrak{G}^{\prime}$ is uniquely determined by its graph and tagging, i.e. the pair $(G,\tau_{G})$.

The second important subset of decorated graphs is generated from $\mathfrak{G}^{\prime}$ by applying the operations $\mathcal{F}_{n},\mathcal{F}_{c}$ to decorated graphs in $\mathfrak{G}^{\prime}$ until the stem is completely nonbacktracking, i.e. all stem vertices (apart from $a(G)$ and $b(G)$) are black.

For $\mathcal{G}\in\mathfrak{G}^{\prime}$ we define $\mathscr{B}_{\mathcal{G}}$ as the set of decorated graphs $\widetilde{\mathcal{G}}\in\mathfrak{G}$ whose stem is completely nonbacktracking and that are obtained from $\mathcal{G}$ by a finite number of operations $\mathcal{F}_{n}$ and $\mathcal{F}_{c}$. Furthermore we set

The set $\mathfrak{G}_{\sharp}$ is the set of “good” graphs that we shall work with in later sections. Thus, given a graph $\mathcal{G}\in\mathfrak{G}^{\prime}$ corresponding to a summand of (6.4), we first transform it into the family $\mathscr{B}_{\mathcal{G}}$ of graphs in $\mathfrak{G}_{\sharp}$. The contribution of $\mathcal{G}$ to the expansion (6.4) is given by the sum of the contributions of all graphs in $\mathscr{B}_{\mathcal{G}}$ (see (6.10) below). We then exploit the fact that we have good estimates on the contributions of graphs with completely nonbacktracking stems.

Next, we state and prove the key properties of the set $\mathfrak{G}_{\sharp}$ and the operations $\mathcal{F}_{n}$ and $\mathcal{F}_{c}$.

If $(G,\tau_{G},l_{G})\in\mathfrak{G}_{\sharp}$ then all leaves of $G$ are small (in $\tau_{G}$).

If $(G,\tau_{G},l_{G})\in\mathfrak{G}_{\sharp}$ and $e\in\mathcal{E}(G)$ has tag $\tau_{G}(e)=(b,1)$, then $e$ is a leaf of $G$.

If $\mathcal{G}\neq\mathcal{G}^{\prime}\in\mathfrak{G}^{\prime}$ then $\mathscr{B}_{\mathcal{G}}\cap\mathscr{B}_{\mathcal{G}^{\prime}}=\emptyset$.

For any $\mathcal{G}\in\mathfrak{G}^{\prime}$ and $\widetilde{\mathcal{G}}\in\mathscr{B}_{\mathcal{G}}$ we have $\deg(\mathcal{G})=\deg(\widetilde{\mathcal{G}})$.

For each $\mathcal{G}\in\mathfrak{G}^{\prime}$ we have

The key ingredient of the proof is the following ripping operation, denoted by $\mathcal{R}$. It provides a link between the sets $\mathfrak{G}_{\sharp}$ and $\mathfrak{G}^{\prime}$, and is essentially the converse of multiple applications of $\mathcal{F}_{n}$ and $\mathcal{F}_{c}$. The idea is to take hold of the vertices $a(G)$ and $b(G)$ of a given tagged graph $(G,\tau_{G})$ and “pull them apart”, thus “ripping open” all bough edges of $\mathcal{G}$ except those of type $(b,1)$. When interpreted graphically, the character of each edge (straight or wiggly) is kept unchanged, whereby the double edge of a bough edge is split into two single edges.

When defining $\mathcal{R}$ it is convenient, in a first step, to “rip open” all bough edges (including those of type $(b,1)$) of $(G,\tau_{G})$; we shall call the resulting tagged graph $\mathcal{P}(G,\tau_{G})$. In a second step, we undo the ripping of all bough edges of type $(b,1)$, which results in the tagged graph $\mathcal{R}(G,\tau_{G})$.

In order to define $\mathcal{P}$, we need one additional tag $(s,2)$ for stem edges, which we draw with a single solid line that is slashed. Stem edges of type $(s,2)$ result from the ripping open of a bough edge of type $(b,1)$. By walking around $G$, we associate with the tagged graph $(G,\tau_{G})$ a tagged bare stem $(\widetilde{G},\tau_{\widetilde{G}})=\mathrel{\mathop{:}}\mathcal{P}(G,\tau_{G})$. More precisely, we draw $G$ in the plane, and start at the vertex $a(G)$. At each step, we move along one edge of $G$ in such a way that we always remain to the left of $G$; see Figure 6.7. Every stem edge is travelled once, and every bough edge twice. Each time we move along an edge $e\in\mathcal{E}(G)$, we add an edge $\widetilde{e}$ to the stem $\widetilde{G}$. Depending on whether we moved along $e$ in the direction of $e$ (denoted by $+$) or against the direction of $e$ (denoted by $-$), we associate a tag $\tau_{\widetilde{G}}(\widetilde{e})$ with $\widetilde{e}$ according to the following table.

These rules are made obvious by a glance at Figure 6.4; indeed, a tagged bough edge is represented with a double line which corresponds exactly to the two single lines resulting from ripping the bough edge open. Figure 6.9 provides an example of the operation $(G,\tau_{G})\mapsto\mathcal{P}(G,\tau_{G})$. The map $\mathcal{P}$ can also be interpreted as first doubling all bough edges according to their tags, and ripping them open successively by pulling the edges $a(G)$ and $b(G)$ apart; see Figure 6.8.

We now define $\mathcal{R}(G,\tau_{G})=\mathcal{G}^{\prime}$ to be the unique decorated graph $\mathcal{G}^{\prime}=(G^{\prime},\tau_{G^{\prime}},l_{G^{\prime}})\in\mathfrak{G}^{\prime}$ that satisfies $\mathcal{P}(G,\tau_{G})=\mathcal{P}(G^{\prime},\tau_{G^{\prime}})$; see Figure 6.9. That there is exactly one such $\mathcal{G}^{\prime}\in\mathfrak{G}^{\prime}$ follows immediately from the definitions of $\mathcal{P}$ and $\mathfrak{G}^{\prime}$, as well as the fact that $l_{G^{\prime}}$ is uniquely determined by the pair $(G^{\prime},\tau_{G^{\prime}})$ through Definition 6.4 (ii). (Thus, the operation $\mathcal{P}$ plays only an auxiliary role, its sole purpose being to clarify the definition of $\mathcal{R}$.)

Having defined the ripping operation $\mathcal{R}$, we are now ready to prove Claim (i) of the Proposition. Before giving the full proof we outline the strategy. First, for any $\mathcal{G}=(G,\tau_{G},l_{G})\in\mathfrak{G}_{\sharp}$ we construct the ripped graph $\mathcal{R}(G,\tau_{G})\in\mathfrak{G}^{\prime}$, which does not depend on $l_{G}$. Second, by definition of $\mathfrak{G}^{\prime}$, the ripped graph $\mathcal{G}^{\prime}=\mathcal{R}(G,\tau_{G})$ bears a unique nonbacktracing map $l_{G^{\prime}}$. Third, by definition of $\mathfrak{G}_{\sharp}$, there is a sequence $i_{1},\dots,i_{k}\in\{n,c\}$ such that $\mathcal{G}=(G,\tau_{G},l_{G})=(\mathcal{F}_{i_{k}}\circ\cdots\circ\mathcal{F}_{i_{1}})(\mathcal{R}(G,\tau_{G}))$. Fourth, we prove that this representation is unique. Thus we have expressed $l_{G}$ as a function of $(G,\tau_{G})$.

Now to the proof of (i). Let $\mathcal{G}=(G,\tau_{G},l_{G})\in\mathfrak{G}_{\sharp}$. By definition of $\mathfrak{G}_{\sharp}$, there is a decorated graph $\mathcal{G}^{\prime}=(G^{\prime},\tau_{G^{\prime}},l_{G^{\prime}})\in\mathfrak{G}^{\prime}$ and a finite sequence $i_{1},\dots,i_{k}\in\{n,c\}$ such that

We now claim that both $\mathcal{G}^{\prime}$ and the sequence $i_{1},\dots,i_{k}$ are uniquely determined by $(G,\tau_{G})$ (under the obvious constraint that no $\mathcal{F}_{i_{j}}$ is allowed to act on a decorated graph whose stem is completely nonbacktracking). Indeed, we must have that $\mathcal{G}^{\prime}=\mathcal{R}(G,\tau_{G})$. (This follows immediately from the fact that $\mathcal{R}$ is left invariant under the action of $\mathcal{F}_{i}$, $i\in\{n,c\}$; i.e. $\mathcal{R}(G_{2},\tau_{G_{2}})=\mathcal{R}(G_{1},\tau_{G_{1}})$ for any $(G_{2},\tau_{G_{2}},l_{G_{2}})=\mathcal{F}_{i}(G_{1},\tau_{G_{1}},l_{G_{1}})$ where $(G_{1},\tau_{G_{1}},l_{G_{1}})\in\mathfrak{G}$.)

That different (under the above constraint) sequences applied to $\mathcal{R}(G,\tau_{G})$ yield a different tagged graph is an immediate consequence of the following general claim. In order to state it, we introduce the set $\mathscr{D}_{\widetilde{\mathcal{G}}}$ as the set of decorated graphs obtained from $\widetilde{\mathcal{G}}\in\mathfrak{G}$ by a arbitrary applications of the operations $\mathcal{F}_{n},\mathcal{F}_{c}$. (The set $\mathscr{D}_{\widetilde{\mathcal{G}}}$ will be used in the statement and the proof of the following Claim $(*)$. We remark that the previously defined set $\mathscr{B}_{\widetilde{\mathcal{G}}}$ is a subset of $\mathscr{D}_{\widetilde{\mathcal{G}}}$ with the additional requirement that the stem is black.)

Let $\widetilde{\mathcal{G}}=(\widetilde{G},\tau_{\widetilde{G}},l_{\widetilde{G}})\in\mathfrak{G}$ be an arbitrary decorated graph whose stem is not completely nonbacktracking. Then for any $\mathcal{G}_{1}=(G_{1},\tau_{G_{1}},l_{G_{1}})\in\mathscr{D}_{\mathcal{F}_{n}(\widetilde{\mathcal{G}})}$ and $\mathcal{G}_{2}=(G_{2},\tau_{G_{2}},l_{G_{2}})\in\mathscr{D}_{\mathcal{F}_{c}(\widetilde{\mathcal{G}})}$ we have $G_{1}\neq G_{2}$.

We now prove Claim $(*)$. For any graph $\widetilde{G}\in\mathfrak{W}$ and integer q\in Q_{\widetilde{G}}\mathrel{\mathop{:}}=\bigl{\{}{0,1,\dots,\lvert\mathcal{E}(\mathcal{S}(\widetilde{G}))\rvert+2\lvert\mathcal{E}(\mathcal{B}(\widetilde{G}))\rvert}\bigr{\}}, we define the vertex $v_{\widetilde{G}}(q)\in\mathcal{V}(\widetilde{G})$ as the vertex reached after $q$ steps of the walk around $\widetilde{G}$ (see Figure 6.7). For $q\in Q_{\widetilde{G}}$ we define the “time of next return” $r_{\widetilde{G}}(q)$ as the smallest integer $q^{\prime}>q$ such that $v_{\widetilde{G}}(q^{\prime})=v_{\widetilde{G}}(q)$; if there is no such $q^{\prime}$, we set $q^{\prime}\mathrel{\mathop{:}}=\infty$.

Next, let $v_{1}\in\mathcal{V}(\widetilde{G})\setminus\{a(\widetilde{G}),b(\widetilde{G})\}$ be the first backtracking stem vertex of $\widetilde{G}$, and denote by $v_{0}$ its parent vertex (for an example see Figure 6.6). Define $q_{0}$ as the “last time we walk across $v_{0}$”, i.e. as the largest integer in $Q_{\widetilde{G}}$ satisfying $v_{\widetilde{G}}(q_{0})=v_{0}$. By definition of $q_{0}$, we have $r_{\widetilde{G}}(q_{0})=\infty$. Now define $\mathcal{G}_{c}=(G_{c},\tau_{G_{c}},l_{G_{c}})\mathrel{\mathop{:}}=\mathcal{F}_{c}(\widetilde{\mathcal{G}})$. Clearly, we have that $r_{G_{c}}(q_{0})<\infty$. Moreover, one readily sees that

for all $\mathcal{G}_{1}=(G_{1},\tau_{G_{1}},l_{G_{1}})\in\mathscr{D}_{\mathcal{F}_{n}(\widetilde{\mathcal{G}})}$ and $\mathcal{G}_{2}=(G_{2},\tau_{G_{2}},l_{G_{2}})\in\mathscr{D}_{\mathcal{F}_{c}(\widetilde{\mathcal{G}})}$. The equality expresses the fact that $v_{0}$ and $v_{2}$ have already been collapsed into one vertex in all $\mathcal{G}_{2}\in\mathscr{D}_{\mathcal{F}_{c}(\widetilde{\mathcal{G}})}$. The inequality expresses the fact that, while $v_{0}$ may be collapsed with a stem vertex $v_{j}$ at some point when constructing $G_{1}\in\mathscr{D}_{\mathcal{F}_{n}(\widetilde{\mathcal{G}})}$, the walk from $v_{0}$ to $v_{j}$ is strictly longer than from $v_{0}$ to $v_{2}$. Claim $(*)$ follows immediately from (6.12).

If a vertex $v\in\mathcal{V}(G)$ that is not the root of a bough satisfies $(u,v),(v,w)\in\mathcal{E}(\mathcal{S}(G))$ for some vertices $v,w$ and if the tags of $(u,v)$ and $(v,w)$ are both $(s,0)$, then the vertex $v$ is a nonbacktracking stem vertex.

Next, Claim (iii) clearly holds if $\mathcal{G}=(G,\tau_{G},l_{G})\in\mathfrak{G}^{\prime}$. Moreover, by definition of $\mathcal{F}_{n}$ and $\mathcal{F}_{c}$, Claim (iii) holds for $\mathcal{F}_{n}(\mathcal{G})$ and $\mathcal{F}_{c}(\mathcal{G})$ if it holds for $\mathcal{G}$. Hence Claim (iii) follows from the definition of $\mathfrak{G}_{\sharp}$.

Claim (iv) is an immediate consequence of the fact that if $\widetilde{\mathcal{G}}\in\mathscr{B}_{\mathcal{G}}$ then $\mathcal{G}=\mathcal{R}(\widetilde{\mathcal{G}})$.

Claim (v) is an immediate consequence of the fact that, by definition of $\mathcal{F}_{n}$ and $\mathcal{F}_{c}$, we have $\deg(\mathcal{G})=\deg(\mathcal{F}_{n}(\mathcal{G}))=\deg(\mathcal{F}_{c}(\mathcal{G}))$.

Finally, we prove Claim (vi). Let $\mathcal{G}\in\mathfrak{G}^{\prime}$. Using Lemma 6.3 repeatedly, we get

where $(\mathcal{G}_{i})_{i\in I}$ is a finite family of decorated graphs whose stems are completely nonbacktracking. By definition of $\mathscr{B}_{\mathcal{G}}$, we have $\mathscr{B}_{\mathcal{G}}\;=\;\{{\mathcal{G}_{i}\,:\,i\in I}\}$. What remains is to show that each $\widetilde{\mathcal{G}}\in\mathscr{B}_{\mathcal{G}}$ appears only once in $(\mathcal{G}_{i})_{i\in I}$. But this is an immediate consequence of the uniqueness of the sequence $i_{1},\dots,i_{k}$ in the representation \widetilde{\mathcal{G}}=\bigl{(}{\mathcal{F}_{i_{k}}\circ\cdots\circ\mathcal{F}_{i_{1}}}\bigr{)}(\mathcal{G}); see the proof of Claim (i) above. ∎

In view of Proposition 6.6 (i), we may regard the set $\mathfrak{G}_{\sharp}$ as a set of tagged graphs $(G,\tau_{G})$. We shall consistently adopt this point of view from now on.

where $\mathfrak{V}_{xy}(\mathcal{G})$ is defined in (6.9), and we defined the subset of graphs

The first equality of (6.13) follows from (6.4) and the definition of $\mathfrak{G}^{\prime}$ (see Definition 6.4); the second from Proposition 6.6 (iv), (v), and (vi). ∎

Lumping of edges

For the following we fix $\mathcal{G}=(G,\tau_{G})\in\mathfrak{G}_{\sharp}$ and $\mathcal{G}^{\prime}=(G^{\prime},\tau_{G^{\prime}})\in\mathfrak{G}_{\sharp}$. Thus, we also fix the maps $l_{G}$ and $l_{G^{\prime}}$; see Proposition 6.6 (i). To streamline notation, we introduce their union $\mathcal{G}\cup\mathcal{G}^{\prime}=(G\cup G^{\prime},\tau_{G\cup G^{\prime}})$ defined in the obvious way. We also get the map $l_{G\cup G^{\prime}}$ that we extend by requiring that $l_{G\cup G^{\prime}}(v,w)=0$ if $v\in\mathcal{V}(G)$ and $w\in\mathcal{V}(G^{\prime})$. We often abbreviate $\tau\equiv\tau_{G\cup G^{\prime}}$ and $l\equiv l_{G\cup G^{\prime}}$.

As in the previous section, we abbreviate the family of labels with

Let $\mathscr{G}(G\cup G^{\prime})$ denote the set of all lumpings of $\mathcal{E}(G\cup G^{\prime})$ whose lumps are of even degree. Thus (7.3) becomes

where we defined the value of the graph $\mathcal{G}\cup\mathcal{G}^{\prime}$ with lumping $\Gamma$ as

Next, let $I_{n}\in\mathfrak{W}$ denote the bare stem consisting of $n$ edges. Recall that a bare stem is a graph with no bough edges; it is uniquely determined by its number of edges. Denote by $\mathcal{I}_{n}\in\mathfrak{G}_{n}$ the decorated graph obtained from $I_{n}$ by assigning the tag $(s,0)$ to each edge (in particular, the stem $I_{n}$ is completely nonbacktracking in $\mathcal{I}_{n}$). Define the subset

From (7.1) and (7.5) we get the splitting

This is our starting point for the remaining sections. The first term on the right-hand side of (7.7) is the leading term, whose contribution is computed in Section 8. The remaining three terms on the right-hand side of (7.7) are error terms, and are estimated in Sections 9 and 10.

The bare stem

In this section we analyse the first term on the right-hand side of (7.7) by proving the following result.

where we recall the definition of $L(T,X)$ from (3.4).

The rest of this section is devoted to the proof of Proposition 8.1. The proof is similar to , which we shall frequently refer to in this section for precise definitions and proofs. We therefore assume that the reader has some familiarity with .

The only complication compared to is that controlling higher order lumpings (resulting in high moments of $\widehat{A}_{xy}$) requires more effort, since, unlike in , the matrix elements of $\widehat{A}$ are not bounded by $1$ (but only by $M^{\delta}$). A lump $\gamma$ containing $\lvert\gamma\rvert$ edges carries a weight $M^{\delta\lvert\gamma\rvert}$, but this factor can be compensated by the fact that large lumps impose strong restrictions on the labelling of the vertices. Technically, we shall deal with these higher order lumpings by replacing an arbitrary lumping with a pairing whose contribution is small enough to compensate any powers of $M$ resulting from the lumping. In this way we can directly reduce the estimate of general lumpings to pairings. The appropriate pairing will be selected by a greedy algorithm defined in Appendix C.

We begin by establishing notation and recalling the relevant results from .

The simple structure of $\mathcal{I}_{n}\cup\mathcal{I}_{n^{\prime}}$ allows for some notational simplifications. Following , we abbreviate $\mathscr{G}_{n,n^{\prime}}\mathrel{\mathop{:}}=\mathscr{G}(I_{n}\cup I_{n^{\prime}})$ and $V_{x}(\Gamma)\;\mathrel{\mathop{:}}=\;V_{x}(\mathcal{I}_{n}\cup\mathcal{I}_{n^{\prime}},\Gamma)$. Thus the left-hand side of (8.1) becomes

As in , we identify the vertices $a(I_{n})$ and $b(I_{n^{\prime}})$, as well as the vertices $b(I_{n})$ and $a(I_{n^{\prime}})$ (this is purely a notational simplification). We label the vertices explicitly according to

The expression (7.6) may also be simplified in the case of the bare stem. From (7.6) we get

Here we used that all edges of $\mathcal{I}_{n}\cup\mathcal{I}_{n^{\prime}}$ have tag $(s,0)$.

We call lumpings $\Gamma=\{\gamma\}$ with $\lvert\gamma\rvert=2$ for each $\gamma\in\Gamma$ pairings, and denote the subset of pairings by $\mathscr{P}_{n,n^{\prime}}\subset\mathscr{G}_{n,n^{\prime}}$. We shall often use the notation $\Pi=\{\pi\}$ instead of $\Gamma=\{\gamma\}$ to denote a pairing. We represent a pair $\pi=\{e,e^{\prime}\}$ graphically by drawing a line, called a bridge, that joins the edges $e,e^{\prime}\in\mathcal{E}(I_{n}\cup I_{n^{\prime}})$; see Figure 8.2.