Combinatorial Theory

Given an $n$-vertex digraph $D$ and a labeling $\sigma :V(D)\to [n]$, we say that an arc $u\to v$ of $D$ is a descent of $\sigma$ if $\sigma (u)›\sigma (v)$. Foata and Zeilberger introduced a generating function $A_D(t)$ for labelings of $D$ weighted by descents, which simultaneously generalizes both Eulerian polynomials and Mahonian polynomials. Motivated in part by work of Kalai, we prove three results related to $-1$ evaluations of $A_D(t)$: we give combinatorial interpretations of $|A_D(-1)|$ for a large class of digraphs (such as digraphs whose underlying graph is bipartite), we determine the maximum and minimum possible values of $|A_D(-1)|$ obtained by directed trees, and we obtain bounds on the mulitiplicity of $-1$ as a root of $A_D(t)$.

Mathematics Subject Classifications: 05C20, 05A15

Keywords: Eulerian polynomials, alternating permutations, combinatorial reciprocity