Séminaire Lotharingien de Combinatoire, 84B.54 (2020), 12 pp.

Byung-Hak Hwang, Woo-Seok Jung, Kang-Ju Lee, Jaeseong Oh and Sang-Hoon Yu

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 result, we develop "acyclic orientation" analogues for theorems concerning the chromatic polynomial by Birkhoff, Whitney, and Greene-Zaslavsky. As the main application, we provide a new proof for Stanley's sink theorem for chromatic symmetric functions X_G, which 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.

Received: November 20, 2019. Accepted: February 20, 2020. Final version: April 30, 2020.

The following versions are available:

PDF (176 K)
TeX version