Given an n-vertex digraph D and a labeling σ:V(D)→[n], we say that an arc u→v of D is a descent of σ if ›σ(u)›σ(v). Foata and Zeilberger introduced a generating function AD(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 AD(t): we give combinatorial interpretations of |AD(−1)| for a large class of digraphs (such as digraphs whose underlying graph is bipartite), we determine the maximum and minimum possible values of |AD(−1)| obtained by directed trees, and we obtain bounds on the mulitiplicity of −1 as a root of AD(t).
Mathematics Subject Classifications: 05C20, 05A15
Keywords: Eulerian polynomials, alternating permutations, combinatorial reciprocity
Cookie SettingseScholarship uses cookies to ensure you have the best experience on our website. You can manage which cookies you want us to use.Our Privacy Statement includes more details on the cookies we use and how we protect your privacy.