검색 상세

Acyclic orientation polynomials and the sink theorem for chromatic symmetric functions

초록/요약 도움말

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. (C) 2021 Elsevier Inc. All rights reserved.

more