Graph spectra and topology

Question

This is a somewhat vague question, but I'm wondering if there has been any research into connections between the spectrum of a graph and some notion of the "topology" of that graph.

To give an example of what I mean, say we take some two-manifold $M$ and consider a graph $G$ which lives on it. By this I mean, let $G$ consist of a very large number of points on $M$ with edges connecting adjacent points. Let $A$ be the adjacency matrix of $G$. Is there some way to define a matrix $B$ dependent on $A$ such that if $M$ has trivial fundamental group the smallest eigenvalue of $B$ is negative but if $M$ has nontrivial fundamental group the smallest eigenvalue of $B$ is positive?

That was a pretty specific example - I'm really just wondering more generally if there's a way to associate a matrix with a graph such that the spectrum of the matrix "sniffs out" some topological feature of the space the graph is associated with.

Answer 1

To push this in a different direction from the comments, in the past years there have been some developments in spectral graph theory related to covering maps of graphs. Notice that this is the same notion as covering from topology when we regard graphs as topological spaces in the obvious manner.

A covering map of graphs $p:G\to H$ is a graph homomorphism which is locally an isomorphism, so that the neighbors of $v\in V(G)$ get mapped bijectively to the neighbors of $p(v)\in V(H)$. There are natural ways to generalize this to directed multigraphs. It's an easy exercise that every eigenvalue of $H$ will be an eigenvalue of $G$ in this situation, and moreover eigenfunctions of $G$ can be obtained from eigenfunctions of $H$ by precomposing with $p$ (or to be strict the vertex component of $p$).

I'm going to be more vague now - it turns out that coverings of a good expander are usually good expanders. The breakthrough paper of Marcus, Spielman and Srivastava used coverings to finally resolve in the affirmative the existence of Ramanujan graphs of all degrees (nonconstructively); see also this paper by Agarwal, Kolla and Madan which discusses the expansion of small-degree coverings). Check out the references of these papers as well, there is a lot more work going on on eigenvalues of coverings. This is the spectral connection.

The connection to topology and embeddings that I'm aware of concerns the question of embedding graphs on surfaces without edge intersections (so it's a generalization of planarity); to this end the above notion of covering is useful in the book by Gross and Tucker on topological graph theory (I read parts of it to make sense of the connection to spectral stuff)