#####
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
**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.

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

The following versions are available: