Let $A$ be the adjacency operator of a symmetric graph $\Gamma$. (It may be weighted and/or non-regular, but, to keep it simple, let us say it is unweighted and regular of degree $d$.) We want to bound the (non-trivial) eigenvalues of $A$. It is then natural to try to bound $\textrm{Tr} A^{2 k}$ -- which equals the number of closed paths of length $2 k$.

Counting that can be a pain because of backtracking. There is also the option of considering the non-backtracking operator $H$ (Hashimoto matrix); the trace of $H^\ell$ is precisely the number of non-backtracking closed paths of length $\ell$. Counting them is not generally much easier than counting closed paths in general, but it can be cleaner -- and sometimes their number seems to be quite small (whereas the number of closed paths cannot be *that* small - all walks of length $2 k$ induced by trivial words on $d$ letters of length $2 k$ are closed).

What one can then do is the following. The number of closed paths of length $2 k$ -- which equals $\textrm{Tr} A^{2 k}$ -- can also be expressed as $\textrm{Tr} (H+R)^{2 k}$, where $R$ is the edge-reversal operator, i.e., the operator sending an edge $(v_1,v_2)$ to $(v_2,v_1)$. We can now expand the binomial $(H+R)^{2 k}$, and use rules such as $R H R = H^*$ (where $H^*$ is the adjoint of $H$) and $H^* H = R H (d-2)+ I$ to simplify. We end up having a linear combination of terms of the form $\textrm{Tr} H^{\ell}$, $\textrm{Tr} R H^{\ell}$, essentially. Thus we have reduced the problem of bounding $\textrm{Tr} A^{2 k}$ to that of bounding $\textrm{Tr} H^{\ell}$.

(I suppose this strategy must be extremely well-known. It's more of a mess when the graph is not regular.)

Now, here is the question. What happens if you have a very good bound on $\textrm{Tr} H^\ell$ -- say, a bound so small that it is overwhelmed by the contribution of walks coming from trivial words? What sort of extra mileage (on the spectrum of $A$?) can one hope to get from such a bound?

usethe Ihara-Bass formula. In particular, can you use it to bound the eigenvalues of A, either as above or in some other way? My understanding is that Ihara-Bass doesn't really give a direct relation between the spectrum of A and the spectrum of H (see mathoverflow.net/questions/219752/…) - and at any rate the spectrum of H may be the wrong thing to reduce to, as it can be hard to find (H is not normal). Bounding Tr H^{2 k} is easier. $\endgroup$wholespectrum through use of Ihara-Bass (ie they prove convergence of spectrum in Hausdorff distance). They comment that using nonbacktracking walk operators is indispensable. $\endgroup$