Algebraic Combinatorics Seminar - Krystal Guo

Title: Inverses of Trees

Abstract:

A tree is invertible if and only if it has a perfect matching.

Godsil considers an invertible tree T and finds that the inverse of the adjacency matrix has entries in {0, ±1} and is the signed adjacency matrix of a graph which contains T. In this talk, we give a new proof of this theorem, which gives rise to a partial ordering relation on the class of all invertible trees on 2n vertices. Though properties of graphs are related to their eigenvalues, this relationship is not, in general, a quid pro quod relationship. In this case however, we are able to define an operation which changes an invertible tree T to a non- isomorphic invertible tree T' whose median eigenvalue is strictly greater. This extends naturally to a partial ordering of the class of invertible trees. We characterize the maximal and minimal elements of this poset and discuss some applications.