The Non-Backtracking Spectrum of the Universal Cover of a Graph

1.2. Main results.

• The paper characterizes when a lifted symmetric local operator on a universal cover is invertible using polynomial ratio-system equations and a decay condition α(r) < 1.The criterion is explicit in the finite base graph and spectral parameter, making the universal-cover spectrum algorithmically determined.Source: §1 · p. 2, §1.2 · p. 7

1.1. Motivation.

• For non-backtracking operators, the same ratio-system criterion characterizes the spectrum of the lifted operator, whose spectrum may be complex because the operator is not self-adjoint.Non-backtracking walks are encoded by a matrix indexed by directed edges, and its powers count walks of corresponding lengths.Source: §1 · p. 2
• For non-regular graphs, the universal-cover non-backtracking spectrum can have two-dimensional structure in the complex plane, unlike the circle-and-interval form for regular graphs.The paper uses K4 with one edge deleted as an example of nontrivial spectrum and illustrates it in Figure 1.Source: Figure 1 · p. 3, §1.1 · p. 4

Bounds for graphs with large girth.

• The non-backtracking spectral radius of the universal cover satisfies ρ(eB) = √gr, linking operator growth to the tree’s growth rate.This relation further motivates the graph-theoretical Riemann hypothesis proposed by Stark and Terras.Source: §1.1 · p. 4, Bounds for graphs with large girth · p. 5

Alon’s conjecture.

• Experiments indicate that the new non-backtracking spectrum of large random lifts approaches the universal-cover spectrum, suggesting a generalization of Alon’s second eigenvalue conjecture.For a random 300-lift of K4 minus an edge, Figure 2 compares the lift spectrum with the universal-cover region and base-graph spectrum.Source: §1 · p. 2, Figure 2 · p. 3, Alon’s conjecture · p. 4

1.2. Main results.

• The method rests on Green-function decay ratios that depend only on the projected edge type, enabling reconstruction of the Green function from periodic ratios.The paper explains this through automorphisms of the universal cover and a grafting argument that would otherwise produce multiple Green functions.Source: §1.2 · pp. 6–7
• The framework extends beyond simple graphs to finite tree quotients and supports applications to adjacency matrices, Laplacians, and non-backtracking operators.The paper also discusses graphs with self-loops, multiple edges, weights, lengths, and related pregraph structures.Source: §1.2 · p. 7

• A non-backtracking walk follows directed edges without immediately traversing an inverse edge, and B acts on directed-edge functions to encode such walks.Source: §2 · pp. 8–9
• The universal cover is the tree cover constructed from finite non-backtracking walks, and every other cover factors through it.Source: §2 · p. 8
• An n-lift has n copies of each base vertex, with independently chosen perfect matchings over base edges defining a natural random-lift distribution.Source: §2 · pp. 8–9
• The non-backtracking spectrum is the spectrum of B and may contain complex values, unlike the self-adjoint adjacency spectrum.Source: §2 · p. 9
• The growth rate gr of the universal cover is the exponential rate of ball growth and equals the Perron–Frobenius eigenvalue of B.Source: §2 · p. 9

• The spectrum of a bounded operator is characterized through eigenfunctions, adjoint eigenfunctions, or approximate eigenfunctions; for symmetric operators, approximate eigenfunctions suffice.Source: §3 · pp. 9–10
• For non-symmetric B, conjugation by edge reversal relates B to its adjoint, so checking the approximate-eigenfunction condition suffices to identify its spectrum.Source: §3 · p. 10
• For finite regular graphs, Qλ is singular exactly when λ satisfies λ^2 − µλ + d − 1 = 0 for some adjacency eigenvalue µ.Source: §3 · p. 10
• The determinant identity det(Qλ) = det(X − λI) makes non-backtracking eigenvalue computation accessible through standard matrix algorithms.Source: §3 · p. 10
• For infinite graphs, the proof relates approximate eigenfunctions of Qλ and B−λI through 0-form and 1-form sum operators, excluding λ = ±1 in the main equivalence.Source: §3 · pp. 10–11
• The non-backtracking spectrum is confined to an annulus and two real intervals determined by minimum and maximum degrees.Source: §3 · p. 12

• For every bipartite graph, the non-backtracking spectrum is invariant under reflection across both the real and imaginary axes; trees therefore have this fourfold symmetry.Source: §4 · p. 13
• For trees without leaves and with uniformly bounded growth, Theorem 4.2 improves the general growth-based upper bound on the non-backtracking spectrum.Source: §4 · p. 14
• For universal covers of finite graphs, the growth rate is the exponential ball-growth limit and equals the Perron–Frobenius eigenvalue of B.Source: §4 · p. 14
• The tree argument bounds operator norms by counting non-backtracking paths according to how they descend toward and ascend away from a chosen root.Source: §4 · p. 14
• The resulting path-counting estimates yield the claimed spectral bound for the tree non-backtracking operator.Source: §4 · pp. 14–15

• The Green function is symmetric for the symmetric operator considered here.Source: §5 · p. 15
• The Green function is invariant under tree automorphisms that commute with the pulled-back operator.Source: §5 · p. 15
• Relative kernels consist of functions supported on a directed-edge subtree whose operator image vanishes away from the root.Source: §5 · p. 15
• The relative kernel is one- or two-dimensional, with dimension two possible only when G(u,u)=0 and G(u,v)≠0.The authors do not know an operator realizing the two-dimensional case.Source: §5 · pp. 15–16
• When the relative kernel is one-dimensional, Green-function restrictions to the corresponding subtree are proportional.Source: §5 · p. 16

• Invertibility is equivalent to the existence of a finite ratio system with α(r)<1 and nonzero, finite edge ratios.Source: §6 · p. 17
• A finite ratio system propagates Green-function values along lifted non-backtracking paths through products of edge ratios.Source: §6 · p. 17
• The condition α(r)<1 makes the ratio-generated functions square-summable and supports construction of the Green function and inverse.Source: §6 · pp. 18–19
• If α(r)=1, polynomially growing approximate-kernel functions force the operator to lack a bounded inverse.Source: §6 · p. 21
• For the non-backtracking operator, the ratio choice r_e=λ^-1 gives α(r)=λ^-2gr, proving invertibility for |λ|>√gr and singularity at |λ|=√gr.Source: §6 · p. 21

• Vanishing Green-function diagonal entries require ratio systems whose values may be zero or infinity.Source: §7 · pp. 21–22
• Condition (c) prevents incompatible infinite ratios, including two edges leaving one vertex with infinite ratios.Source: §7 · p. 21
• Products containing zero and infinity require an inductive convention, with the adjacent zero–infinity case assigned a value determined by operator weights.Source: §7 · pp. 21–22
• Generalized ratios are defined from Green-function quotients and remain well-defined through proportionality of Green-function restrictions.Source: §7 · p. 22
• The generalized ratio system satisfies α(r)<1 and therefore yields the same invertibility criterion as finite systems.Source: §7 · pp. 22, 24
• The ratio-generated Green-function construction is modified by dividing out infinite branches and shifting splitting points to neighboring vertices.Source: §7 · pp. 23, 25

8. Examples

• The examples motivate generalized ratios because invertible operators can have vanishing diagonal Green-function entries.Source: §8 · p. 25, §8.1 · p. 25

8.1. Example 1: Fig`a-Talamanca and Steger.

• For weighted K4, the ratio system r1=∞ and r2=r3=0 has α(r)<1 when (p2/p1)^2+(p3/p1)^2<1.Source: §8.1 · p. 25
• In the weighted K4 example, the adjacency operator is invertible with G(u,u)=0 in the stated strict-inequality regime.Source: §8.1 · p. 25

8.2. Example 2: (2, 3)-bipartite graphs.

• For (2,3)-bipartite graphs, omitting condition (c) produces α<1 despite non-invertibility, so that condition cannot be removed.Source: §8.2 · p. 26

8.3. Example 3: Case study of P1,2,2.

• For P1,2,2, symmetry reduces the calculation to three ratios x, y, and z and the condition x^2z^2(1+2y^2)<1.Source: §8.3 · p. 26
• A plot identifies the λ-region where none of the ratio-system solutions has α(r)<1 for the P1,2,2 case.Source: §8.3 · p. 26

Generalizations

• The framework extends to universal covers of graphs and pregraphs with self-loops, multiple edges, boundaries, vertex and edge weights, and edge lengths.These structures admit finite tree quotients, reducing the generalization to that setting.Source: §9 · pp. 26–27

Tree quotients

• A tree quotient is a tree with a group action, and a finite quotient has finitely many vertex and edge orbits.Ratio systems on the quotient are invariant under the group action and can be viewed on quotient edges.Source: §9 · p. 27

Ratio systems

• For symmetric local operators, Green functions produce generalized periodic ratios on the tree quotient, from which the Green function can be reconstructed.This motivates classifying conditions defined directly on ratio systems.Source: §9 · p. 27

Classification

• For universal covers of finite graphs, α(r) < 1 is a classifying condition for the tree quotient.The condition is explicitly tied to invertibility through the ratio-system characterization.Source: §9 · pp. 27–28
• The generalized periodic-ratio condition is classifying when it characterizes Green-function ratios, excludes zeros of the relevant diagonal terms, and yields a bounded kernel.For cofinite actions, the operator R is finite with nonnegative entries, and Green-function ratios satisfy α(r) < 1.Source: §9 · p. 28

Limitation

• The classification remains unresolved when the acting group is not cofinite on the tree.The paper explicitly states that no classifying condition is known in that setting.Source: §9 · p. 28

Examples

• The paper gives explicit quotient examples for half-loops, a degree-two/degree-three pregraph, and a graph with parallel edges and a half-loop.In the half-loop case, invertibility is characterized by the displayed inequality involving p2 through pr.Source: §9 · p. 28

Scope and open cases

• The characterization is established for invertible symmetric local operators on finite tree quotients, while the nonfinite or nonsymmetric cases remain open.The paper specifically asks what happens when the tree quotient is not finite or the operator is not symmetric with respect to an ℓ2 measure.Source: §10 · p. 29

Random lifts

• The authors conjecture a limiting spectral measure for non-backtracking spectra of random lifts, supported on the universal-cover spectrum.The conjecture allows possible corrections near ±1 and convergence in a suitable topology.Source: §10 · p. 29

Approximate eigenfunctions

• The proof of Theorem 1.6 constructs approximate eigenfunctions only when a ratio system has α = 1, leaving general spectral parameters as an open question.The authors ask whether approximate eigenfunctions can be found for every λ in the spectrum.Source: §10 · p. 29

Spectral boundary

• The paper conjectures that boundary points of the spectrum have ratio systems with α(r) = 1, but raises unresolved questions about limits of ratio systems and infinite coordinates.The conjecture concerns λ on the spectral boundary and does not establish the claimed limiting behavior.Source: §10 · p. 29