Discrete CATS Seminar

Date: 
03/20/2017 - 2:00pm to 3:00pm
Location: 
POT 745
Speaker(s) / Presenter(s): 
Pamela Harris

Speaker: Pamela Harris, Williams College

Title: A proof of the peak polynomial positivity conjecture

 

Abstract: We say that a permutation $\pi=\pi_1\pi_2\cdots \pi_n \in \mathfrak{S}_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 $\pi$ has a peak. Given a set $S$ of positive integers, we define $P(S;n)=\{\pi\in\mathfrak{S}_n:P(\pi)=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 talk 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.

X
Enter your linkblue username.
Enter your linkblue password.
Secure Login

This login is SSL protected

Loading