Archive for May, 2009

Funnily enough, a few days after I wrote the previous post, I was linked to a graph theory paper where one of the first results cited, which was clearly well-known to the authors, is the following remarkable generalization of what I tried to do:

Theorem: The only connected simple graphs with spectral radius less than or equal to \ 2 are the induced subgraphs of the Dynkin diagrams \tilde{A}_n, \tilde{D}_n, \tilde{E}_6, \tilde{E}_7, \tilde{E}_8.

I have to admit, I really didn’t suspect that the classification result I was going after was both so simple and so interesting! Certainly there are heuristic reasons why the above classification makes sense: as I forgot to note in the previous post, there really can’t be too many vertices of degree 3 in a graph with \rho(G) \le 2. But I really can’t fathom why spectral radius can be used to define the Dynkin diagrams, considering their relationship to

- simply laced Lie groups,

- binary polyhedral groups and the Platonic solids,

- quiver representations, or

- the octonions (okay, this one is stretching it a little).

Anyone know any good references?

In any case, I’d like to discuss the McKee-Smyth paper because it has some interesting ideas I’d thought about independently.


Read Full Post »


Get every new post delivered to your Inbox.

Join 345 other followers