Skip to content
Preprint

Non-log-concave $\tau$-polynomials of regular graphs

Nov 2026 · 0 citations · 18 references
Mathematics

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.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.