Question: Does there exist a satisfying combinatorial interpretation of non-integer eigenvalues of a graph?

A little background. The adjacency matrix associated to a graph has the property that its powers describe the number of walks of certain lengths between vertices of , so to find closed forms for these numbers it is easiest to diagonalize and work with its eigenvalues instead. The question is whether there is generally a way we can deduce these eigenvalues combinatorially without computing them.

This may seem a little backwards, so let me explain. Many nice graphs have integer eigenvalues: for example, the complete graph with self-loops has eigenvalues and it's trivial to see why, since a walk on is just a list of vertices. (It's only slightly harder to figure out why the complete graph without self-loops has eigenvalues .) I've gone on and on about what eigenvalue means. What I'm interested in is whether non-integer eigenvalues can still be given combinatorial meaning.

Let me demonstrate with two problems I've been thinking of.

Problem 1: Find a combinatorial proof of Binet's formula, .

This amounts to finding a combinatorial interpretation of the eigenvalues of the graph with adjacency matrix

.

I have discussed the relationship between the Fibonacci numbers and walks on this graph (i.e. tilings with and dominoes) previously. The factor corresponds to coloring such a tiling or equivalently adding edges to the graph. The question is to explain the factor.

It is likely that the answer to this question is well-known. It may not even be terribly difficult, but I have been working on it for some time without success.

Problem 2: Find a combinatorial proof of the identity .

This amounts to finding a combinatorial interpretation of the eigenvalues of the graph with adjacency matrix

.

We've seen this matrix connected to this problem before. The bijection is as follows: a walk on the above graph has the property that you have two choices at each vertex, either stay or move to the next vertex. Interpret "stay at a vertex during step " as "don't add to a subset" and interpret "move to the next vertex during step " as "add to a subset." Then the number of closed walks from vertex to itself is the number of walks where you have to move a number of times congruent to , i.e. the number of subsets with cardinality divisible by , and similarly for the other two. To explain the eigenvalues here, one needs to either exhibit a counting argument that depends on the value of or explain what will, after simplification, turn out to be a factor. (The former might actually be quite easy; nevertheless, I have not been able to make progress on it.)

The above two examples can be summarized, a little tongue-in-cheek, as follows: is there a combinatorial proof of the quadratic formula? (This would allow us to explain the role of the discriminant.) Perhaps I really mean a categorical proof, but that's taking me too far afield.

The difficulty I have in resolving either of these questions is that I cannot imagine a way in which a solution would naturally generalize. While I think there might be a nice proof in the Fibonacci case, it is difficult to generalize beyond two vertices. As for the other, it is a special property of the third roots of unity that are still (sixth) roots of unity; the generalization that handles what I would call "a combinatorial interpretation of the roots of unity filter," on the other hand, would have to deal with eigenvalues that are not roots of unity (or multiples thereof, such as ) and hence do not correspond (in a straightforward way) to some kind of periodic behavior. Computing the "real forms" of these identities would be even harder; one has to study quadratic subfields of cyclotomic fields and I really cannot imagine a combinatorial theory making these computations.

There is a sense in which what I've been looking for in these last two posts is a "categorified graph theory" something along the lines of what John Baez calls the groupoidification of linear algebra, but equipped to handle the notion of similarity. I definitely need more background to see if this idea makes any sense, though.

More questions:

The spectral theorem tells us that undirected graphs have real eigenvalues. Can this be deduced from purely graph-theoretic concerns, i.e. the number of walks of length as grows is either a sum of components which are either strictly increasing, strictly decreasing, or have period ? In other words, can we prove (a special case of) the spectral theorem graph-theoretically?

Directed acyclic graphs have a natural interpretation as the Hasse diagrams of finite posets. Are two Hasse diagrams for the same poset isospectral? Do two posets with isospectral Hasse diagrams have the same width? Can we prove a weaker version of the nilpotent Jordan normal form theorem via Dilworth's theorem? (Part of this question should be settled quickly by some computations I should get around to doing; it will be very obvious if the answer to either of the first two questions is "no.")

The Fibonacci discussion above generalizes as follows: it appears that any problem asking for the number of words of length on a finite alphabet avoiding certain local patterns such as substrings (i.e. no consecutive s) can be rephrased as a question about walks on a certain graph, but it is also possible to impose global patterns (the number of s is a multiple of ) as in the third-roots-of-unity discussion. Is there a concise description of problems of this sort that reduce to walks on graphs? (At least one type of global pattern - for example, that the number of s be equal to the number of s - is definitely not of this form.)