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.

  • 1
    $\begingroup$ For a start a graph can embed in many different surfaces, so what matrix could we use? If the matrix depends on the surface, there's no real point in computing eigenvalues, $\endgroup$ – Chris Godsil Feb 13 '16 at 23:02
  • 1
    $\begingroup$ The spectrum of the Laplacian controls the behavior of the heat equation on a graph, so loosely the eigenvalues tell you something about how quickly heat dissipates on the graph, which has something to do with how connected the graph is. More precisely, look up the Cheeger inequalities. $\endgroup$ – Qiaochu Yuan Feb 13 '16 at 23:57

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)

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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