A proof of the peak polynomial positivity conjecture

作者：Diaz Lopez Alexander^*; Harris Pamela E; Insko Erik; Omar Mohamed

来源：Journal of Combinatorial Theory - Series A, 2017, 149: 21-29.

DOI：10.1016/j.jcta.2017.01.004

• Binomial coefficient
• Peaks
• Peak polynomial
• Permutation
• Positivity conjecture

We say that a permutation pi = pi(1) pi(2) center dot center dot center dot pi(n). epsilon G(n) has a peak at index i if pi(i-1) < pi(i) > pi(i+1). Let P(pi) denote the set of indices where z- has a peak. Given a set S of positive integers, we define P(S; n) = {pi epsilon G(n) : P(pi) = S}. In 2013 Billey, Burdzy, and Sagan showed that for subsets of positive integers S and sufficiently large n, vertical bar P(S; n)vertical bar = ps(n)2(n-vertical bar S vertical bar-1) where ps(x) is a polynomial depending on S. They proved this by establishing 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 vertical bar P(S; n)vertical bar without alternating sums and we use this recursion to prove that their conjecture is true.

• 出版日期2017-7