A proof of the peak polynomial positivity conjecture

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:149

Article

Diaz-Lopez, Alexander¹  Harris, Pamela E.²  Insko, Erik³  Omar, Mohamed⁴ 

[1] Swarthmore Coll, Dept Math & Stat, Swarthmore, PA 19081 USA

[2] Williams Coll, Dept Math & Stat, Williamstown, MA 01267 USA

[3] Florida Gulf Coast Univ, Dept Math, Ft Myers, FL USA

[4] Harvey Mudd Coll, Dept Math, Claremont, CA USA

关键词: Binomial coefficient;    Peaks;    Peak polynomial;    Permutation;    Positivity conjecture;   

DOI  :  10.1016/j.jcta.2017.01.004

来源: Elsevier

【 摘 要 】

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. (C) 2017 Elsevier Inc. All rights reserved.

【 授权许可】

Free