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