THE NON-BACKTRACKING SPECTRUM OF THE UNIVERSAL COVER OF A GRAPH

OMER ANGEL, JOEL FRIEDMAN, AND SHLOMO HOORY

Abstract. A non-backtracking walk on a graph, H, is a directed path of directed edges of H such that no edge is the inverse of its preceding edge. Non-backtracking walks of a given length can be counted using the non-backtracking adjacency matrix, B, indexed by H’s directed edges and related to Ihara’s Zeta function.

We show how to determine B’s spectrum in the case where H is a tree covering a finite graph. We show that when H is not regular, this spectrum can have positive measure in the complex plane, unlike the regular case. We show that outside of B’s spectrum, the corresponding Green function has “periodic decay ratios.” The existence of such a “ratio system” can be effectively checked, and is equivalent to being outside the spectrum.

We also prove that the spectral radius of the non-backtracking walk operator on the tree covering a finite graph is exactly \sqrt{gr}, where gr is the growth rate of the tree. This further motivates the definition of the graph theoretical Riemann hypothesis proposed by Stark and Terras [ST].

Finally, we give experimental evidence that for a fixed, finite graph, H, a random lift of large degree has non-backtracking new spectrum near that of H’s universal cover. This suggests a new generalization of Alon’s second eigenvalue conjecture.

1. Introduction

Let H be a finite, simple (i.e., without self-loops or multiple edges), connected graph. The main result of this paper is to describe the spectrum of operators on the universal cover, H̃, of H, that are “lifts” from operators on H. Let us briefly describe this result, saving precise definitions and statements for later sections.

A cover of H is a graph homomorphism π: G → H such that π induces a bijection between the edges incident on x and those incident on π(x). Note that G may be infinite. The universal cover H̃ of H is the unique (up to isomorphism) cover of H that is a tree. A cover of H may be thought of as a graph with the same local structure as H. The universal cover is in several senses an approximation to typical large covers of H.

A connected local operator on H is a matrix M indexed by H’s vertices, such that if x ≠ y then M_{x,y} ≠ 0 iff x ∼ y, where x ∼ y means that x is adjacent to y; M may be viewed as an operator, in that for a function f on H we have a function Mf defined by (Mf)_{x} = ∑_{y∼x} M_{x,y}f_{y}. Using the bijection on neighbourhoods induced by π, any such operator extends in a canonical way to a bounded operator M̃ on ℓ^{2}(H̃). (See Section 2 for more detailed definitions.) One of our main results is an algebraic description of the spectrum of M̃.

Date: November 2007. This research was done while OA and SH were at UBC; OA held a PIMS postdoctoral fellowship.

Theorem 1.1. Fix a finite graph, H, and symmetric, connected, local operator, M, on H. There is an explicit (in terms of H, λ) set, S, of polynomial equations in variables {r_{e}}_{e∈E(H)} taking values in ℂ ∪ {∞}, such that M̃ − λI is invertible iff S has a solution with norm α(r) < 1, where α(r) is the largest eigenvalue of a matrix whose entries are given via H as polynomials in the {r_{e}}.

See Theorem 1.4 below for a statement including the algebraic representation. This result gives an algorithm for finding the spectrum of of H̃, and shows that it is determined by some algebraic curves.

A significant and motivating case of Theorem 1.1 is the non-backtracking spectrum of a graph. A non-backtracking walk on a graph, H, is a directed path in H such that no edge is the inverse of the preceding edge. The non-backtracking matrix of the graph allows counting such paths in the same way that the adjacency matrix of a graph is used to count paths in the graph. Non-backtracking walks appear in numerous applications and estimating their number is a fundamental problem. The matrix B is indexed by directed edges of H, with B_{e,f} = 1 iff (e, f) form a nonbacktracking path of length 2. This may be seen as an asymmetric, local operator on the edge graph of H, and in this way extended to an operator on H̃. This operator is asymmetric, but we can still use Theorem 1.4 to characterize B̃’s spectrum. Note that while B and B̃ are real operators, they are not self-adjoint and so their spectra may be complex.

Theorem 1.2. Given H, λ, there is an explicit set of polynomial equations in variables {r_{e}}_{e∈E(H)} taking values in ℂ ∪ {∞}, such that B̃ − λI is invertible iff there is a solution with norm α(r) < 1, where α(r) is explicitly given in terms of H.

As an example, we consider the case where H is K_{4} with one edge deleted. Already in that case, the spectrum of the non-backtracking path operator on B̃ has a nontrivial structure, see Figure 1. We are also interested in the relation between the non-backtracking spectrum of H̃ and that of a typical large but finite cover of H. Figure 2 shows the spectrum of a randomly chosen cover of this H. This and other numerical experiments give strong indication that the spectra converge to the spectrum of the universal cover (determined rigorously in this paper.)

1.1. Motivation. Non-backtracking walks seem to be an essential part of various aspects of graph theory, including the Broder-Shamir trace method ([BS87, Fri91, Fri93, Fri]), Ihara zeta functions of graphs ([Has89, KS00, ST]), Bollobas’ question concerning girth and average degree ([AHL02, Hoo05]), and decoding of low density linear codes ([Gal63, Sho04, RU]). Given H, there is a matrix, B = B(H), whose powers count non-backtracking walks of a given length. B is indexed by the directed edges of H, and is analogous to the adjacency matrix for paths (see below). Many interesting quantities concerning non-backtracking walks can be expressed in terms of spectral properties of B.

Several applications of walks in a graph H, require understanding the spectrum of the universal cover of H, denoted H̃. Similarly, there are connections between nonbacktracking walks on H and the spectrum of the non-backtracking walk operator on H̃.

Figure 1. The non-backtracking spectrum of the universal cover of K_{4} minus an edge.

Figure 2. The non-backtracking spectrum of a random 300-lift of K_{4} minus an edge. The shaded area is the non-backtracking spectrum of its universal cover; the circled points are the spectrum for the base graph.

For regular graphs, i.e., graphs in which each vertex has the same degree, there is a direct and simple relationship between the spectrum of B and that of the adjacency matrix, A = A(H). This fact renders many questions quite easy for regular graphs, masking formidable difficulties that may occur for non-regular graphs. In the case of a d-regular graph H, the universal cover is a d-regular tree, and the spectrum of Ã = A(H̃) is known to be the interval

σ(Ã) = [−2\sqrt{d − 1}, 2\sqrt{d − 1}] .

In this case, the spectrum of B̃ = B(H̃) is the union of a circle and two real intervals in the complex plane. Numerical experiments, such as those of Stark and Terras (see [ST] and the previous papers in that series), suggest that B̃, for general (nonregular) H, can be two dimensional. As an example, when H is K_{4} minus an edge, the non-backtracking spectrum of H̃ is depicted in Figure 1.

The main goal of this paper is to give a method for finding the spectrum of B̃ for any finite graph, H. This will prove the above noted two-dimensionality. A consequence of this method is that ρ(B̃) = \sqrt{gr}, i.e., the spectral radius of B̃ is the square root of the growth rate of H̃. This further motivates the definition of the graph theoretical Riemann hypothesis proposed by Stark and Terras [ST].

Alon’s conjecture. Alon’s conjecture states that for any d ≥ 3 and any ε > 0, the probability that a random d-regular graph on n vertices has second largest eigenvalue λ_{2} ≤ 2\sqrt{d − 1} + ε tends to 1 as n → ∞. This was proven for various of notions of “random graph,” i.e., various probability distributions on d-regular graphs on n vertices, in [Fri] (see also [BS87, Fri91]). A main tool used to this end is the analysis of non-backtracking walks in random, regular graphs.

As we shall see (and see [Fri]), for finite d-regular graphs each μ ∈ σ(A) corresponds to two λ ∈ σ(B) given by the solutions of λ^{2} − μλ + d − 1 = 0. In particular, since σ(A(H)) ⊂ [−d, d], the non-backtracking spectrum is contained in the union of the circle \{z : |z| = \sqrt{d − 1}\} and the two real segments [1−d, −1] and [1, d−1]. This simple relation yields a form of Alon’s conjecture in terms of the non-backtracking spectrum, namely that the spectral radius, ρ(B), of B is at most \sqrt{d − 1} + ε.

In [Fri03], Alon’s conjecture is relativized, meaning that for any graph, H (the “base graph”), we consider a random lift, π: G → H, of degree n; eigenpairs of A(H) pull back to eigenpairs of A(G), we call such eigenpairs of A(G) old eigenpairs of π, while eigenpairs of A(G) not arising from A(H) we call new eigenpairs of π; we conjecture that for any fixed H and ε > 0, most random lifts have all new eigenvalues of absolute value bounded above by ε plus the spectral radius of A(H̃); and a weaker new eigenvalue bound is proved via the Broder-Shamir technique (Alon’s original conjecture is the case where H has one vertex). The full conjecture might be provable with a refined Broder-Shamir method (as in [Fri91, Fri]) that seems to require a translation between the adjacency matrix spectrum and non-backtracking spectrum. However, for irregular graphs we are aware of no such translation. This makes it difficult to apply the trace method in the general case.

Computer experiments indicate that the new (i.e., not arising from the base) nonbacktracking spectrum of large random lifts is distributed in some fixed region, as seen in Figure 2. We would like to prove that this region is the non-backtracking spectrum of the universal cover of the base graph, shown in Figure 1. This suggests a generalization of the relative Alon conjecture, roughly stating that the new nonbacktracking spectrum of a large random lift is near the non-backtracking spectrum of the universal cover; for non-regular graphs, unlike the case of regular graphs, it is not clear how this relates to the usual relative Alon conjecture regarding adjacency matrix spectrum. This might allow us to apply the trace methods of [BS87, Fri93, Fri] in order to prove some analog of Alon’s conjecture for lifts of general base graphs (perhaps first for the non-backtracking spectrum and then, ultimately, on the adjacency matrix spectrum).

The relativized Alon conjecture raises the questions of how to determine the nonbacktracking spectrum of the universal cover of a finite graph (answered in this paper) and how can one translate spectral bounds between adjacency matrices and non-backtracking adjacency matrices in the irregular case.

The Ihara Zeta function. For a finite graph H, the eigenvalues of B(H) are the reciprocals of the poles of the Ihara zeta function of the graph. This zeta function is a graph theoretic analogue of the number theoretic Riemann zeta function. For further details, we refer the reader to Hashimoto [Has89], Kotani and Sunada [KS00], and to Stark and Terras [ST].

Bounds for graphs with large girth. A third motivation is the result of Alon, Hoory, and Linial [AHL02], giving a lower bound on the number of vertices in a graph with a specified girth and average degree. They answer affirmatively a longstanding open question by Bollobás. Their result is basically a lower bound on the Perron eigenvalue of B in terms of the average degree. In further work, Hoory [Hoo05], gave a similar bound on the spectral radius of H’s universal cover, ρ(A(H̃)).

Further questions raised by these works concern the relation between H̃’s growth rate gr = ρ(B), and the spectral radii of the remaining three operators A, Ã, and B̃. In this paper we partially answer this question by proving that ρ(B̃) = \sqrt{gr}.

LDPC error correcting codes. A final motivation is the analysis of a decoding algorithm for a family of error correcting codes, known as low density parity check (LDPC) codes. This decoding algorithm, which is receiving a lot of attention at present, was first suggested by Gallager [Gal63]. LDPC codes are binary linear codes of length n, described by a set of highly sparse linear equations over GF (2). It is convenient to represent such a code by a bipartite graph, where the two sides correspond to variables and equations. Each equation is adjacent to the variables occurring in it. There is a natural decoding algorithm for such codes based on message passing. At each iteration of the algorithm, a message is sent along each directed edge of the graph (alternating between variables to equations and equations to variables rounds). We refrain from further description of this algorithm, and refer the reader to a survey by Shokrollahi [Sho04], or a book by Richardson and Urbanke [RU].

The connection of this algorithm to non-backtracking walks is in the fact that the k-th generation message computed at edge e depends only on the initial value at the endpoints of all length k non-backtracking walks starting at e. It seems that to analyze such an algorithm, one needs a non-backtracking analog of expansion. For example, the Mixing Lemma for expanders states that the number of edges e(S, T) between any two vertex sets S, T in a d-regular graph satisfies |e(S, T) −

d|S||T |/N| ≤ λ_{2}\sqrt{|S||T |}, where λ_{2} is the second largest eigenvalue in absolute value (see [HLW] for a survey on expander graphs). It would be helpful to develop a non-backtracking analogue of the expander Mixing Lemma.

1.2. Main results. In the following unless otherwise specified, all graphs will be simple, meaning without self-loops or multiple edges, and connected; in Section 9 we explain our conventions and generalizations to graphs that are not simple. Throughout this paper, if G is a graph, then V (G) denotes G’s vertices, and E(G) denotes G’s directed edges, which (for G simple) we define as the union of {(u, v), (v, u)} over all u, v joined by an edge of G; for e = (u, v) ∈ E(G) we set e^{−1} = (v, u); we write u ∼ v to denote that there is an edge joining u and v. (All graphs in this paper are locally finite, meaning that each vertex is incident upon a finite number of edges.)

Let π: T → H be the universal cover of a finite graph, H. For an operator, M, on l^{2}(V (T)), we set M_{uv} = ⟨δ_{u}, Mδ_{v}⟩ for u, v ∈ V (T) (where δ denotes the Dirac delta function); we say that M is

(1) symmetric if \overline{M}^{∗} = M;

(2) local if M_{uv} = 0 for u, v of distance greater than one;

(3) connected if M_{uv} ≠ 0 for u, v of distance one;

(4) a pullback (from π or, abusively, H) if M_{uv} depends only on π(u) and π(v) assuming u ∼ v.

The main result of this paper gives a way to compute the spectrum of local, symmetric operators on T pulled back from H. If M has an inverse, we define the Green function for M to be G(u, v) = ⟨δ_{u}, M^{−1}δ_{v}⟩. If an operator A on l^{2}(V (H)) pulls back to π^{∗}A on T, then determining the spectrum of π^{∗}A amounts to determining for which λ the operator M = M_{λ} = π^{∗}A − Iλ has a Green function.

The key idea in this paper to determine the Green function, G, of M, is that for any edge, e = (u, v), of E(T), the ratio r_{e} = G(u, v)/G(u, u) should depend only on π(e). This surprised us at first, although the intuitive explanation is simple. If π(e) = π(e′) for e′ = (u′, v′) ∈ E(T), then there is an automorphism of T taking e to e′; using this automorphism we can “graft” appropriate linear combinations of pieces of G(u, ·) and G(u′, ·) onto G(u′, ·); if r_{e} ≠ r_{e′}, then this “grafting” process will yield more than one Green function, which is impossible (see Lemma 5.3).

There are numerous technical difficulties in turning this intuition into precise theorems. One is that an example of Figà-Talamanca and Steger (see Section 8) shows that G(u, u) may vanish, forcing us to work with the more delicate situation of zero and infinite ratios. Another is that knowing M and a ratio system, r, while it is easy to determine G, it does not seem easy to know if M is invertible, at least when H is infinite.

To make a precise statement, if a, b ∈ ℂ with at least one of a, b not vanishing, we interpret b/a to be ∞ if a = 0 and the usual ratio otherwise; in this case we say the generalized ratio, b/a, exits. If u, v, w ∈ V (T) are vertices of a tree, T, we write [u, w] for the unique path (a sequence alternating between vertices and edges) from u to w in T, and say that v is between u and w if v lies in [u, w].

Definition 1.3. A ratio system for M is a function r: E(H) → ℂ ∪ {∞} satisfying the following:

(a) If r_{e} ≠ 0 for some e = (u, v) then

0 = m_{vv} + \frac{m_{e^{−1}}}{r_{e}} + ∑_{e′ s.t. e→e′} m_{e′}r_{e′},  (1)

with the convention that c/∞ = 0 for any c, and where e → e′ means that e′ ≠ e^{−1} but (e, e′) forms a path of length two (i.e., e’s head is the tail of e′).

(b) If r_{e} = 0 then there is some f with e → f and r_{f} = ∞.

(c) If r_{f} = ∞ and e → f, then r_{e} = 0 and r_{f^{−1}} ≠ 0.

Here condition (a) comes from the fact that for fixed u we have MG(u, ·) = δ_{u}; conditions (b) and (c) are needed when the ratios become zero or infinite, i.e., when G(u, u) = 0 for some u. Note that there is no assumed relationship between r_{e} and r_{e^{−1}}.

For a ratio system we define r’s decay rate, α(r), to be the Perron eigenvalue of the matrix R whose rows and columns are indexed by the directed edges of H with nonzero (but possibly infinite) ratios, defined by:

R_{e,f} = \begin{cases}∑_{e′ s.t. e→e′→f} |m_{f}/m_{e^{′−1}}|^{2} & r_{f} = ∞, \\ |r_{f}|^{2} & r_{f} ≠ ∞ and e → f, \\ 0 & otherwise. \end{cases}  (2)

Theorem 1.4. Let π: T → H be a universal cover of a finite graph, H, and let M be a pulledback, symmetric, local operator on l^{2}(V (T)). Then M has a bounded inverse if and only if M has a ratio system r : E(H) → ℂ ∪ {∞} with α(r) < 1.

Furthermore, for and edge (u, v) of type e and any w such that u ∈ [w, v], we have G(w, v)/G(w, u) = r_{e} whenever this generalized ratio is defined.

Theorem 1.4 has numerous applications, including to adjacency matrices and Laplacians. The application to non-backtracking spectrum of a graph, G, derives from its connection to the local operator

Q_{λ} = Q − λA + λ^{2}I

where A = A_{G} is the adjacency matrix of G and Q = Q_{G} is the diagonal matrix with entries Q_{vv} = d_{v} − 1 where d_{v} is the degree of v. Specifically we shall prove the following theorem for graphs, G, of bounded degree, regarding the spectrum, σ(B), of B = B(G).

Theorem 1.5. Let G be a graph with degrees bounded by d_{max}, then

σ(B(G)) = {±1} ∪ {λ : Q_{λ} is not invertible}.

For λ = 0, Q_{λ} is symmetric, and otherwise

λ^{−1}Q_{λ} = λ^{−1}Q − A + λI

is (real) symmetric, and so Theorem 1.4 applies to Q_{λ}.

The following provides an interesting contrast to Theorem 1.4.

Theorem 1.6. Let π: T → H be as in Theorem 1.4. If r is a ratio system with α(r) = 1, then M is not invertible.

Calculations with K_{4} minus an edge, as in Figure 1, show that a given M can have more than one ratio system. Theorem 1.6 says that if there is a ratio system with α = 1, then there are none with α < 1.

The rest of this paper is divided as follows. In Section 2 we give some preliminary remarks. In Section 3 we discuss the non-backtracking spectra of trees and prove Theorem 1.5. In Section 4 we bound the non-backtracking spectrum in an annulus in terms of the growth rate of the tree. In Section 5 we discuss the Green function and relative kernels (that make precise the “grafting” idea discussed earlier showing that Green’s function has “periodic ratios”). In Section 6 we prove Theorem 1.4 in the case of a ratio system with no zero or infinite ratios. In Section 7 we prove Theorem 1.4 in full generality. In Section 8 we give some interesting examples illustrating various aspects of Theorem 1.4. In Section 9 we show how to extend our theory to much more general base graphs (or pregraphs), H. In Section 10 we make some remarks, mentioning a few of the many questions left open by this paper.

Acknowledgments. We wish to thank Chen Greif, Audry Terras, Alex Gamburd, and Bálint Virág for illuminating discussions.

2. Preliminaries

A directed edge e′ = (u′, v′) of a graph, H, can follow edge e = (u, v), denoted e → e′, if u′ = v and e′ ≠ e^{−1}. A non-backtracking walk on H is a sequence of directed edges e_{1}, e_{2}, …, e_{r} such that e_{k} → e_{k+1} for all k.

If H is a graph and v ∈ V (H), the 1-neighbourhood of v is the subgraph consisting of all undirected edges incident upon v. A graph homomorphism ν: H′ → H is a covering map (see [Fri93]) if for each v′ ∈ V (H′), ν gives a bijection of the edges of the 1-neighbourhood of v′ with those of v (note that this definition is correct even when the graphs have self-loops; see Section 9). H′ is a cover of H. The type of a vertex v ∈ H′, is defined as the vertex ν(v) ∈ H. If ν(v′) = v for vertices v′, v, we say that v′ is above v (or v is below v′). These terms are similarly defined for edges.

Note that a cover of a cover is a cover. The universal cover of H, denoted H̃, is the (unique up to isomorphism) cover of H that is also a cover of every other cover of H. The universal cover may be constructed as follows. Fix some (arbitrary) vertex v_{0} ∈ H. The vertices of H̃ are the finite non-backtracking walks on H starting at v_{0}. Two vertices of H̃ are adjacent if one extends the other by a single step. The covering map π: V (H̃) → V (H) maps a walk to its terminal vertex in H. It is easy to see that H̃ is a tree, hence it is also referred to as the covering tree of H. The universality of H̃ can be stated as follows: If ν: H′ → H is any covering map, and v′ ∈ V (H′) is of type v_{0}, then there is a unique covering map μ: H̃ → H′ with π = νμ and μ(ϕ) = v′, where ϕ is the empty path.)

If the covering map ν: H′ → H is n-to-1 for some finite n, then we also say that H′ is a lifting, or an n-lifting, of H. Every cover is either a lifting or is ∞-to-1. Equivalently, the graph H′, which we denote H^{n}, can be characterized as follows: the vertex set of H^{n} consists of n copies of H’s vertices: V (H^{n}) = V (H) × [n], with the covering map π((v, i)) = v. The edges in H^{n} are given by a perfect matching between π^{−1}(v) and π^{−1}(u) for every undirected edge (u, v) ∈ E(H). This characterization gives rise to a natural distribution on n-lifts of H, by picking the perfect matchings independently and uniformly at random.

We define 0-forms to be functions on the vertices of a graph, and 1-forms to be functions on directed edges of a graph (with no constraint relating f(e) and f(e^{−1}).) Denote by A = A(H) the adjacency operator acting on the Hilbert space of 0-forms, i.e., (Af)(v) = ∑_{u∼v} f(u) with multiple edges taken into account.) For graphs with minimal degree at least two, we consider the non-backtracking adjacency operator, B = B(H), which acts on 1-forms. B’s action is given by

(Bf)(e) = ∑_{e′ s.t. e→e′} f(e′).

The definitions of A, B are valid for any locally finite graph, and in particular for H̃. When the degrees in a graph are globally bounded, A and B may be viewed as bounded operators on l^{2}(V) and l^{2}(E), respectively. In the finite case, B is the adjacency matrix of the directed graph with an edge from e_{1} to e_{2} iff e_{2} → e_{1}. Notice that in the literature B is occasionally defined as the adjoint of our definition.

The non-backtracking spectrum of a graph H is defined to be the spectrum of the corresponding operator B (as opposed to the spectrum of H which is the spectrum of A.) Note that A is self-adjoint, hence any graph’s spectrum is real. However, the non-backtracking spectrum generally contains complex numbers. Ã = A(H̃) and B̃ = B(H̃) denote the corresponding operators on H̃.

We denote by ρ(u, v) the graph distance in H̃. We let gr denote the growth rate of the universal cover H̃, i.e.

gr = lim_{r→∞} |Ball(v, r)|^{1/r},

where Ball(v, r) is the radius r ball around some (arbitrary) vertex v ∈ V (H̃); for connected H the limit is independent of the choice of v. It is straightforward to see gr is the Perron-Frobenius eigenvalue of B.

3. Non-backtracking spectrum basics

We start with some background from spectral theory. Let T be a bounded linear operator acting on a Hilbert space H (in this paper we work with l^{2}(X), where X will be one of V, Ṽ = V (H̃), E, or Ẽ = E(H̃)). Recall that the spectrum of T is

σ(T) = {λ|T − λI does not have a bounded inverse},

and its spectral radius is

ρ(T) = max{|λ| : λ ∈ σ(T)}

(no confusion should arise regarding this ρ and the distance, ρ, that involves two arguments). If H is finite dimensional, then λ ∈ σ(T) iff there is a nonzero f satisfying T f = λf. In the general case we have [Rud91, Chapter 12]:

Theorem 3.1. For a bounded linear operator T: H → H, we have λ ∈ σ(T) iff one of the following three possibilities hold:

(i) there exists a nonzero f such that (T − λI)f = 0, (ii) there exists a nonzero f such that (T^{∗} − \overline{λ}I)f = 0, (iii) for every ε > 0 exists a nonzero f such that ∥(T − λI)f∥ < ε∥f∥.

In case (iii), a sequence of f’s with ε → 0 is referred to as approximate eigenfunctions; case (i) is a special case of (iii).

Definition 3.2. A bounded linear operator T is called symmetric (sometimes real symmetric in the literature) if \overline{T}^{∗} = T.

If T is symmetric, then case (ii) of Theorem 3.1 is equivalent to case (i), and so λ is in the spectrum iff case (iii) holds, i.e., we have a sequence of approximate eigenfunctions for λ.

While the operator B is not symmetric, to identify its spectrum it suffices to check only case (iii). To see this, define the unitary operator U: l^{2}(E) → l^{2}(E) by its action (Uf)_{e} = f_{e^{−1}}. Note that U^{−1} = U. Since B is real, it is easy to see that U^{−1}BU = B^{T} = B^{∗}. Consequently, if f is an eigenfunction of B^{∗} with eigenvalue \overline{λ}, then Uf is an eigenfunction of B with eigenvalue λ. Thus case (ii) of Theorem 3.1 holds for the same λ as case (i), and it suffices to check case (iii).

At this point we are ready to prove Theorem 1.5. Before doing so we make a few remarks on the theorem.

Note that if G is a d-regular graph, Q = (d − 1)I and so Q_{λ} = (λ^{2} + d − 1)I − λA is singular iff λ^{2} − μλ + d − 1 = 0 for some μ ∈ σ(A). Theorem 1.5 is known (in more precision) for finite graphs:

Theorem 3.3 (Bass [Bas92], Kotani and Sunada [KS00]). For any finite graph

det(B − λI) = (λ^{2} − 1)^{|E|−|V |} · det(Q_{λ}).

Note 3.4. A version of Theorem 3.3 holds for graphs with multiple edges and selfloops. Each half-loop (see Section 9) contributes a factor of λ−1, rather than λ^{2} −1.

We thank Chen Greif for the following remark:

Note 3.5. Consider the 2n × 2n matrix X = ( \begin{matrix}A & −Q \\ I & 0 \end{matrix} ). One can easily verify by row elimination that det(Q_{λ}) = det(X − λI). This observation has practical importance for calculating the non-backtracking spectrum of specific graphs, since eigenvalue calculation is a standard feature in most numeric/symbolic matrix manipulation programs.

Proof of Theorem 1.5. If G is finite, then Theorem 3.3 implies our result, hence we may restrict ourselves to infinite G. The result follows from the following three statements:

(1) we have ±1 ∈ σ(B);

(2) if λ ≠ ±1 and Q_{λ} is not invertible, then neither is B − λI;

(3) if λ ≠ ±1 and B − λI is not invertible, then neither is Q_{λ}.

To prove (1), we explicitly construct approximate eigenfunctions. G contains some infinite path of directed edges {e_{i}}_{i≥0}. For any k, define the function

f = ∑_{i=1}^{k} δ_{e_{i}} − ∑_{i=0}^{k−1} δ_{e_{i}^{−1}},

i.e., f is 1 on e_{1}, …, e_{k}, f is −1 on e_{0}^{−1}, …, e_{k−1}^{−1}, and zero on all other edges. One can easily check that

(B − I)f = δ_{e_{0}} − δ_{e_{0}^{−1}} − δ_{e_{k}} + δ_{e_{k}^{−1}}.

Thus ∥(B − I)f∥ = \sqrt{4}, while ∥f∥ = \sqrt{2k}, and so taking k → ∞ gives approximate eigenfunctions for λ = 1.

λ = −1 is similar, with

f = ∑_{i=1}^{k}(−1)^{i}δ_{e_{i}} + ∑_{i=0}^{k−1}(−1)^{i}δ_{e_{i}^{−1}}.

To prove (2), assume Q_{λ} is not invertible. Since Q_{λ} is symmetric, as noted above it has approximate (perhaps exact) eigenfunctions. Thus for every ε there is an f such that ∥f∥ = 1 and ∥Q_{λ}f∥ < ε. Note that f is defined on the vertices of G. From f we construct a 1-form, g, given by g_{uv} = f_{u} − λf_{v}. Then:

((B − λI)g)_{uv} = ∑_{\begin{matrix}w∼v \\ w≠u \end{matrix}} g_{vw} − λg_{uv} = ∑_{w∼v} g_{vw} − g_{vu} − λg_{uv}

= ∑_{w∼v}(f_{v} − λf_{w}) + (λ^{2} − 1)f_{v}

= (d_{v} − 1)f_{v} − λ(Af)_{v} + λ^{2}f_{v} = (Q_{λ}f)_{v}.

Therefore,

∥(B − λI)g∥^{2} ≤ d_{max} · ∥Q_{λ}f∥^{2} < ε^{2}d_{max}.

It remains to show that ∥g∥ is bounded from below. To this end, note that ( \begin{matrix}g_{uv} \\ g_{vu} \end{matrix}) = ( \begin{matrix}1 & −λ \\ −λ & 1 \end{matrix} ) ( \begin{matrix}f_{u} \\ f_{v} \end{matrix} ) is an invertible linear transformation for λ ≠ ±1. Thus for λ ≠ ±1, for some c = c(λ) > 0

|g_{uv}|^{2} + |g_{vu}|^{2} ≥ c (|f_{u}|^{2} + |f_{v}|^{2}) .

Summing over all edges we find ∥g∥^{2} ≥ c.

To prove (3), let S_{o}, S_{i} be the outbound and inbound sum operators from 1-forms to 0-forms, defined by (S_{o}h)_{v} = ∑_{u∼v} h_{vu}, and (S_{i}h)_{v} = ∑_{u∼v} h_{uv}. For any v, and any 1-form h:

(S_{i}Bh)_{v} = ∑_{u∼v}(Bh)_{uv} = ∑_{\begin{matrix}u,w∼v \\ w≠u \end{matrix}} h_{vw} = (d_{v} − 1)(S_{o}h)_{v}

(S_{o}Bh)_{v} = ∑_{u∼v}(Bh)_{vu} = ∑_{\begin{matrix}w∼u∼v \\ w≠v \end{matrix}} h_{uw} = (AS_{o}h − S_{i}h)_{v}.

And so we have

S_{i}B = QS_{o},  and  S_{o}B = AS_{o} − S_{i}.

Assume B − λI is not invertible for some λ ≠ ±1. As before, since B is real, for any ε > 0 there is a function g such that ∥g∥ = 1, and ∥(B − λI)g∥ < ε. We claim that f = S_{o}g is an approximate eigenfunction of Q_{λ}. Indeed:

∥Q_{λ}f∥ = ∥(λ^{2}I − λA + Q)S_{o}g∥
= ∥(λ^{2}S_{o} − λS_{o}B − λS_{i} + S_{i}B)g∥
= ∥(S_{i} − λS_{o})(B − λI)g∥
≤ (1 + |λ|)\sqrt{d_{max}} ε

(since ∥S_{o}∥ = ∥S_{i}∥ = \sqrt{d_{max}}). Furthermore, for λ ≠ ±1 we shall bound ∥f∥ from below. For any edge vu,

(S_{o}g)_{v} = (Bg)_{uv} + g_{vu} − λg_{uv} + λg_{uv};

notice that S_{i}^{∗} is the “head map,” (S_{i}^{∗}h)_{uv} = h_{v} for all h ∈ L^{2}(V), and similarly S_{o}^{∗} is the “tail map.” So we may write the last equation as S_{i}^{∗}S_{o} = (B − λI) + (λI + U) (recall (Ug)_{uv} = g_{vu}.) Since ∥g∥ = 1, U^{2} = 1 and ∥U∥ = 1, we have

|λ^{2} − 1| = ∥(λ^{2} − 1)g∥ = ∥(λ − U)(λ + U)g∥
≤ (|λ| + 1)∥(λ + U)g∥.

Since clearly ∥h∥^{2} ≥ ∥S_{i}^{∗}h∥^{2}/d_{max} for any h ∈ L^{2}(V), we have

\sqrt{d_{max}}∥f∥ ≥ ∥S_{i}^{∗}f∥ = ∥S_{i}^{∗}S_{o}g∥ ≥ ∥(λI + U)g∥ − ∥(B − λI)g∥

≥ \frac{|λ^{2} − 1|}{|λ| + 1} − ∥(B − λI)g∥.

Since ∥(B − λI)g∥ < ε, it follows that for ε small enough ∥f∥ is bounded from below. □

Note 3.6. It is possible to prove Theorem 3.3 by a similar argument, with cycles taking the place of the infinite path, resulting in exact eigenfunctions; the eigenspace of 1 is spanned by functions which are 1 on edges of an oriented cycle and -1 on the reverse cycle. The eigenspace of -1 is similar but with alternating signs along cycles of even length.

The following theorem restricts the non-backtracking spectrum of G to the union of an annulus in the complex plain, and two real intervals. For finite graphs, the theorem is due to Kotani and Sunada [KS00].

Theorem 3.7. Let d_{min} ≥ 2 and d_{max} be the minimal and maximal degrees of some (finite or infinite) graph G. Then

σ(B) ⊂ \{λ ∈ ℂ : \sqrt{d_{min} − 1} ≤ |λ| ≤ \sqrt{d_{max} − 1}\} ⋃ \{λ ∈ ℝ : 1 ≤ |λ| ≤ d_{max} − 1\} .

Proof. We first prove that

σ(B) ⊂ {λ ∈ ℂ : 1 ≤ |λ| ≤ d_{max} − 1} .

Fix some vertex v. Clearly UB acts on functions supported on edges directed out of v independently of its action on all other edges. On these d_{v} edges, the action of UB is given by the matrix J−I where J is the all ones matrix. Since σ(J−I) = {−1, d_{v}−1} and since J −I (being symmetric) is orthonormally diagonalizable, we easily see that

\frac{∥(J − I)f∥}{∥f∥} ∈ [1, d_{v} − 1]

for any function f supported on these edges; therefore, since U is unitary, for any 1-form, f, we have

\frac{∥Bf∥}{∥f∥} = \frac{∥UBf∥}{∥f∥} ∈ [1, d_{max} − 1].

If λ ∈ σ(B), then we have for any ε an approximate eigenfunction, f, with ∥f∥ = 1 and ∥(B − λ)f∥ ≤ ε. So

|λ| = ∥λf∥ ≤ ∥λf − Bf∥ + ∥Bf∥ ≤ ε + d_{max} − 1.

Taking ε → 0 yields |λ| ≤ d_{max} − 1. Similarly

|λ| = ∥λf∥ ≥ ∥Bf∥ − ∥Bf − λf∥ ≥ 1 − ε,

and we conclude ∥λ∥ ≥ 1.

It remains to prove that the non-real λ ∈ σ(B) satisfy \sqrt{d_{min} − 1} ≤ |λ| ≤ \sqrt{d_{max} − 1}. Given f ∈ L^{2}(V), define

α = \frac{⟨f, Af⟩}{∥f∥^{2}}, β = \frac{⟨f, Qf⟩}{∥f∥^{2}},

and note that ⟨f, Q_{λ}f⟩ = ∥f∥^{2} · (λ^{2} − αλ + β). Further, note that since A, Q are real symmetric operators, that α, β are real. From the definition of A, Q, we clearly have |α| ≤ d_{max} and β ∈ [d_{min} − 1, d_{max} − 1].

If f is an eigenfunction then λ^{2} − αλ + β = 0. If Q_{λ} has only approximate eigenfunctions, f_{ε}, then for those we have α = α_{ε}, β = β_{ε} satisfying

|λ^{2} − α_{ε}λ + β_{ε}| = |⟨f, Q_{λ}f⟩| ≤ ε

and as before, |α_{ε}| ≤ d_{max} and β_{ε} ∈ [d_{min} − 1, d_{max} + 1]. By passing to a subsequence we may assume that α_{ε} and β_{ε} have limits, α, β, as ε → 0. We find that, again, λ^{2} − αλ + β = 0 with real α, β satisfying β ∈ [d_{min} − 1, d_{max} − 1].

Solving the quadratic equation we get λ = α/2 ± \sqrt{α^{2}/4 − β}. If λ is not real then the square root is of a negative number and

|λ|^{2} = (α/2)^{2} + β − α^{2}/4 = β,

and the claim follows. □

4. Non-backtracking spectrum of trees

The non-backtracking spectrum of a tree has a fourfold symmetry that is not hard to rigorously prove:

Proposition 4.1. For any bipartite graph, G, σ(B(G)) is invariant under reflection in the real and imaginary axis.

As we will be primarily concerned with the non-backtracking spectrum of trees, note that this result applies whenever G is a tree.

Proof. Since (for any graph) B is a real operator, σ(B) is invariant under complex conjugation.

For a bipartite graph G, let X, Y be the two sides of the graph. Consider the unitary operator N on 1-forms that negates f_{uv} for u ∈ X and leaves f_{uv} unchanged for u ∈ Y. Clearly N^{−1} = N and it is easy to see that N^{−1}BN = −B. Thus σ(B) = −σ(B). □

The next result improves on the upper bound of Theorem 3.7 for sufficiently nice trees. A graph has uniformly bounded growth, \overline{gr}, if

\overline{gr} = lim sup M_{r}^{1/r}

is finite, where

M_{r} = sup_{v} |Ball(v, r)|.

Theorem 4.2. Assume a tree without leaves has uniformly bounded growth \overline{gr}, then

σ(B) ⊂ \{λ : 1 ≤ |λ| ≤ \sqrt{\overline{gr}}\}.

Note that for graphs with uniformly bounded degrees, M_{r} = O((d_{max}−1)^{r}), and so \overline{gr} is finite. For universal covers of finite graphs, \overline{gr} = gr = lim_{r→∞} |Ball(v, r)|^{1/r} for any fixed v. We shall later see that for universal covers of finite graphs, Theorem 4.2 is sharp and in fact \{λ : |λ| = \sqrt{\overline{gr}}\} ⊂ σ(B).

Proof. Denote e →_{k} e′ if there is a non-backtracking path e → e_{1} → ⋯ → e_{k−1} → e′. Note that if such a path exists, then it is unique and its length is determined by e, e′. By definition,

∥B^{k}∥ = sup_{∥f∥=∥g∥=1} |⟨g, B^{k}f⟩|.

For f, g with ∥f∥ = ∥g∥ = 1, and any collection of coefficients a(e, e′) > 0, we have by Cauchy-Schwarz

|⟨g, B^{k}f⟩| = | ∑_{e′→_{k}e} f(e)g(e′)|

≤ ∑_{e′→_{k}e} a(e, e′)|f(e)|^{2} + a(e, e′)^{−1}|g(e′)|^{2}

≤ (sup_{e} ∑_{e′→_{k}e} a(e, e′)) ∥f∥^{2} + (sup_{e′} ∑_{e′→_{k}e} a(e, e′)^{−1}) ∥g∥^{2}.

It remains to choose the coefficients a(e, e′) so that the sums above are small. To this end, fix some (arbitrary) vertex in the tree to be the root. The unique path from e′ to e must descend toward the root some number of steps i, and then ascend k − i steps on a different branch to reach e. Fix a(e, e′) = \overline{gr}^{(i−k/2)}.

For any ε > 0 there is some c = c(ε), such that the total number of nonbacktracking paths of length ℓ from any vertex is bounded by c · ((1 + ε)\overline{gr})^{ℓ}. Since there is always a unique path toward the root, the number of paths starting at e′ with i, k as above is at most c · ((1 + ε)\overline{gr})^{k−i}. Consequently

sup_{e} ∑_{e′→_{k}e} a(e, e′) ≤ ∑_{i=0}^{k} c((1 + ε)\overline{gr})^{k−i}\overline{gr}^{(i−k/2)}
≤ c(k + 1)(1 + ε)^{k}\overline{gr}^{k/2}.

Similarly, the number of paths of type i ending at e is bounded by c_{δ}((1 + ε)\overline{gr})^{i}, and hence also

sup_{e′} ∑_{e′→_{k}e} a(e, e′)^{−1} ≤ c(k + 1)(1 + ε)^{k}\overline{gr}^{k/2}.

Combining the bounds we find

ρ(B) = lim (∥B^{k}∥)^{1/k} ≤ (1 + ε)\sqrt{\overline{gr}}.

Since ε was arbitrary, this proves the claim. □

5. The Green function and the Relative Kernels

Let π: T → H and M as in Theorem 1.4. By deleting edges e = {u, v} from E(H) for which m_{uv} = 0, we may assume M is connected, i.e., m_{uv} ≠ 0 whenever (u, v) ∈ E(V). If e = (u, v) is an edge of T or H, we write m_{e} for m_{uv}.

Assume that M is invertible. Then there is a unique Green function, G = G_{M}, defined by the requirement that MG(x, ·) = δ_{x}(·), or equivalently,

G(u, v) = (M^{−1}δ_{u})(v).

Notice that the symmetry M^{∗} = \overline{M} implies the symmetry of the Green function,

G(u, v) = ⟨M^{−1}δ_{u}, δ_{v}⟩ = ⟨δ_{u}, (M^{∗})^{−1}δ_{v}⟩
= \overline{⟨(\overline{M})^{−1}δ_{v}, δ_{u}⟩} = ⟨M^{−1}δ_{v}, δ_{u}⟩ = G(v, u).

Proposition 5.1. Let π: T → H, M, and G, be as above. Let σ be an automorphism of T for which σ^{∗}M = Mσ^{∗}, where σ^{∗} is the pullback (i.e., σ^{∗}f = f ∘ σ). Then G(x, y) = G(σx, σy) for all x, y ∈ V (T).

Proof. We have δ_{σz} = σ^{∗}δ_{z} for any z ∈ V (T), and so

G(σx, σy) = ⟨M^{−1}δ_{σx}, δ_{σy}⟩ = ⟨M^{−1}σ^{∗}δ_{x}, σ^{∗}δ_{y}⟩
= ⟨(σ^{∗})^{−1}M^{−1}σ^{∗}δ_{x}, δ_{y}⟩ = ⟨M^{−1}δ_{x}, δ_{y}⟩ = G(x, y).  □

We introduce some further notions in order to derive additional properties of the Green function. For a directed edge e = (u, v) of the covering tree, consider the subtree T_{e} consisting of v’s connected component in T − e, together with e itself. Thus T_{e} contains exactly those vertices contained in a non-backtracking path from u that begins with e. T_{e} is considered to be rooted at u, which is of degree 1 in it. For any vertex x, the unique neighbour closer to the root referred to as x’s parent; the other neighbours are x’s children.

Definition 5.2. Let T_{e} be a tree as above, e = (u, v). The relative kernel of M with respect to e, denoted ker_{e} M, is the subspace of l^{2}(V (T)) consisting of functions f supported on T_{e} for which Mf is zero on T_{e} \ {u}. The relative null-kernel, denoted ker_{e}^{0} M, is the subspace of the relative kernel consisting of those functions, f, for which f(u) = 0.

It is clear that either ker_{e} M = ker_{e}^{0} M or else ker_{e} M/ ker_{e}^{0} M is one-dimensional.

Lemma 5.3. Let M be invertible and let e = (u, v).

(i) If G(u, u) ≠ 0, then dim(ker_{e} M) = 1.

(ii) If G(u, u) = G(u, v) = 0, then dim(ker_{e} M) = 1.

(iii) If G(u, u) = 0 and G(u, v) ≠ 0, then dim(ker_{e}^{0} M) = 1.

This lemma shows that ker_{e} M is one-dimensional or two-dimensional, with the latter only possible in the case where G(u, u) = 0 and G(u, v) ≠ 0. We do not know of any operator where ker_{e} M is two-dimensional, or whether such an example exists. There is a class of M’s where there are edges for which G(u, u) = 0 and G(u, v) ≠ 0 (see Section 8.1).

Proof. Assume first G(u, u) ≠ 0. Consider the function

f(w) = \begin{cases}G(u, w) & w ∈ T_{e} \\ 0 & w ∉ T_{e} \end{cases} .

Mf differs from MG(x, ·) = δ_{u} only at u and outside T_{e}, and therefore f ∈ ker_{e} M. Since f(u) ≠ 0, the dimension of ker_{e} M is at least 1. To show that the dimension is not larger than one, suppose that g ∈ ker_{e} M, and define g̃ via

g̃(w) = \begin{cases}G(u, u)g(w) & if w ∈ V (T_{e}), \\ G(u, w)g(u) & otherwise. \end{cases}

Thus g̃ is proportional to g on T_{e} and to G(u, ·) outside. The two definitions coincide at u. It follows that Mg̃ is supported on u, and so g̃ is proportional to G(u, ·) and hence g is proportional to f.

Assume from here on that G(u, u) = 0. Consider the restriction of the G(u, ·) to the subtrees emerging from u. Since the Green function is unique, G(u, ·) must vanish on all but one of these trees (otherwise the restriction of G(u, ·) to each subtree gives another function with Mf = δ_{u}). In particular, there is a unique neighbour x of u with G(x, u) ≠ 0.

If G(u, v) = 0, then the we repeat the argument above with f the restriction to T_{e} of G(x, ·). As above, f ∈ ker_{e}. If there is another g ∈ ker_{e}, then let

g̃(w) = \begin{cases}G(x, u)g(w) & if w ∈ V (T_{e}), \\ G(x, w)g(u) & otherwise. \end{cases}

This time, Mg̃ is supported on {x, u}, and so g̃ = c_{1}G(x, ·) + c_{2}G(u, ·). Applying this at x and u gives

G(x, x)g(u) = c_{1}G(x, x) + c_{2}G(u, x), G(x, u)g(u) = c_{1}G(x, u) + c_{2}G(u, u)

and solving for c_{1}, c_{2} shows c_{2} = 0 (and c_{1} = g(u)). Thus g is proportional to f, and dim(ker_{e}) = 1.

Finally, if x = v, then G(u, ·) vanishes outside T_{e}, and so f = G(u, ·) ∈ ker_{e}^{0} M implying the dimension is at least one. Conversely, for any g ∈ ker_{e}^{0} M the function Mg is supported on u and hence must be proportional to f, implying the dimension is exactly one. □ Corollary 5.4. If e = (u, v) and x, y are not in V (T_{e}) \ {u}, then the restrictions of G(x, ·) and G(y, ·) to T_{e} are proportional. Proof. The cases G(u, u) ≠ 0 and G(u, u) = G(u, v) = 0 follow from the onedimensionality of ker_{e} M. The remaining case G(u, u) = 0 and G(u, v) ≠ 0 follows from the fact mentioned in the above proof that G(u, ·) is supported on T_{e}, so G(u, x) = G(u, y) = 0. Hence G(x, u) = G(u, x) = 0. Thus the restrictions to T_{e} of G(x, ·) and G(y, ·) are both in the one-dimensional ker_{e}^{0} M. □

6. Green Functions with finite periodic ratios

Let π: T → H and M be as in Theorem 1.4.

Definition 6.1. A finite ratio system for M is a ratio system, r, whose values, r_{e}, are never 0 or ∞; in other words, (1) always holds.

As a step toward proving Theorem 1.4, we first discuss the simpler case where all ratios are finite.

Theorem 6.2. The following are equivalent:

(1) M is invertible and G(u, u) ≠ 0 for all u,

(2) there is a finite ratio system for M with α(r) < 1.

We start the proof of Theorem 6.2 with the assumption that M is invertible and G(u, u) ≠ 0 for all u, and prove that there is a ratio system for M with α(r) < 1. Indeed, for any edge e_{0} ∈ H, take some edge e = (u, v) of type e_{0} and define

r_{e_{0}} = \frac{G(u, v)}{G(u, u)}.

For a path p⃗ = {e_{i}}_{i=0}^{n} in H, it will be convenient to denote r(p⃗) = ∏ r_{e_{i}}, i.e., the product of r_{e} over p⃗, with repeated edges taken into account.

For an edge e, we consider the function f on T_{e} defined by f = \frac{G(u,·)}{G(u,u)}. As noted above, f ∈ ker_{e} M. The following relates f to the finite ratio system.

Claim 6.3. Consider a non-backtracking path p⃗ in H beginning with e_{0}. Lift the path to H̃, starting at u and let y be the terminal vertex. Then f(y) = r(p⃗).

Proof. We induct on the path’s length. If n = 0 the claim states f(u) = 1, which is true. If n = 1, the claim states f(v) = r_{e} which is also true by the choice of r. For the inductive step, let e′ = (x, y) be an edge of type e_{k} in T_{e}, with x closer to the root, then it suffices to show that f(y) = r_{e_{k}}f(x) (this is why we call r a finite ratio system).

Since the restriction of f to T_{e′} is in ker_{e′} M, by Lemma 5.3 it is proportional to G(x, ·), and so

\frac{f(y)}{f(x)} = \frac{G(x, y)}{G(x, x)} = r_{e_{k}}.  □

To check that r is indeed a finite ratio system, note that (Mf)(v) = 0. However,

(Mf)(v) = m_{vv}r_{e} + m_{e^{−1}} + ∑_{e→e′} m_{e′}r_{e}r_{e′},

which is just (1).

It remains to show that α(r) < 1. Consider S_{n} = ∑_{ρ(x,u)=n} |f(x)|^{2}, i.e., the contribution to ∥f(x)∥^{2} from all x at level n of T_{e}. The matrix R is constructed so that S_{n} is the square of the l^{2}-norm of the row corresponding to e_{0} in R^{n} (this is proved by induction using Claim 6.3).

By Perron-Frobenius theory, there is an e_{0} and c > 0 such that S_{n} ≥ cα(r)^{n} for n large (see e.g., [HJ85, Theorem 8.1.26]). Since ∑_{n} S_{n} = ∥f_{n}∥^{2} is finite, it must be that α(r) < 1.

We now prove the second direction of Theorem 6.2. Given a ratio system r with α(r) < 1, we will first construct the Green function for M, and then use it to construct the inverse of M. For a vertex u ∈ T we define f_{u}(v) = r(p⃗(u, v)), where p⃗(u, v) is (the projection to H of) the unique path from u to v. By convention, f_{u}(u) = 1. Note that f_{u} ∈ l^{2}, since for all ε > 0 we have S_{n} = ∑_{ρ(x,u)=n} |f(x)|^{2} = (α(r) + ε)^{n} for large n, which converges if ε < 1 − α(r).

Claim 6.4. We have (Mf_{u})(v) = 0 whenever v ≠ u. If e is (the type of) an edge incident to u then (Mf_{u})(u) = 0 iff r_{e}r_{e^{−1}} = 1. In particular, either r_{e}r_{e^{−1}} = 1 for all edges, or for no edges.

Proof. When v ≠ u the claim is immediate from (1).

Let e be an edges originating at u. We have (Mf_{u})(u) = m_{uu} + ∑_{e′=(u,v)} m_{e′}r_{e′}, where the sum is over all edges originating at u. Multiplying this by r_{e^{−1}} and subtracting (1) for e^{−1} gives

r_{e^{−1}}(Mf_{u})(u) = m_{e}(r_{e}r_{e^{−1}} − 1).

If r_{e}r_{e^{−1}} = 1, then r_{e^{−1}} ≠ 0 and therefor (Mf_{u})(u) must be 0. If r_{e}r_{e^{−1}} ≠ 1, then (since we assume m_{e} ≠ 0) (Mf_{u})(u) cannot be 0.

It follows that if e, e′ are two edges incident on u, then r_{e}r_{e^{−1}} and r_{e′}r_{e^{′−1}} are either both 1 or both different from 1. Since H is connected, the same holds for any two edges. □

We now show that r_{e}r_{e^{−1}} ≠ 1 for all e. Assume the contrary. Take some nonbacktracking cycle p⃗ ∈ H, then also r(p⃗)r(p^{−1}) = 1, and so at least one of the two has absolute value at least one. Without loss of generality suppose |r(p⃗)| ≥ 1. However, in this case f_{u} cannot be in l^{2}, since |f_{u}| ≥ 1 at all endpoints of the path that is the lifting of p⃗ repeated any number of times.

Thus we find that (Mf_{u})(u) ≠ 0 for all u. Consequently, there is a function g_{u} proportional to f_{u} such that (Mg_{u}) = δ_{u}. Let us define G̃(u, v) = g_{u}(v). Our next goal is to prove that G̃ is the Green function for M. Let us establish some of its properties ^{1}.

First, note that there are constants K_{1}, K_{2} such that for any x, z and any y on the path [x, z]

K_{1} |G̃(x, z)| ≤ |G̃(x, y)G̃(y, z)| ≤ K_{2} |G̃(x, z)| .  (3)

This follows from the definition of G̃ in terms of the finite ratio system, r, and the fact that G̃(y, y) takes on only finitely many values as it depends only on y’s type.

The second property is that G̃(x, ·) and G̃(·, x) are in l^{2}. Moreover, multiplying a row or a column of G̃ by a “slowly increasing function” (like that in the lemma that follows) still yields an l^{2} function. Recall that we denote the distance between vertices x, y in T by ρ(x, y).

Claim 6.5. For any vertex u, let h_{1} = ρ(u, ·)G̃(u, ·) and h_{2} = ρ(u, ·)G̃(·, u). There is some constant c independent of u such that ∥h_{1}∥_{2} < c and ∥h_{2}∥_{2} < c.

1Note that since M is a symmetric operator, we expect G̃ to be symmetric as well. While this fact has a direct proof, the following lemma is easier and suffices for our purposes. The symmetry of G̃ will eventually follow by proving that G̃ is the Green function of M.

Proof. Since there are finitely many types for u, it suffices to consider a single u. As before, let S_{n} = ∑_{ρ(x,u)=n} |G̃(u, x)|^{2}, so that for any ε > 0 we have S_{n} = (α(r) + ε)^{n} for large n. It follows that

∥h_{1}∥^{2} = ∑_{n} n^{2}S_{n} < ∞.

For h_{2}, consider S′_{n} = ∑_{ρ(x,u)=n} |G̃(x, u)|^{2}. This equals the l^{2} norm of a column of R^{n}, and therefore has the same asymptotics as S_{n}. □

The next two claims imply that M is invertible.

Claim 6.6. For every h ∈ l^{2}(T) there exists θ ∈ l^{2}(T) such that Mθ = h.

Claim 6.7. The kernel of M is trivial.

Proof of Claim 6.6. Given h ∈ l^{2}(T), define θ as

θ(v) = ∑_{u∈V (T)} G̃(u, v)h(u);

Claim 6.5 and Cauchy-Schwarz combined imply that the above sum converges. It also follows that Mθ = h at each vertex. It remains to show that θ ∈ l^{2}(T), so we need to bound

\begin{aligned}∑_{v} |θ(v)|^{2} & ≤ ∑_{u,v,w} |h(u)h(w)G̃(u, v)G̃(w, v)| \\ & = ∑_{u,w} |h(u)h(w)H(u, w)|, \end{aligned}  (4)

where

H(u, w) = ∑_{v} |G̃(u, v)G̃(w, v)|.

The tree paths [v, u] and [v, w] separate at some point x, which is along the path [u, w] (possibly, x = u or x = w.) Separating the last sum according to the value of x = x(v, u, w), using (3) and summing over v we get

\begin{aligned}H(u, w) & ≤ c ∑ ; \begin{aligned}u & x & w \\ & v \end{aligned} |G̃(u, x)G̃(w, x)G̃(x, v)^{2}| \\ & ≤ c′ \begin{matrix}& ∑ \\ u & x & w \end{matrix} |G̃(u, x)G̃(w, x)|, \end{aligned}  (5)

where the first diagram means that we sum over all vertices u, w, v, x such that the subtree they span has the given structure (with x at the branching point in the first case, and along the path in the second). Note that it is possible to use (3) at this stage to eliminate x. We keep x to facilitate discussion in the next section. Inserting (5) in (4) gives

∑_{v} |θ(v)|^{2} ≤ c \begin{matrix}& ∑ \\ u & x & w \end{matrix} |h(u)h(w)G̃(u, x)G̃(w, x)|.

Fix an arbitrary root in V (T) and let z be the last common ancestor of u, w in the above sum. Either x ∈ [u, z] or x ∈ [w, z]. We bound the sum for x ∈ [u, z], the proof for other sum being identical. We need to show that

∑ ; \begin{aligned}& z \\ x & & w \\ u \end{aligned} |h(u)h(w)G̃(u, x)G̃(w, x)| < ∞.

Note that z must be the common ancestor of x, w. To avoid division by zero, denote for any two vertices u, v

ρ′(u, v) = max{1, ρ(u, v)}.

Using (3) for z ∈ [x, w] and Cauchy-Schwarz we have

|h(u)h(w)G̃(u, x)G̃(w, x)| ≤ c|h(u)h(w)G̃(u, x)G̃(z, x)G̃(w, z)|

≤ c|h(w)G̃(u, x)G̃(z, x)\frac{ρ′(z, x)ρ′(x, u)}{ρ′(z, w)}|^{2}

+ c|h(u)G̃(w, z)\frac{ρ′(z, w)}{ρ′(z, x)ρ′(x, u)}|^{2}.

Consider the first term. Its contribution to the sum can be written as

c ∑ ; \begin{aligned}& z \\ x & & w \\ u \end{aligned} |h(w)G̃(u, x)G̃(z, x)\frac{ρ′(z, x)ρ′(x, u)}{ρ′(z, w)}|^{2}.

u lies below x in the tree, and the sum of ρ′(x, u)^{2}|G̃(u, x)|^{2} over such u is uniformly bounded. Similarly we can sum ρ′(z, x)^{2}|G̃(z, x)|^{2} over all x below z. Summing over u and then over x we are left with

c ∑ ; \begin{matrix}z \\ w \end{matrix} \frac{|h(w)|^{2}}{ρ′(z, w)^{2}} .

Since z must lie on the path from w to the root, summing over z, we are left with

c ∑_{n=0}^{∞} \frac{|h(w)|^{2}}{(max(1, n))^{2}} ≤ c′∥h∥_{2}^{2} < ∞.

The second term above is similarly bounded, except that we sum first over w, then over z, x and u in that order to end up with c′∥h∥_{2}^{2} again. □

Proof of Claim 6.7. Suppose that Mf = 0. Then for every function g ∈ l^{2}(T), using the symmetry of M,

0 = ⟨Mf, g⟩ = ⟨f, M^{∗}g⟩ = ⟨f, \overline{M}g⟩.

Since we have a finite ratio system for M with α < 1, we also have one for \overline{M}. By Claim 6.6 for \overline{M}, its image is all of l^{2}, and so for every h ∈ l^{2}(T) we have 0 = ⟨f, h⟩. Thus f must be 0. □

This completes the proof of Theorem 6.2. Now we give a proof of Theorem 1.6 in the case of finite ratio systems.

Theorem 6.8. If there is a finite ratio system for M with α(r) = 1 then M is not invertible.

Proof. Fix some edge e = (u, v) ∈ H̃. Using a finite ratio system r with α(r) = 1 we consider the function

f_{n}(x) = \begin{cases}r(p⃗) & if x ∈ T_{e} and ρ(x, u) = n, \\ 0 & otherwise, \end{cases}

and let F_{n} = ∑_{k=0}^{n} f_{k}. Thus ∥F_{n}∥^{2} = ∑^{n} ∥f_{k}∥^{2}. Since MF_{n} is 0 on levels 1, …, n−1 of the tree, it is supported on level 0 and levels n, n + 1. Consequently ∥MF_{n}∥^{2} = O(∥f_{n}∥^{2}).

Recall that ∥f_{n}∥^{2} is the sum of the row corresponding to e in R^{n}. Since the Perron eigenvalue of R is 1, this sum grows polynomially in n and we have ∥f_{n}∥^{2} = P (n) + o(1) for some polynomial P. By choosing the edge e to be in the support of the Perron eigenfunction of R we can guarantee P ≢ 0.

Assume deg P = k (which might be 0), with leading term cn^{k}. Then ∥F_{n}∥^{2} = cn^{k+1}/(k + 1) + O(n^{k}), while ∥MF_{n}∥ = O(n^{k}). Thus ∥MF_{n}∥/∥F_{n}∥ → 0 as n → ∞, and so M cannot have a bounded inverse. □

Corollary 6.9. For any finite graph H, we have ρ(B̃) = \sqrt{gr}. Moreover, \{λ : |λ| = \sqrt{gr}\} ⊂ σ(B̃).

Proof. By Theorem 1.5, it suffices to show that M = Q_{λ} is invertible for |λ| > \sqrt{gr}, and is not invertible for |λ| = \sqrt{gr}. Since m_{vv} = d_{v} − 1 + λ^{2} and m_{e} = −λ for any e, it is straightforward to see that r_{e} ≡ λ^{−1} satisfies (1). This finite ratio system has α(r) = λ^{−2}gr. Theorem 6.2 shows that Q_{λ} is invertible whenever |λ| > \sqrt{gr}. However, if |λ| = \sqrt{gr} then α(r) = 1 and Theorem 6.8 implies that Q_{λ} is singular. □

7. Zeroes and Infinities

In this section we extend the results of the previous section to the case where G(u, u) could vanishes for some u, i.e., where ratios are allowed to be zero or infinity; we finish the proofs of Theorem 1.4 and 1.5. We discuss some examples where G(u, u) vanishes for some u in Section 8.

We start with some remarks about Definition 1.3. Conditions (b) and (c) replace condition (a) in the situation of zero and infinite ratios. Condition (b) is easy to justify: m_{e^{−1}}/r_{e} = ∞, so there must be an infinite term in the sum as well. Condition (c) effectively states that the only way to have r_{f} = ∞ is as in condition (b). In particular, there cannot be two edges leaving a vertex with infinite ratios (since then their inverses both must and cannot have ratio zero).

As before, we need to extend r to non-backtracking paths, and would like r(p⃗) to be the product of the ratios along the edges of the path. In the presence of infinite ratios this needs clarification. We define r(p⃗) inductively. For paths of a single edge, r(e) = r_{e}, and for the an empty path, ε, r(ε) = 1).

For longer paths, note that an infinite ratio must be preceded by a zero ratio, so we must determine the value of 0 · ∞. For paths of length m ≥ 2 we define r(p⃗) inductively as follows:

r(e_{1}, …, e_{m}) = \begin{cases}r_{e_{1}}r(e_{2}, …, e_{m}) & r_{e_{1}}, r_{e_{2}} ≠ ∞, \\ −_{\frac{m_{e_{2}}}{m_{e{−1 \atop 1}}}} r(e_{3}, …, e_{m}) & r_{e_{1}} = 0, r_{e_{2}} = ∞, \\ ∞ & r_{e_{1}} = ∞. \end{cases}  (6)

In the case r_{e_{1}} = 0 and r_{e_{2}} = ∞, we effectively define “r_{e_{1}}r_{e_{2}}” (literally zero times infinity) to be r(e_{1}, e_{2}) = −m_{e_{2}}/m_{e_{1}^{−1}}, since the uniqueness of G implies that G(v, v) = 0 and G(v, u) ≠ 0 implies that G(v, w) ≠ 0 for exactly one other neighbour of u, and furthermore m_{vw}G(v, w) + m_{vu}G(v, u) = 0.

We remark that with this definition of r(p⃗), the proof of Theorem 6.8 carries over to prove Theorem 1.6.

We first assume that M is invertible, and find the promised ratio system {r_{e}}. Let G be the Green function. Let e = (u, v) be some edge in T of type e_{0}. We define r_{e} to be the generalized ratio G(u, v)/G(u, u) as before, provided G(u, v) and G(u, u) do not both vanish. Otherwise, since MG(u, ·) does not vanish at u, there must be a neighbour x of u with G(u, x) ≠ 0. We then define r_{e} = G(x, v)/G(x, u). In short there is some x, either x = u or x ∉ T_{e} such that G(u, x), G(x, v) are not both zero and

r_{e} = G(x, v)/G(x, u).

By Corollary 5.4, this ratio does not depend on our choice of x. As before, r_{e} depends only on the type of e, so this it is naturally equivalent to a function on edges of H.

Claim 7.1. The function r defined above is a ratio system for M with α(r) < 1.

Proof. Throughout we assume that e = (u, v) and that x is either u or outside T_{e} and G(x, v)/G(x, u) is defined (and therefore equals r_{e}). In particular x ≠ v and so MG(x, ·) = δ_{x} vanishes at v. Thus we have

0 = m_{vv}G(x, v) + m_{e^{−1}}G(x, u) + ∑_{\begin{matrix}w∼v \\ w≠u \end{matrix}} m_{vw}G(x, w).  (7)

To check (a), note that r_{e} ≠ 0 implies G(x, v) ≠ 0, and so the same x may be used to find r_{f} for f = (v, w). Writing G(x, w) = G(x, v)r_{vw} in (7) gives

0 = m_{vv} + m_{e^{−1}} \frac{G(x, u)}{G(x, v)} + ∑_{\begin{matrix}w∼v \\ w≠u \end{matrix}} m_{vw}r_{vw}.

This is just (1), since \frac{G(x,u)}{G(x,v)} = 1/r_{e} (meaning 0 if r_{e} = ∞).

To prove (b), suppose that r_{e} = 0. Then we have G(x, u) ≠ 0 and G(x, v) = 0, and so (7) gives

∑_{\begin{matrix}w∼v \\ w≠u \end{matrix}} m_{vw}G(x, w) = −m_{vu}G(x, u) ≠ 0

Thus not all of G(x, w) are 0. Let w ∼ v such that G(x, w) ≠ 0, then the same x can be used to find r_{f} for f = (v, w), and r_{vw} = G(x, w)/G(x, v) = ∞.

To verify (c), note that if r_{f} = ∞ for f = (v, w), then by Corollary 5.4, we must have G(x, v) = 0 for all x ∉ V (T_{f}) \ {v}. In particular G(v, v) = 0. It follows that G(v, w) ≠ 0, so w can be used to find r_{f^{−1}} and so r_{f^{−1}} = \frac{G(w,v)}{G(w,w)} ≠ 0. Finally, to check that r_{e} = 0, suppose x is used to find r_{e}. Then G(x, v) = 0, for otherwise x could be used to find r_{f}, and r_{f} would be finite.

It remains to show that α(r) < 1. As before, we show that the Perron eigenvalue of R satisfies α(r) < 1 by proving that for all e with r_{e} ≠ 0 the sum of row e in R^{k} tends to zero with k. Pick an edge ẽ = (u, v) of type e with r_{e} ≠ 0. As above, fix some vertex x ∉ Tẽ \ {u} satisfying G(x, v) ≠ 0. We claim that

∑_{y∈Tẽ} |G(x, y)|^{2} = |G(x, u)|^{2} + |G(x, v)|^{2} ∑_{f} ∑_{k=0}^{∞}(R^{k})_{ef}  (8)

This implies the required result, since the left-hand-side is finite. To see (8), for every y ∈ Tẽ except for u, the path [v, y] in T projects to some non-backtracking walk p⃗_{y} in H. This gives a bijection between such y and non-backtracking walks in H that begin with an edge e′ such that e → e′. We have G(x, y) = G(x, v)r(p⃗_{y}).

The definition of R is such that

(R^{k})_{ef} = ∑ |rp⃗|^{2},

where the sum is over paths in H that begin with an edge e′ such that e → e′, end with edge f and, for some m, contain k + m steps with m edges with r_{e_{i}} = ∞. The above identity follows. □

Conversely, given a ratio system r with α(r) < 1, we construct a candidate for the Green function G̃(·, ·) as in the proof of Theorem 6.2 and use it to construct M^{−1}. Our first goal is to find for each u a function f_{u} so that Mf_{u} = cδ_{u}. We can then define G̃(u, v) = c^{−1}f_{u}(v).

Generally we take f_{u}(x) = r(p⃗) where p⃗ is (the projection of) the path from u to x. However, if there is an edge e leaving u with r_{e} = ∞, then this results in some infinite values of f_{u}. In this case, roughly speaking, we “divide by ∞”. All finite values will become 0, and the infinite ones will become finite. We shall now make this more precise.

Let V_{∞} denote the set of all u such that there is an edge e = (u, v) with r_{e} = ∞:

V_{∞} = {u : ∃v, r_{uv} = ∞}

As noted above, for u ∈ V_{∞}, the v with r_{uv} = ∞ must be unique. Define u^{∗} to be this neighbour, v; otherwise, for u ∉ V_{∞}, let u^{∗} = u. Then (recall π: T → H is the covering map) set

f_{u}(x) = \begin{cases}r(p⃗) & if u ∉ V_{∞}, where p⃗ = π([u, x]), \\ r(q⃗) & if u ∈ V_{∞} and x ∈ T_{(u,u^{∗})} \ \{u\}, where q⃗ = π([u^{∗}, x]), \\ 0 & otherwise. \end{cases} (9)

We further denote Z(u) = ∑_{e=(u,v)} m_{e}r_{e} where the sum is over edges leaving u with r_{e} ≠ ∞ (i.e., if one of the edges has r_{e} = ∞, then it is not included).

Claim 7.2. For any u we have

(Mf_{u})(u) = \begin{cases}m_{uu^{∗}} & u ∈ V_{∞}, \\ m_{uu} + Z(u) & u ∉ V_{∞}. \end{cases}  (10)

Proof. If u ∈ V_{∞} then we have r_{uu^{∗}} = ∞. Consequently f_{u} is supported on T_{uu^{∗}}, f_{u}(u) = 0 and for v ∼ u we have f_{u}(v) is 1 or 0 according to whether or not v = u^{∗}. The claim follows. For u ∉ V_{∞} we have f_{u}(u) = 1 and f_{u}(v) = r_{uv} for all neighbours v of u, so the equality holds also in this case. □

Define V_{0} = {u : m_{uu} + Z(u) = 0}.

Claim 7.3. If an edge e = (u, v) has r_{e} ∉ {0, ∞} and v ∈ V_{0}, then r_{e}r_{e^{−1}} = 1 and u ∈ V_{0}.

Proof. (1) can be written as m_{vv} + m_{e^{−1}}/r_{e} + Z(v) − m_{e^{−1}}r_{e^{−1}} = 0. If v ∈ V_{0} this becomes 1/r_{e} − r_{e^{−1}} = 0, or r_{e}r_{e^{−1}} = 1. Applying this to (1) for e^{−1} gives m_{uu} + Z(u) = 0, so u ∈ V_{0} as well. □

Claim 7.4. If u ∈ V_{0}, some edge entering u has ratio in {0, ∞}, then one edge e entering u has r_{e} = r_{e^{−1}} = ∞, and all other edges entering u have ratio 0.

Proof. If r_{vu} = 0 for some v, then by (b) there is an e = (w, u) with r_{e^{−1}} = ∞. This implies by (c) that all edges e′ entering u except for e have r_{e′} = 0. By (c), r_{e} ≠ 0. Applying (a) to e reduces to m_{uu} + m_{e^{−1}}/r_{e} + Z(u) = 0. Since u ∈ V_{0}, we must have r_{e} = ∞.

If r_{e} = ∞ for some e = (v, u), then we claim r_{e^{−1}} = ∞: if it were finite, applying (a) to e would give m_{uu} + Z(u) − m_{e^{−1}}r_{e^{−1}} = 0. This implies r_{e^{−1}} = 0, contradicting (c). Since r_{e} = r_{e^{−1}} = ∞, again by (c) all edges e′ entering u except for e have r_{e′} = 0. □

Claim 7.5. V_{0} ⊂ V_{∞}.

Proof. Suppose that u ∈ V_{0} \V_{∞}. Since there are no edges with infinite ratio leaving u, by Claim 7.4 all edges entering u have finite nonzero ratios. By Claim 7.3 this implies that all of u’s neighbours are in V_{0}, and by Claim 7.4 they are all in V_{0} \ V_{∞}.

It follows that if V_{0}\V_{∞} is nonempty then it must be the entire tree. If V_{0}\V_{∞} = T then for all edges r_{e}r_{e^{−1}} = 1. Then (as in Claim 6.4) taking a non-backtracking cycle, p⃗, in H gives r(p⃗)r(p^{−1}) = 1, and so α ≥ 1 — a contradiction. □

Claim 7.6. For any u, (Mf_{u})(u) ≠ 0.

Proof. By Claim 7.2, either u ∈ V_{∞} and then (Mf_{u})(u) = m_{uu^{∗}} ≠ 0, or u ∉ V_{∞}. In the latter case u ∉ V_{0}, and therefore (Mf_{u})(u) = m_{uu} + Z(u) ≠ 0. □

It follows that we may define

G̃(u, x) = \frac{f_{u}(x)}{(Mf_{u})(u)},  (11)

so that MG̃(u, ·) = δ_{u}. It remains to prove the generalized form of Claim 6.6:

Claim 7.7. Given a ratio system with α(r) < 1, for every h ∈ l^{2}(T) there exists a θ ∈ l^{2}(T) such that Mθ = h.

The proof is very similar to the proof of Claim 6.6, and we only point out the differences.

Proof. Equation (3) only fails if G(y, y) = 0. This problem is easily overcome by shifting the splitting point from y to y^{∗}, which is the unique neighbour of y satisfying r_{yy^{∗}} = ∞. When G(y, y) ≠ 0 we define y^{∗} to be y. We have for suitable K_{1}, K_{2} and any y ∈ [x, z]

K_{1}|G̃(x, z)| ≤ |G̃(x, y^{∗})G̃(y^{∗}, z)| ≤ K_{2}|G̃(x, z)|.  (3′)

This follows from the definition of G̃ and the fact that y has only finitely many types.

As in the preceding section, we define H(u, w) = ∑_{v} |G̃(u, v)G̃(w, v)|. Using (3′) gives the bound

H(u, w) ≤ c \begin{matrix}& ∑ \\ u & x & w \end{matrix} |G̃(u, x^{∗})G̃(x^{∗}, w)|.

In all subsequent estimates x^{∗} and z^{∗}, respectively, take the place of x and z in all instances of G̃, but x and z remain unchanged in the “tree sum” notation and in ρ′.

The only difference is that in place of Claim 6.5 we need bounds of the form

∑_{x} ρ(u, x)^{2} (|G̃(u, x^{∗})|^{2} + |G̃(x^{∗}, u)|^{2}) < c.  (12)

Such bounds are an easy consequence of Claim 6.5: The map x ↦ x^{∗} maps no more than d_{max} + 1 x’s to each x^{∗}. Since also |ρ(x^{∗}, y^{∗}) − ρ(x, y)| ≤ 2, replacing some of the variables by their starred versions introduces at most a constant factor into the bounds at each stage of the computation. □

8. Examples

We wish to analyze two examples to highlight the necessity of considering ratio systems. Each of these examples demonstrates a general point. Then we give a third example, which seems to be the “smallest interesting example” of a graph with a non-regular universal cover. We describe the calculations needed to determine its non-backtracking spectrum. In each of these examples, the finite graph is a simple graph. In the next section we shall show how each of these can be viewed as a covering of an even smaller graph by using self-loops, multiple edges, or “passing” to a pregraph.

8.1. Example 1: Figà-Talamanca and Steger. [FTS94] contains various examples of graphs where G(u, u) = 0 for some u when M is the weighted adjacency matrix of the tree. Consider K_{4}, the complete graph on four vertices, whose six edges are written as the disjoint union of three perfect matchings, E_{1}, E_{2}, E_{3}. Let the edges in E_{i} have weight p_{i}, for some positive real p_{1}, p_{2}, p_{3}. Without loss of generality p_{1} ≥ p_{2} ≥ p_{3}. By symmetry (i.e., using Proposition 5.1), for any ratio system r, the ratios r_{e} of all directed edges of E_{i} are equal. Call the three ratios r_{1}, r_{2}, r_{3}, and consider the ratio system is r_{1} = ∞, r_{2} = r_{3} = 0. We have r(e_{k}, e_{1}) = −p_{k}/p_{1}; the condition α(r) < 1 amounts to

(p_{2}/p_{1})^{2} + (p_{3}/p_{1})^{2} < 1.

Thus the adjacency matrix for the tree is invertible with G(u, u) = 0 if p_{1}^{2} > p_{2}^{2} + p_{3}^{2}. (In [FTS94, Lemma 1.4] it is shown that if p_{1}^{2} ≤ p_{2}^{2} + p_{3}^{2} then the adjacency matrix is not invertible.)

It is of interest to note that the relative kernel with respect to an E_{1} edge is only one-dimensional (when p_{1}^{2} > p_{2}^{2} + p_{3}^{2}).

8.2. Example 2: (2, 3)-bipartite graphs. Consider the adjacency matrix of a (2, 3)-bipartite graph, i.e., a bipartite graph with vertex set V_{2} ∪ V_{3} such that each vertex in V_{k} is of degree k. Then consider r_{32} = ∞, r_{23} = 0, where e_{23} is an edge from V_{2} to V_{3} and e_{32} the opposite. This fails to be a generalized ratio for the adjacency matrix only at condition (c) of the definition. Furthermore, if we tried to omit condition (c), then this ratio system would have α < 1: A vertex of degree 3 in the universal cover has two children so r(e_{32}, e_{23}) = −1/2. This gives rise to L^{2}-functions, f, with Mf = δ_{r} for any vertex r of degree 2 (we can take f to have value 0 at all degree two vertices, and value −(−2)^{−a} at all vertices at odd distance 2a − 1 to r).

It is easy to see that the adjacency matrix is not invertible here; indeed, consider a long path in the tree, and a function supported on the degree two vertices of this path, alternating ±1; this function, f, has Mf bounded but ∥f∥ unbounded as the path length tends to infinity. This example shows that condition (c) in the definition of a ratio system cannot be omitted from Theorem 1.4.

8.3. Example 3: Case study of P_{1,2,2}. We consider here non-backtracking walks on lifts of the graph P_{1,2,2} consisting of three paths between a pair of vertices u, u′ of lengths 1, 2, 2. Thus u, u′ have degree 3 and there are two other vertices, v, v′, of degree 2. This is the same as K_{4} with an edge removed.

To find the spectrum of B(P̃_{1,2,2}) we need to determine invertibility of M = Q_{λ}. Let us look for ratio functions r_{e} that respect all the graph’s symmetries, i.e. r_{uv} = r_{uv′} = · · ·. There are only three distinct ratios:

x = r_{uv}  y = r_{uu′}  z = r_{vu}.

Thus y appears on two directed edges, and x, z on four each. The equations we need to satisfy are

(λ^{2} + 1)x + λ(1 + xz) = 0,
(λ^{2} + 2)y + λ(1 + 2xy) = 0,
(λ^{2} + 2)z + λ(1 + xz + yz) = 0.

Using the first equation to eliminate z and the second to eliminate x yields:

(y + λ^{−1}) ((2λ^{4} + 2λ^{2} + 4)y^{2} + λ^{3}(λ^{2} + 1)y − λ^{2}(λ^{2} + 1)) = 0.

This leads to the trivial solution x = y = z = −λ^{−1} and two non-trivial solutions for x, y, z (or to be precise, two branches of one solution). The condition α(r) < 1 reduces to x^{2}z^{2}(1 + 2y^{2}) < 1. A computer plot of the λ where none of the solutions has α(r) < 1 is shown in Figure 1 (the shaded region).

9. Self-loops and Pregraphs via Finite Tree Quotients

We shall show that Theorem 1.4 can be generalized to universal covers of all of the following structures: graphs/pregraphs with multiple edges, self-loops, boundaries (with boundary conditions), edge and vertex weights, and edge lengths (see [Fri93]).

The common theme is that all these structure admit some sort of “universal cover,” T that is sufficiently symmetric that a mild generalization of Theorem 1.4 holds.

First, note that Definition 1.3 makes sense for any graph homomorphism π: T → H, regardless of whether or not H is finite (and even whether or not π is a covering map).

Definition 9.1. A tree quotient is a tree, T, along with a group, G, acting on it; we denote this T/G. By V (T/G) we mean the G orbits of V (T), and similarly for E(T/G). The action of G is cofinite if V (T/G) and E(T/G) are finite; alternatively we say T/G is finite. By a symmetric local operator on T/G we mean a symmetric local operator on T that is invariant under G. By a ratio system on T we mean a ratio system as in Definition 1.3 with H there taken to be T; by a ratio system on T/G we mean a ratio system on T that is invariant under G, i.e., r can be viewed as a function r : E(T/G) → ℂ ∪ {∞}.

Any finite graph and pregraph as described in [Fri93, FT04] (possibly with boundary, self-loops, multiple edges, vertex and edge weights, and edge lengths) admits a universal cover, π: T → G; T is a tree (a graph) that inherits vertex and edge weights and lengths from G (boundary edges may be discarded with the Laplacian or adjacency matrix modified appropriately). By the universal property of T, for any two vertices in T above the same G vertex, T admits an automorphism from taking one vertex to the other. It follows that if G is the group of all automorphisms of T over G, then T/G is finite and has at most as many edges and vertices as G. Hence to generalize Theorem 1.4 to all the above situations it suffices to consider finite tree quotients T/G.

Consider a symmetric, local operator, M, on a tree quotient, T/G. The proof of Theorem 1.4 shows that a Green’s function, G, for M gives rise to generalized periodic ratios on T; Proposition 5.1 shows that generalized periodic ratios also live on T/G. Furthermore, given the periodic ratios {r_{e}} from G, we can reconstruct G via (9) and (11).

Definition 9.2. A classifying condition for a tree quotient, T/G, is a condition C = C(r) or even C = C(r, M) on generalized periodic ratios, r, such that C(r, M) is satisfied iff r arises from the Green function, G, of an invertible, symmetric, local operator, M, on T/G.

Given a tree quotient, we wish to find a classifying condition that is simple to check. Theorem 1.4 says that if π: T → H is a universal cover of a finite graph, H, and G is the group of automorphisms of T over H, then “α(r) < 1” is a classifying condition for T/G.

Our first task is to generalize the matrix R that describes α on a tree quotient, T/G. For e, f ∈ E(T) with r_{e}, r_{f} ≠ 0, we define R_{e,f} as in (2); for a, b ∈ E(T/G) pick an e with e ∈ a and set

R_{a,b} = ∑_{f∈b} R_{e,f}.

In this setting, our proof of Theorem 1.4 shows the following:

Theorem 9.3. Let C = C(r) be a condition on generalized periodic ratios of a tree quotient, T/G, such that

(a) if r arises from a Green function, then C(r) is satisfied,

(b) if r satisfies C(r), then (Mf_{u})(u) ≠ 0 for all u (with f as in (9)), and

(c) if r satisfied C(r) then G̃ is a bounded kernel, i.e., the map

h( ·) ↦ ∑_{u∈V (T)} G̃(u, ·)h(u),

is bounded in L^{2}.

Then C is a classifying condition for T/G. Furthermore,

(1) (Mf_{u})(u) ≠ 0 for all u as long as there can exist no sequence of distinct vertices, v_{0}, v_{1}, … in T for which |r([v_{0}v_{i}])| ≥ 1 for all i ≥ 1, and

(2) any function G̃: V (T) × V (T) → ℂ is a bounded kernel provided that it satisfies the bounds (3) and (12).

Now let α(r) be the spectral radius of the operator R defined above as an operator on l^{2}(V (T/G)). If G acts cofinitely on T, then R is a finite real matrix with nonnegative entries, and a periodic ratio arising from a Green function must satisfy α(r) < 1 since the Green function is in l^{2}, using the analogue of (8). Conversely, a generalized periodic ratio with α(r) < 1 yields that

R + 2R^{2} + 3R^{3} + ⋯

is a bounded operator, from which we conclude (12) and that there cannot exist distinct v_{0}, v_{1}, … ∈ V (T) with |r([v_{0}v_{i}])| ≥ 1; the cofinite action on G on T shows that ((Mf_{u})(u))^{−1} and r_{e} are uniformly bounded, yielding (3). We conclude the following theorem.

Theorem 9.4. Let G act cofinitely on T. The condition α(r) < 1, defined above, is a classifying condition for T/G.

We do not know a classifying condition when G does not act cofinitely on T.

We now demonstrate how the trees in the three examples in the previous section have smaller quotients, provided one is willing to pass to graphs or pregraphs that may have self-loops and multiple edges.

Example 1 in the previous section covers the graph consisting of one vertex with three half-loops, e_{1}, e_{2}, e_{3}, of respective weights p_{1} ≥ p_{2} ≥ p_{3}. This is how it is presented in [FTS94]; they allow any number of half-loops with weights p_{1} ≥ ⋯ ≥ p_{r}. The covering tree’s adjacency matrix is invertible iff p_{1}^{2} > p_{2}^{2} + ⋯ + p_{r}^{2}. The r half-loop example is covered by any r-regular graph whose edges can be partitioned into r perfect matchings.

Example 2 covers the pregraph with two vertices, no self-loops, with one vertex of degree two, and one vertex of degree three.

Example 3 covers the graph H = (V, E), where V = {u, v}, where there are two edges joining u and v and one half-loop at u.

10. Concluding Remarks and Further Questions

We have given a semi-algebraic characterization of invertible symmetric local operators on a finite tree quotient. It would be interesting to know what happens when the tree quotient is not finite and/or when the operator is not symmetric (with respect to l^{2} of any measure on the tree vertices). For example, the non-backtracking random walk selects at each step a uniform neighbour of X_{n} different from X_{n−1} [ABLS, OW07].

Our characterization can be used, at least in principle, to compute the various spectra of trees, including adjacency and Laplacian, and, less obviously, nonbacktracking. This may shed light on the questions mentioned in the introduction. One interesting question, especially for two-dimensional non-backtracking spectrum, is to know if there is a natural spectral measure there, analogous to the Wigner semicircle law, as done by McKay for regular base graphs. Specifically, we conjecture that for any finite graph H there is a measure μ supported on the non-backtracking spectrum of the universal cover H̃, such that the uniform measure on σ(H^{n}) converges in probability (in a suitable topology) to μ, where H^{n} is a random uniform n-lift of H (possibly with some corrections, say around ±1).

The proof of Theorem 1.6 is based on explicitly constructing approximate eigenfunctions when there is a ratio system with α = 1. It would be nice to be able to find a sequence of approximate eigenfunctions of M − λ for general λ is M’s spectrum.

Finally we believe that for λ on the boundary of the spectrum of M (as before), M − λI, has a ratio system, r, with α(r) = 1. In particular, if {λ_{n}} is a sequence of complex numbers with a finite limit, λ, and M is as usual, and r_{n} is a ratio system for M − λ_{n}, then r_{n} has a limit point, r, where we compactify ℂ ∪ {∞} as usual. Is r necessarily a ratio system? In particular is it impossible to have r_{e} = r_{f} = ∞ for two edges, e, f, with the same tail? If this does happen, might it still be possible to define α for the limit point, r?

References

[ABLS] N. Alon, I. Benjamini, E. Lubetzky, and S. Sodin. Non-backtracking random walks mix faster. to appear.

[AHL02] N. Alon, S. Hoory, and N. Linial. The Moore bound for irregular graphs. Graphs Combin., 18(1):53–57, 2002.

[Bas92] H. Bass. The Ihara-Selberg zeta function of a tree lattice. Internat. J. Math., 3(6):717– 797, 1992.

[BS87] A. Broder and E. Shamir. On the second eigenvalue of random regular graphs. In The 28th Annual Symposium on Foundations of Computer Science, pages 286–294, 1987.

[Fri] J. Friedman. A proof of Alon’s second eigenvalue conjecture. Memoirs of the A.M.S., to appear.

[Fri91] Joel Friedman. On the second eigenvalue and random walks in random d-regular graphs. Combinatorica, 11(4):331–362, 1991.

[Fri93] Joel Friedman. Some geometric aspects of graphs and their eigenfunctions. Duke Math. J., 69(3):487–525, 1993.

[Fri03] J. Friedman. Relative expanders or weakly relatively Ramanujan graphs. Duke Math. J., 118(1):19–35, 2003.

[FT04] Joel Friedman and Jean-Pierre Tillich. Wave equation for graphs and the edge-based laplacian. Pacific Journal of Mathematics, 216(2):229–266, 2004.

[FTS94] Alessandro Figà-Talamanca and Tim Steger. Harmonic analysis for anisotropic random walks on homogeneous trees. Mem. Amer. Math. Soc., 110(531):xii+68, 1994.

[Gal63] R. G. Gallager. Low density parity check codes. MIT Press, Cambridge, MA, 1963.

[Has89] K. Hashimoto. Zeta functions of finite graphs and representations of p-adic groups. In Automorphic forms and geometry of arithmetic varieties, volume 15 of Adv. Stud. Pure Math., pages 211–280. Academic Press, Boston, MA, 1989.

[HJ85] R. A. Horn and C. R. Johnson. Matrix analysis. Cambridge University Press, Cambridge, 1985.

[HLW] S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. to appear.

[Hoo05] S. Hoory. A lower bound on the spectral radius of the universal cover of a graph. J. Combin. Theory Ser. B, 93(1):33–43, 2005.

[KS00] M. Kotani and T. Sunada. Zeta functions of finite graphs. J. Math. Sci. Univ. Tokyo, 7(1):7–25, 2000.

[OW07] R. Ortner and W. Woess. Non-backtracking random walks and cogrowth of graphs. Canad. J. Math., 59(4):828–844, 2007.

[RU] T. Richardson and R. Urbanke. Modern coding theory. Draft of the book,

       http://lthcwww.epfl.ch/papers/mct.ps.

[Rud91] W. Rudin. Functional analysis. International Series in Pure and Applied Mathematics. McGraw-Hill Inc., New York, second edition, 1991.

[Sho04] A. Shokrollahi. LDPC codes: an introduction. In Coding, cryptography and combinatorics, volume 23 of Progr. Comput. Sci. Appl. Logic, pages 85–110. Birkhäuser, Basel, 2004.

[ST] H. Stark and A. Terras. Zeta functions of finite graphs and coverings, part iii. http://math.ucsd.edu/ aterras/BrauerSiegel.pdf.

(Omer Angel) Math, UofT

  E-mail address: angel@math.utoronto.ca

(Joel Friedman) CS, UBC

E-mail address: jf@cs.ubc.ca

(Shlomo Hoory) Haifa Research Lab., IBM

  E-mail address: shlomoh@il.ibm.com