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:
- 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.
- A Ramanujan graph $G$ obeys the Riemann Hypothesis.
-
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…
Best Answer
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.