Non-log-concave -polynomials of regular graphs
In the authors' words
For any simple graph on vertices, write its chromatic polynomial in the rising factorial basis as , where for any and . Brenti (1992) introduced the -polynomial and its augmented version, defined by He asked whether always has only real roots and whether always has a log-concave coefficient sequence. In this paper, we show that for any integer , there exists an integer such that, for every connected -regular graph of girth at least , the coefficient sequence of fails to be log-concave. This failure also occurs for , and Newton's inequalities imply that has nonreal roots. Thus both questions have counterexamples among regular graphs of arbitrarily large girth.
Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.