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?

  • $\begingroup$ I'm not exactly sure the question, but one can often get a lot of mileage out of the Ihara--Bass formula, which gives a way to map back and forth between the eigenvalues of $A$ and the eigenvalues of $H$. (Several proofs are here -- conservancy.umn.edu/bitstream/handle/11299/3043/1/1459.pdf -- though there are even shorter ones. It is also generalized to graphs with edge weights, even matrix-value edge weights.) This paper gives a good example usage -- arxiv.org/abs/1502.04482. But it's kind of like what you've written in your question. Were you looking for more than this? $\endgroup$ Aug 31, 2022 at 19:36
  • $\begingroup$ Right - I've glanced at Bordenave's paper, but I guess I am not familiar with how to use the 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$ Aug 31, 2022 at 22:12
  • $\begingroup$ I think that this article may be useful arxiv.org/abs/2006.13605. Notice that the technique only applies to regular graphs, although one can generalize without much problems to biregular graphs. For general graphs see arxiv.org/abs/1801.00876, but this is more complicated. $\endgroup$
    – Amitay
    Sep 1, 2022 at 6:52
  • $\begingroup$ In this one arxiv.org/abs/1801.00876 Bordenave and Collins are interested in the spectra of adjacency matrices of various random models, and they access the whole spectrum through use of Ihara-Bass (ie they prove convergence of spectrum in Hausdorff distance). They comment that using nonbacktracking walk operators is indispensable. $\endgroup$ Sep 4, 2022 at 13:25


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.