05C50 Online Seminar: Harry Richman

The distance matrix of a graph records the length of the shortest path between any two vertices. Graham and Pollak found that when the underlying graph is a tree, the determinant of the distance matrix satisfies a nice, simple formula. In particular, the determinant only depends on the number of vertices.

In some applications, such as phylogenetics, we have an underlying tree but our information is limited such that we only know the distance between "terminal" vertices. In this situation, the determinant of the restricted distance matrix is not quite so simple. However, we show that the Graham-Pollak theorem result can be generalized to this setting, where the formula involves counts of various rooted spanning forests. I will explain this formula with examples and give some ideas behind its proof, which involves potential theory. 

This is joint work with Farbod Shokrieh and Chenxi Wu.