Séminaire Lotharingien de Combinatoire, 78B.6 (2017), 9 pp.

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

A Proof of the Peak Polynomial Positivity Conjecture

Abstract. We say that a permutation π=π1π2...πn in Sn 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 Sn : P(π)=S}. In 2013 Billey, Burdzy, and Sagan showed that for subsets of positive integers S and sufficiently large n, |P(S;n)| = pS(n)2n-|S|-1 where pS(x) is a polynomial depending on S. They gave a recursive formula for pS(x) involving an alternating sum, and they conjectured that the coefficients of pS(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.

Received: November 14, 2016. Accepted: February 17, 2017. Final version: April 1, 2017.

The following versions are available: