"Simplicial, cubical and cellular spanning trees"

Jeremy Martin
University of Kansas

Monday, April 13, 2009
4:00 pm, 845 Patterson Office Tower

Abstract:

The classical Matrix-Tree Theorem enumerates the number of spanning trees in a graph; that is, the number of connected, acyclic subgraphs with one fewer edge than it has vertices. Both the definition of spanning tree, and the Matrix-Tree Theorem, can be generalized by replacing the graph with a simplicial complex or even a CW-complex. For many kinds of complexes (for example, shifted simplicial complexes and skeletons of cubes), there are explicit combinatorial formulas for the number of spanning trees, as well as generating functions that enumerate spanning trees by some statistic such as vertex degree sequences. This is joint work with Art Duval and Carly Klivans.