Unimodality of chromatic polynomial

497 Views Asked by At

The chromatic polynomial of a graph $G=(V,E)$ on $n$ vertices is of the form $\sum_{i=1}^n a_ik^i$. The unimodal conjecture (unproven) states that the absolute values of the coefficients are unimodal, i.e. that for some $k$ $|a_1|\leq|a_2|\leq\ldots|a_k|\geq|a_{k+1}|\ldots\geq|a_n|$.

Now this chromatic polynomial can also be written as $\sum_{i=1}^n b_i(k)_i$ where $(k)_i$ is the falling factorial $k(k-1)\ldots(k-i+1)$. In this representation $b_i$ is the number of ways that $V$ can be partitioned into $i$ independent sets (so the $b_i$ are all non-negative).

I am curious to know whether this sequence $b_i$ is unimodal. It seems much more obvious than the unimodality of the $|a_i|$, but until now I have been unable to prove it. Can anybody help?