A Proof of the Peak Polynomial Positivity Conjecture

Alexander Diaz-Lopez   ; Pamela E. Harris   ; Erik Insko   ; Mohamed Omar

Séminaire lotharingien de combinatoire, 78B (2017)

Résumé

We say that a permutation π=π₁π₂...π_n in S_n has a peak at index i if π_i-1 π_i > π_i+1. Let P(π) denote the set of indices where π has a peak. Given a set S of positive integers, we define P(S;n) = {π in S_n : P(π)=S}. In 2013 Billey, Burdzy, and Sagan showed that for subsets of positive integers S and sufficiently large n, |P(S;n)| = p_S(n)2_n-|S|-1 where p_S(x) is a polynomial depending on S. They gave a recursive formula for p_S(x) involving an alternating sum, and they conjectured that the coefficients of p_S(x) expanded in a binomial coefficient basis centered at max(S) are all nonnegative. In this paper we introduce a new recursive formula for |P(S;n)| without alternating sums and we use this recursion to prove that their conjecture is true.