Eulerian Polynomials for Digraphs

Abstract

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 by work of Kalai, we look at problems related to $-1$ evaluations of $A_D(t)$. In particular, we give a combinatorial interpretation of $|A_D(-1)|$ in terms of "generalized alternating permutations" whenever the underlying graph of $D$ is bipartite.