8
$\begingroup$

Ramanujan graphs are defined as $(q+1)$-regular graphs for which all nontrivial eigenvalues of the adjacency operator are contained in the interval $$[-2\sqrt{q}, 2\sqrt{q}].$$ The reason for this definition is that this interval is precisely the spectrum of the adjacency operator on the universal cover of these regular graphs, i.e. the infinite $(q+1)$-regular tree. There are quick ways to see heuristically why the spectral radius should be $2\sqrt{q}$: it follows from the number of closed walks of lenght $2n$ in the tree being approximately $(4q)^n$ (see this answer).

We can extend the notion of Ramanujan graphs to $(q_1+1, q_2+1)$-biregular graphs (i.e. bipartite graphs such that every vertex in the first side of the bipartition has degree $q_1+1$ and every vertex in the second side has degree $q_2+1$). Following Zeta Functions of Finite Graphs and Representations of $p$-Adic Groups by Hashimoto, we can define biregular Ramanujan graphs to be those for which all nontrivial eigenvalues of the adjacency operator lie in $$\left[-\sqrt{q_1}-\sqrt{q_2}, -\left|\sqrt{q_1}-\sqrt{q_2}\right|\right]\cup \left[\left|\sqrt{q_1}-\sqrt{q_2}\right|,\sqrt{q_1}+\sqrt{q_2}\right].$$ This can be explained by this union of intervals (together with $\{0\}$) being exactly the spectrum of the adjacency operator on the universal cover, the $(q_1+1, q_2+1)$-biregular tree. I understand how one can prove that this is indeed the spectrum (and even calculate the spectral measure) by finding the walk generating function and using inversion formulas to find the measure with that particular moment generating function (this is done for example in this paper by Godsil and Mohar). However, the bounds for the spectrum just seem to pop out of nowhere at the end of the calculation, so I am looking for a more conceptual explanation. The spectral radius $\sqrt{q_1}+\sqrt{q_2}$ can be explained by approximating the number of closed walks as in the regular case, but I don't see heuristically why the spectrum isn't just an interval centered at the origin but instead has a gap in the middle. Hence my question:

What is a conceptual explanation for this "gap" in the middle of the spectrum if the biregular tree, which doesn't appear in the regular case?

Improve this question
$\endgroup$
5
  • $\begingroup$ If $q_2=1$ you can interpret it as the edge-subdivision of the regular tree. One can relate the eigenvectors and eigenvalues of the regular tree and its subdivision in a direct manner, recovering the formula, which doesn't pass through walk counting (except on the regular tree where it's maybe more intuitive). $\endgroup$
    – Will Sawin
    Commented Jun 28, 2022 at 16:57
  • $\begingroup$ If $q_2=1$ you can interpret it as the edge-subdivision of the regular tree. One can relate the eigenvectors and eigenvalues of the regular tree and its subdivision in a direct manner, recovering the formula, which doesn't pass through walk counting (except on the regular tree where it's maybe more intuitive). $\endgroup$
    – Will Sawin
    Commented Jun 28, 2022 at 17:00
  • $\begingroup$ A somewhat conceptual reason is to look at Hashimoto'a non-backtracking operator on directed edges or its square to make it slightly more symmetric. This is a non symmetric operator summing $q_1q_2$ elements, and there is a "simple" reason that its spectrum on the tree is bounded in absolute value by $\sqrt{q_1q_2}$ (and is actually all $|\lambda|=\sqrt{q_1q_2}$). Then you translate to usual adjacency operator (as in the zeta function of a finite biregular graph) and get the result. $\endgroup$
    – Amitay
    Commented Jun 29, 2022 at 9:37
  • $\begingroup$ @Amitay Do you have a reference for this operator? $\endgroup$
    – Antoine Labelle
    Commented Jun 29, 2022 at 15:02
  • $\begingroup$ You can look at Hashimoto's paper "Zeta functions of finite graphs and Representations of p-adic groups" for the action of the operator on finite graphs, but there are also many other references. The conceptual reason this operator has square root cancellation is that it is "collision-free" on the tree (its powers are simple and sum different edges), unlike the usual adjacency operator whose powers are more complicated, but the actual proof requires some more. I can't point to a specific reference, but see arxiv.org/abs/1702.05452 or arxiv.org/abs/1609.04433, section 3.5. $\endgroup$
    – Amitay
    Commented Jun 30, 2022 at 7:01

0

Reset to default

You must log in to answer this question.