Acyclic orientation polynomials and the sink theorem for chromatic symmetric functions

Abstract

We define the acyclic orientation polynomial of a graph to be the generating function for the sinks of its acyclic orientations. Stanley proved that the number of acyclic orientations is equal to the chromatic polynomial evaluated at $-1$ up to sign. Motivated by this link between acyclic orientations and the chromatic polynomial, we develop "acyclic orientation" analogues of theorems concerning the chromatic polynomial of Birkhoff, Whitney, and Greene-Zaslavsky. As an application, we provide a new proof for Stanley's sink theorem for chromatic symmetric functions $X_G$. This theorem gives a relation between the number of acyclic orientations with a fixed number of sinks and the coefficients in the expansion of $X_G$ with respect to elementary symmetric functions.

21 pages, 4 figures