Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Matthew Russell, Rutgers University, russell2 {at} math [dot] rutgers [dot] edu)
Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

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.

See: http://www.math.rutgers.edu/~russell2/expmath/