Non-log-concave $\tau$-polynomials of regular graphs
Abstract
For any simple graph $G$ on $n$ vertices, write its chromatic polynomial in the rising factorial basis as $P(G,x)=\sum_{j=0}^{n}(-1)^{n-j}c_j x^{\langle j\rangle}$, where $x^{\langle j\rangle}=\prod_{i=0}^{j-1}(x+i)$ for any $j\ge 1$ and $x^{\langle0\rangle}=1$. Brenti (1992) introduced the $\tau$-polynomial and its augmented version, defined by $$\tau(G,x)=\sum_{j=0}^{n}c_jx^j, \qquad \overline{\tau}(G,x)=\sum_{j=0}^{n}j!c_jx^j.$$ He asked whether $\tau(G,x)$ always has only real roots and whether $\overline{\tau}(G,x)$ always has a log-concave coefficient sequence. In this paper, we show that for any integer $d\ge 4$, there exists an integer $h_d$ such that, for every connected $d$-regular graph $G$ of girth at least $h_d$, the coefficient sequence of $\tau(G,x)$ fails to be log-concave. This failure also occurs for $\overline{\tau}(G,x)$, and Newton's inequalities imply that $\tau(G,x)$ has nonreal roots. Thus both questions have counterexamples among regular graphs of arbitrarily large girth.