# Local-Global Principle in Graph Spectrum

The question is a bit vague, but any ideas/directions will be appreciated.

Let us fix an $n$-vertex $d$-regular graph $G=(V,E)$. As I understand it, the eigenvalues of the adjacency matrix $A$ of $G$ capture "global" information about the graph, akin to a fourier transform. For instance, the number of cycles in $G$ of length $k$ is $Tr(A^k)$ which is the $k$-th power sum of the eigenvalues.

But even this uses all the eigenvalues. In particular, take some eigenvalue $\lambda$ and its eigenvector $\vec{f}$. Does $\lambda^k$ alone have any natural correspondence with some measure on the cycles of length $k$?

Secondly, since the spectrum captures global properties of the graph, like expansion, it seems as if slightly changing the graph locally can change the spectrum and eigenvectors significantly in a global way. This can be checked empirically, though I am unclear on how to formalize this.

Does the reverse hold in any meaningful way? That is, suppose I change the graph "globally", for instance, I change every vertex/edge the same way. Would that change the spectrum and eigenvalues "locally"?

The example that illustrates my vague question is the result of Lubetzky-Peres, which says that going from the adjacency matrix $A$ to the Hashimoto matrix (of the line-digraph of $G$) changes the eigenvalues and eigenvectors locally. Each eigenvalue $\lambda$ of $A$ splits into two eigenvalues $\mu,\overline{\mu}$ which are roots of $$x^2-\lambda x+ (d-1)=0$$ and the eigenvector corresponding to $\mu$ at a "vertex" $(v,w)$ is $\mu f(w)-f(v)$. So modifying the graph "globally" as in the case of the line-digraph construction (where we add two vertices for each direction of each edge of $G$) changes the eigenvalues and eigenvectors only locally.

Is there an underlying principle here that governs the degree of locality/globality of the spectrum and eigenvectors? What are the precise class of operations on a graph that change the spectrum locally?

The procedure of going from the a graph (adjacency matrix), $X$, to the directed graph of directed of directed edges (Hashimoto operator), call it $H(X)$, is not exactly what I would call a "global change" but rather a "functorial change". Indeed, $X\mapsto H(X)$ can be extended to a functor from the category of graphs with covering maps as morphisms, call it $\mathcal{G}$, to the category of directed graphs.

Such functorial constructions are abundant. For example, let $P_k(X)$ denote the graph with the same set of vertices as $X$ and with one edge from $x$ to $y$ for every non-backtracking path $x\to y$ of length $k$. Then $X\mapsto P_k(X)$ is functorial in the sense that $P_k$ extends naturally to a functor $\mathcal{G}\to \mathcal{G}$.

For some functorial constructions $X\mapsto F(X)$ there are indeed connections between the spectrum of $X$ and that of $F(X)$, e.g. $H$ and $P_k$. I do not know of a general procedure to predict or compute them. However, such connections often have representation-theoretic interpretations, which is not to say that they cannot be proved in elementary means.

Elaborating on the representation theoretic point of view, let $T$ denote the $k$-regular tree, let $G$ denote its automorphism group (with its point-wise convergence topology), let $K$ be the stablizer of some vertex $t_0\in T$, and let $I$ denote the stablizer of some directed edge $(t_0,t_1)$ in $T$. Any $k$-regular graph $X$ is obtained as $T/\Gamma$ for a lattice $\Gamma$ in $G$, specifically, $\Gamma=\pi_1(X)$. One easily checks that the the vertices of $X$ are in correspondence with $\Gamma{\setminus} G/K$ and that the directed edges are in correpodence with $\Gamma{\setminus}G/I$.

With these observations, one can read the spectrum of the adjacency matrix of $X$ from the irreducible $G$-subrepresentations of $\mathrm{L}^2(\Gamma{\setminus} G)$. Specifically, it is the spectrum of an operator in the relative Hecke algebra $A\in H(G,K)$ restricted to $\mathrm{L}^2(\Gamma{\setminus} G)^K=\mathrm{L}^2(\Gamma{\setminus}G/K)\cong \mathrm{L}^2(X)$ --- in fact, $A$ becomes the adjacency operator of $X$ under this isomorphism. Similarly, the Hashimoto operator of $X$ can be realized as an element $h\in H(G,I)$ acting on $\mathrm{L}^2(\Gamma{\setminus} G)^I=\mathrm{L}^2(\Gamma{\setminus}G/I)$.

The relations between between the spectra of $A$ and $h$ can now be deduced as a consequence of algebraic relations between $A$ and $h$ inside $H(G,I)$, e.g. as done (implicitly) in the proof of Kotani and Sunada (http://www.ms.u-tokyo.ac.jp/journal/pdf/jms070102.pdf). Alternatively, one could compute explicitly the contribution of each irreducible unitary $G$-representation $V$ to the spectrum of $A$ and of $h$ and get the same conclusion.

The strategies sketched here for $H(X)$ can be applied (sometimes after considerable work!) to other functorial constructions $X\mapsto F(X)$, and also when $X$ is a simplicial complex, rather than just a graph. A notable example is in "Zeta functions of complexes from PGL(3): A representation theoretic approach" by Kang, Li and Wang (2010). I also have a preprint which attempts to give a (perhaps too) general view on this kind of approach https://arxiv.org/abs/1605.02664 (section 4 and 6).