Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Counting increasing rooted forests
Speaker: Bruce Sagan, Michigan State University
Date: Thursday, February 19, 2015 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
Let T be a tree whose verices are distinct integers. Call T increasing if the vertices on any path starting from its minimum vertex form an increasing sequence. Similarly, call a forest increasing if each of its component trees is increasing. Given a graph G with vertices 1, ..., n we consider the generating function for all increasing spanning forests of G and show that this polynomial always factors with nonnegative integral roots. We also characterize when this polynomial is equal to the chromatic polynomial of G. Finally, we generalize these results to pure simplicial complexes of arbitrary dimension. This is joint work with Joshua Hallam and Jeremey Martin.