33
$\begingroup$

It all started with Chris' answer saying returning paths on cubic graphs without backtracking can be expressed by the following recursion relation:

$$p_{r+1}(a) = ap_r(a)-2p_{r-1}(a)$$

$a$ is an eigenvalue of the adjacency matrix $A$. Chris mentions Chebyshev polynomials there. It was Will who found the generating function for the given recursion to be:

$$G(x,a)=\frac{1-x^2}{1-ax+2x^2} $$

and just recently Hamed put Chebyshev back on the table:

$$ \frac{1-x^2}{1-ax +2x^2} \xrightarrow{x=t/\sqrt{2}}\frac{1-\frac{t^2}2}{1-2\frac{a}{\sqrt 8} t+t^2}=\left[1-\frac{t^2}{2}\right]\sum_{r=0}^\infty U_r\left(\frac{a}{\sqrt{8}}\right)t^r\\ =\sum_{r=0}^\infty \left(U_r\left(\frac{a}{\sqrt{8}}\right)-\frac12 U_{r-2}\left(\frac{a}{\sqrt{8}}\right)\right)t^r\\ $$ $$ \Rightarrow p_r(a)=\begin{cases}1 & \text{if $r=0$,}\\ 2^{r/2}\left(U_r(a/\sqrt{8})-\frac12U_{r-2}(a/\sqrt{8})\right) & \text{if $r\ge1$.}\end{cases} $$ The final line as taken from Will's community answer...

My question how to relate Ihara's $\zeta$ function and Chebyshev seems therefore mostly settled, but...:

Is it just a funny coincidence that the scaling factor of $\sqrt 8$ coincides with $\lambda_1\leq 2\sqrt 2$, which is the definition of cubic Ramanujan graphs.

And, there is another interesting thing:

As observed by Sunada, a regular graph is a Ramanujan graph if and only if its Ihara zeta function satisfies an analogue of the Riemann hypothesis.

What does this connection between Chebyshev, Ramanujan, Ihara and Riemann mean?

EDIT

I thought maybe something like a corollary could be possible:

  1. For Ramanujan graphs, the Ihara $\zeta$ function can be related to Chebyshev functions of the second kind, since the scaled eigenvalues of $A$ lie inside the range of convergence.
  2. A Ramanujan graph $G$ obeys the Riemann Hypothesis.
  3. Roots of the Ihara $\zeta$ function lie on the critical strip.

    • The bunch of people above have contributed to $1\leftarrow 2$.
    • $2 \leftrightarrow 3$ is proven here: Eigenvalues are of the form $\lambda=2\sqrt 2\cos(b\log 2)$
    • $3\overset{\rightarrow ?}{\leftarrow} 1$ would be nice...
$\endgroup$
5
  • $\begingroup$ I recommend to up-vote the linked answers. Thanks to all that helped so far... $\endgroup$
    – draks ...
    Nov 25, 2015 at 21:29
  • 4
    $\begingroup$ Check out p. 18 of Murty's survey: mast.queensu.ca/~murty/ramanujan.pdf. Also, there's a book by Davidoff, Sarnak, and Valette is very readable. In this context, the Riemann hypothesis is equivalent to 2nd largest eigenvalue being the square root of the degree (square root corresponds to zeros on the line Re(s)=1/2; non-trivial bound on the size of the 2nd largest eigenvalue corresponds to zeros having Re(s) < 1, which I believe implies the analog of the "prime number theorem" in this context.) $\endgroup$ Dec 24, 2015 at 20:30
  • $\begingroup$ @BrendanMurphy great paper, but I don't see how it helps here. Maybe I missed something? $\endgroup$
    – draks ...
    Jan 1, 2016 at 22:12
  • 3
    $\begingroup$ Look at Davidoff, Sarnak, and Valette's book---the results you describe are in the first chapter. In particular, it's not a coincidence that the scaling factor is $\sqrt{8}$. I mentioned Murty's survey because it explains in more detail what the "Riemann Hypothesis" means in this context, and more generally the analogy between cycles and numbers. I'm not sure how to answer the question "what does this connection mean", since I think the connection provides different interpretations, just like Cartesian coordinates provide different interpretations for curves and equations. $\endgroup$ Jan 2, 2016 at 23:22
  • 2
    $\begingroup$ To me, the mysterious part is that the Chebyshev polynomials and the matrices that count loops without backtracking satisfy a similar recurrence. Is this an accident? The last exercise in section 1.4 of DSV mentions a connection to representation theory; I think this is expanded upon in a book by Katz and Sarnak called "Random Matrices, Frobenious Eigenvalues, and Monodromy", although I've only skimmed this book and I'm not sure if the graph theory side is mentioned there. Anyway, perhaps more can be said, but I don't know any more :) $\endgroup$ Jan 3, 2016 at 18:12

1 Answer 1

4
$\begingroup$

Let $G$ be a $d$-regular connected graph on $n$ vertices. Let $$d=\lambda_0 \geq \lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_{n-1}$$ be the $n$ eigenvalues of the adjacency matrix $A$, and let $\lambda = max( |\lambda_1|,|\lambda_{n-1}|)$. Intuitively, the significance of the spectrum of $A$ is that many combinatorial quantities can be expressed linear-algebraically, and optimizations problems in this framework often involve the spectrum.

For instance, we saw that for two vertex subsets $S,T \subseteq V$, the cardinality of $E(S,T)$ is $$E(S,T)=\textbf{1}_{T}^{*} A \textbf{1}_S$$ and this in turn could be expressed as a sum over eigenvalues of $A$.\ In these cases, the summand corresponding to the eigenvalue $d$ turns out to be the "average" value that we would expect of the quantity, while the summands corresponding to the remaining eigenvalues would then be interpreted as the "error" term. In the case of $E(S,T)$, the summand corresponding to $d$ is $$d \frac{|S|}{\sqrt{n}} \frac{|T|}{\sqrt{n}} = \frac{d}{n} |S|.|T|$$ and this is the value we expect for a $d$-regular random graph on $n$ vertices. The remaining eigenvalues and their eigenvectors, through their interaction with $S$ and $T$ determine the deviation of $|E(S,T)|$ from this average value. So when the remaining eigenvalues are small in absolute value, this gives us a bound on the error term and allows us to conclude that for all sets $S,T \subseteq V$, $|E(S,T)|$ is close to the average value.\

This idea can be used in other enumeration problems too. All graph properties, by definition, depend on the adjacency matrix, and so can be expressed in terms of $A$. The challenge is then to ensure that the expression is amenable to linear-algebraic tools.\

Another simple example is that of a random walk on the graph. Suppose we are interested in the number of walks on $G$ of length $k$ that are cycles. Clearly this is $$Tr(A^k)$$ which is $$d^k + \lambda_1^k + \lambda_2^k + \dots + \lambda_{n-1}^k$$ Observe that the total number of walks of length $k$ on $G$ is $$n.d^k$$ In a random graph, we would expect a random walk to end up at its starting point with probability $1/n$. And so the "average" number of closed walks of length $k$ on a random $d$-regular graph is $$\frac{n.d^k}{n}=d^k$$ and this is again exactly the summand corresponding to the eigenvalue $d$ in the linear algebraic formulation of the expression for the fixed graph $G$. Furthermore the number of closed walks of length $k$ on $G$ is $$d^k \pm (n-1)\lambda^k$$ and $(n-1)\lambda^k$ is an upper bound on the error term.\

A more non-trivial example of this is in the case of non-backtracking closed walks of length $k$ on $G$. In this case we are interested in $$Tr(A_k)$$ Since $$A_k = (d-1)^{k/2} U_k \left( \frac{A}{2 \sqrt{d-1}} \right) - (d-1)^{k/2-1} U_{k-2} \left( \frac{A}{2 \sqrt{d-1}} \right)$$ we have $$Tr(A_k) = (d-1)^{k/2} \sum \limits_{j=0}^{n-1} U_k \left( \frac{\lambda_i}{2 \sqrt{d-1}} \right) - (d-1)^{k/2-1} \sum \limits_{i=0}^{n-1} U_{k-2} \left( \frac{\lambda_i}{2 \sqrt{d-1}} \right) $$ Since the total number of non-backtracking walks of length $k$ is $$n d(d-1)^{k-1}$$ we would expect a $1/n$ fraction of these to be closed. The summand corresponding to the eigenvalue $d$ is $$(d-1)^{k/2} \sum \limits_{j=0}^{n-1} U_k \left( \frac{d}{2 \sqrt{d-1}} \right) - (d-1)^{k/2-1} \sum \limits_{i=0}^{n-1} U_{k-2} \left( \frac{d}{2 \sqrt{d-1}} \right)$$ Using the closed form expression for $U_k$ given by $$U_k(x) = \frac{(x+\sqrt{x^2-1})^{k+1}- (x-\sqrt{x^2-1})^{k+1} }{2\sqrt{x^2-1}}$$ we get $$(d-1)^{k/2} \sum \limits_{j=0}^{n-1} U_k \left( \frac{d}{2 \sqrt{d-1}} \right) - (d-1)^{k/2-1} \sum \limits_{i=0}^{n-1} U_{k-2} \left( \frac{d}{2 \sqrt{d-1}} \right) = d(d-1)^{k-1}$$ as expected, and the summands corresponding to the remaining eigenvalues form the error term.\ It is here that the Ramanujan property has a natural interpretation!\

Consider the function $U_k(x)$. It is known that for $|x| \leq 1$, $U_k(x)$ has a trigonometric expression given by $$U_k(\cos{\theta}) = \frac{ \sin{(k+1)\theta}}{\sin{\theta}}$$ So whenever $|x|\leq 1$, $$|U_k(x)| \leq k+1$$ As for when $|x| > 1$, the expression $$U_k(x) = \frac{(x+\sqrt{x^2-1})^{k+1}- (x-\sqrt{x^2-1})^{k+1} }{2\sqrt{x^2-1}}$$ implies that $$U_k(x) = O(x^k)$$

So if the graph is Ramanujan, then for every $|\lambda|\neq d$, $$|(d-1)^{k/2}U_k\left( \frac{\lambda}{2 \sqrt{d-1}} \right) | \leq (k+1)(d-1)^{k/2} = O(k d^{k/2})$$ This means that the number of non-backtracking closed walks of length $k$ on $G$ is $$d(d-1)^{k-1} \pm O(nk d^{k/2})$$ On the other hand if the graph is not Ramanujan, then the error term could be significantly larger, and the most we can say is that the number of non-backtracking closed walks of length $k$ on $G$ is $$d(d-1)^{k-1} \pm O(n d^k)$$ which is not very useful since the error term is of the same order as the average!\ In fact this is the approach used in the original construction of Ramanujan graphs- where they forces the eigenvalues to be small by ensuring that the number of non-backtracking walks of a every given length is close to the average and the error term is small.\

Next consider the number of tailless non-backtracking cycles of length $k$ on $G$. This is given by the quantity $$N_k=\begin{cases} \sum \limits_{j=0}^{n-1} 2(d-1)^{k/2} T_k \left( \frac{\mu_j}{2\sqrt{d-1}} \right) & \text{ if k is odd}\\ \sum \limits_{j=0}^{n-1} 2(d-1)^{k/2} T_k \left( \frac{\mu_j}{2\sqrt{d-1}} \right) + d-2 & \text{ if k is even}\\ \end{cases}$$ https://arxiv.org/abs/1706.00851 The summand corresponding to the eigenvalue $d$ is $$(d-1)^k + 1$$ when $k$ is odd, and $$(d-1)^k + 1 + (d-2)$$ when $k$ is even. It is interesting to ask what this quantity can be interpreted as.\

For simplicity assume $G$ is a Cayley graph, so that the edges incident at each vertex can be represented by a symmetric generating set $S$ of size $d$. A tailless non-backtracking cycle of length $k$ is now a \emph{cyclically reduced word} of length $k$ over the alphabet $S$ that evaluates to $1$ in the group. It is known that the number of cyclically reduced words of length $k$ over a generating set of size $d$ is $$(d-1)^k + d/2 + (d/2-1)(-1)^k$$ https://math.stackexchange.com/questions/825830/reduced-words-of-length-l and so the total number of such special walks on the graph is $$n \left( (d-1)^k + d/2 + (d/2-1)(-1)^k \right)$$ and so the expected number of such walks that are closed is $$(d-1)^k + d/2 + (d/2-1)(-1)^k$$ which is precisely the expression we got earlier for the summand in $N_k$ corresponding to the eigenvalue $d$. \

For Chebyshev polynomials of the first kind, we know that $$T_k(\cos{\theta})=\cos{k \theta}$$ and so for $|x| \leq 1$, $$|T_k(x)| \leq 1$$ This gives us a strong expression for $N_k$ when $G$ is Ramanujan: $$N_k = (d-1)^k + d/2 + (d/2-1)(-1)^k \pm O(n d^{k/2})$$ which is slightly better than the error we got for non-backtracking but possibly tailed cycles.

$\endgroup$
3
  • $\begingroup$ Hey @Bharat How are things? Cheers, draks... $\endgroup$
    – draks ...
    Jan 25, 2018 at 21:29
  • $\begingroup$ @draks... Hello! Been meeting math researchers trying to interest them in the Bilu-Linial conjecture and Marcus-Spielman-Srivastava result. The problem is ambitious, but even special cases would be interesting. Whats up with you? $\endgroup$
    – BharatRam
    Jan 28, 2018 at 20:45
  • $\begingroup$ @draks... Also, is there some direct reinterpretation of LPS construction of Ramanujan graphs in terms of the zeta function of the graph and that of curves over finite fields? That connection is hinted in some places, but never explicitly clarified. Tell me if you know anything on these lines. $\endgroup$
    – BharatRam
    Jan 28, 2018 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.