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?


1 Answer 1


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).


Your Answer

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

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