Room 326

Chromatic polynomials and heaps of pieces

Bishal Deb

CMI

Stanley in 1973 proved that the number of acyclic orientations of
an undirected graph is the value of its chromatic polynomial at (-1) upto
sign. In this paper, he also defined a generalised version of the chromatic
polynomial and related it to the chromatic polynomial. In 1983 Greene and
Zaslavsky showed that the number of acyclic orientations of an undirected
graph with a unique sink at a fixed vertex is same as the coefficient of the
linear term of the chromatic polynomial of the graph upto sign. In this talk
we look at an involution on layer factorisations of heaps which we shall
 use to prove the theorems of Stanley. We will also see how modifications to
this involution can be used to prove the result of Greene and Zaslavsky.