"Increasing Spanning Forests"

Let T be a tree (a combinatorial graph which is connected and acyclic) whose vertices 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 verticex set {1,…,n}, we consider the generating function for all increasing spanning forests of G and show that this polynomial always factors with 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.