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.
