Peak polynomials: positivity and generalizations to graphs

11/29/2016 - 12:00pm
11/29/2016 - 12:55pm
Mohamed Omar (HMC)

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. Moreover, we develop a generalization of peak polynomials to graphs that is consistent with the $S_n$ case and explore positivity therein.

Millikan 2099 (Pomona College)