Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Simplicial spanning trees

Algebra & Discrete Mathematics

Speaker: Art Duval, U. Texas - El Paso
Location: 2112 MSB
Start time: Fri, May 23 2008, 1:10PM

Cayley's famous result that there are n^{n-2} spanning trees in a complete graph of n vertices has been proved, and generalized, in many ways. One particularly nice way is the Matrix- Tree Theorem, that the number of spanning trees of an arbitrary graph can be enumerated by the determinant of a reduced Laplacian matrix. Building upon the work of Kalai and Adin, we extend the concept of a spanning tree from graphs to simplicial complexes, which are just higher-dimensional analogs of graphs. For all complexes K satisfying a mild technical condition, we show that the simplicial spanning trees of K can be enumerated using its Laplacian matrices, generalizing the Matrix-Tree theorem. As in the graphic case, replacing the Laplacian with a weighted analogue yields extra information about the simplicial spanning trees being counted. As an example, we find a nice expression for the resulting weighted tree enumerator of shifted complexes, by generalizing a formula for the Laplacian eigenvalues of a shifted complex to the weighted case.

If time permits, I'll also talk about extending this work to cubical complexes and other CW-complexes.

This is joint work with Carly Klivans and Jeremy Martin.